常见排序算法有快速排序、插入排序、冒泡排序、归并排序、希尔排序
可以在leetcode这道题里面实验所有的方法https://leetcode-cn.com/problems/sort-an-array

快速排序

时间复杂度O(nlgn), 空间复杂度O(n), 不稳定排序

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def quick_sort(nums):

    def partition(start, end, nums):
        if start >= end:
            return
        p = nums[start]
        left = start
        right = end
        while left < right:
            while nums[right] >= p and left < right:
                right -= 1
            while nums[left] <= p and left < right:
                left += 1
            nums[right], nums[left] = nums[left], nums[right]
        nums[start], nums[left] = nums[left], nums[start]
        partition(start, left - 1, nums)
        partition(left + 1, end, nums)
    partition(0, len(nums)-1, nums)

javascript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function quickSort(nums) {
  function partition(start, end, nums) {
    if (start >= end) return;
    let p = nums[start], l = start, r = end, t;
    while (l < r) {
      while (l < r && nums[r] >= p) {
        r -= 1;
      }
      while (l < r && nums[l] <= p) {
        l += 1;
      }
      t = nums[l];  // 交换
      nums[l] = nums[r];
      nums[r] = t;
    }
    t = nums[start];  // 交换中轴
    nums[start] = nums[l];
    nums[l] = t;
    partition(start, l - 1, nums);
    partition(l + 1, end, nums);
  }
  partition(0, nums.length - 1, nums);
}

插入排序

时间复杂度O(n^2), 空间复杂度O(1), 稳定排序

python实现

1
2
3
4
5
6
7
8
9
10
def insertSort(nums):
    start = 0
    end = len(nums)
    for i in range(start, end):
        j = i-1
        temp = nums[i]
        while temp < nums[j] and j >= 0:  # 往后移，直到有可以插入的空位
            nums[j+1] = nums[j]
            j -= 1
        nums[j+1] = temp

javascript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
function insertSort(nums) {
  let len = nums.length;
  let temp;
  for (let i = 0; i < len; i++) {
    temp = nums[i];
    j = i - 1;
    while (j >= 0 && temp < nums[j]) {
      nums[j+1] = nums[j];
      j -= 1;
    }
    nums[j+1] = temp;
  }
}

希尔排序

非稳定排序算法，时间复杂度O(nlg2n), 空间复杂度O(1)
将插入排序的对所有元素进行比较，改为将全部元素划分为几个区域，使得元素能够一次性的向正确位置跨越一大步。然后算法将步数越变越小，在这个过程中，数据是几乎排好序的，所以插入排序选择可能位置的时间很少。

python实现

1
2
3
4
5
6
7
8
9
10
11
12
def shell_sort(nums):
    end = len(nums)
    inc = len(nums) // 2 # 步进
    while inc > 0:
        for i in range(inc, end):  # 从inc, inc+1, inc+2遍历
            temp = nums[i]
            j = i - inc
            while temp < nums[j] and j >= 0:
                nums[j+inc] = nums[j]
                j -= inc
            nums[j+inc] = temp
        inc //= 2

javascript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function shellSort(nums) {
  let step = Math.floor(nums.length / 2);
  let len = nums.length;
  while (step > 0) {
    for (let i = step; i < len; i += step) {
      temp = nums[i];
      j = i - step;
      while (j >= 0 && temp < nums[j]) {
        nums[j+step] = nums[j];
        j -= step;
      }
      nums[j+step] = temp;
    }
    step = Math.floor(step / 2)
  }
}

冒泡排序

时间复杂度O(n^2)，空间复杂度O(1)，稳定排序
python实现

1
2
3
4
5
6
def bubble_sort(nums):
    for i in range(len(nums)):
        for j in range(0, len(nums)-1):  # 交互大小相反的元素
            if nums[j] > nums[j+1]:
                nums[j+1], nums[j] = nums[j], nums[j+1]

javascript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function bubbleSort(nums) {
  let len = nums.length;
  let temp;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      if (nums[j] > nums[j+1]) {
        temp = nums[j];
        nums[j] = nums[j+1];
        nums[j+1] = temp;
      }
    }
  }
}

归并排序

时间复杂度O(nlgn), 空间复杂度O(n)，稳定排序

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def merge_sort(nums):

    def merge(left, mid, right, nums):
        i = left
        j = mid+1
        temp = []
        while i <= mid and j <= right:
            if nums[i] <= nums[j]:
                temp.append(nums[i])
                i += 1
            else:
                temp.append(nums[j])
                j += 1
        if i <= mid:
            temp.extend(nums[i: mid+1])
        if j <= right:
            temp.extend(nums[j: right+1])
        nums[left: right+1] = temp

    def divide(start, end, nums):  # 拆分
        if start < end:
            mid = (start + end) // 2
            divide(start, mid, nums)
            divide(mid+1, end, nums)
            merge(start, mid, end, nums)  # 归并

    divide(0, len(nums)-1, nums)

javascript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function mergeSort(nums) {
  function merge(left, mid, right, nums) {
    let i = left,
      j = mid + 1,
      temp = new Array;
    while (i <= mid && j <= right) {
      if (nums[i] < nums[j]) {
        temp.push(nums[i]);
        i += 1;
      } else {
        temp.push(nums[j]);
        j += 1;
      }
    }
    while (i <= mid) {
      temp.push(nums[i]);
      i += 1;
    }
    while (j <= right) {
      temp.push(nums[j]);
      j += 1;
    }
    nums.splice(left, temp.length, ...temp); // 替换为以merge数组
  }

  function divide(start, end, nums) {
    if (start < end) {
      let mid = Math.floor((start+end)/2);
      divide(start, mid, nums);
      divide(mid+1, end, nums);
      merge(start, mid, end, nums);
    }
  }

  divide(0, nums.length-1, nums);
}

堆排序

时间复杂度O(nlogn)，空间复杂度O(1)，不稳定算法。

其中最关键的是heapify操作，让二叉树大根堆化，也就是父节点要比任意子节点大。排序操作也就是在不同范围内找到堆顶，也就是最大值，下一次大根堆化不把上次的堆顶计算进来。

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def heapify(nums, start, end):
    # 构建当前子树为大根堆
    parent = start
    while parent < end:
        son = parent * 2 + 1
        if son > end:
            return
        if son < end and nums[son+1] > nums[son]:
            son += 1
        if nums[parent] > nums[son]:
            return
        nums[parent], nums[son] = nums[son], nums[parent]
        parent = son


def heap_sort(nums):
    parent = len(nums)//2 - 1  # 最后一个父节点
    end = len(nums) - 1
    for i in range(parent, -1, -1):
        # 将每个子树都大根化
        heapify(nums, i, end)
    print(nums)
    for i in range(len(nums)-1, -1, -1):
        nums[i], nums[0] = nums[0], nums[i]
        print(nums)
        heapify(nums, 0, i-1)

javascript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function heapSort(nums) {
  let len = nums.length;

  function heapify(start, end) {
    let parent = start;
    let son;
    while (parent < end) {
      son = 2 * parent + 1;
      if (son > end) return;
      if (son < end && nums[son] < nums[son + 1]) {
        son += 1
      }
      if (nums[parent] > nums[son]) {
        return;
      }
      let t = nums[parent]
      nums[parent] = nums[son]
      nums[son] = t
      parent = son;
    }
  }

  let lastParent = Math.floor(nums.length / 2) + 1;
  for (let i = lastParent; i >= 0; i--) {
    heapify(i, len - 1);
  }
  for (let i = len - 1; i > 0; i--) {
    let t = nums[0];
    nums[0] = nums[i];
    nums[i] = t;
    heapify(0, i - 1);
  }
  return nums
}

选择排序

时间复杂度O(n^2)，空间复杂度O(1),不稳定

每次选择最小的值，放入当前位置。

javascript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
function selectSort(nums) {
    let len = nums.length;
    for (let i = 0; i < len; i++) {
        let temp = i;
        for (let j = i+1; j < len; j++) {
            if (nums[temp] > nums[j]) {
                temp = j;
            }
        }
        [nums[temp], nums[i]] = [nums[i], nums[temp]]
    }
    return nums
}