A·Y

十大常见排序算法

11/19/2021 Sort

# 序言

虽然在各类编程语言中自带的排序API十分高效，但是掌握基本的排序算法还是非常有必要的。

# 冒泡排序

经典入门排序题，易于理解。核心思想在于不断交换出最大值放到最后。缺点是交换次数较多。

def bubbleSort(nums: List[int]) -> List[int]:
    n = len(nums)
    for i in range(n - 1):
        for j in range(n - i - 1):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums
1
2
3
4
5
6
7
  • 时间复杂度：O(n2)。时间复杂度近似n的阶加, 即$\frac{n(n-1)}{2}$ = $\frac{n^2}{2}$，省略常数1/2,
  • 空间复杂度：O(1)
  • 稳定

Tips

nums参数默认为List[int]

# 选择排序

可以看成是冒泡的升级版，核心思想在于不断交换出最小值放到最前。使用min变量记录最小值索引避免了冒泡的频繁交换。

def selectionSort(nums):
    n = len(nums)
    for i in range(n):
        minIndex = i
        for j in range(i + 1, n):
            if nums[minIndex] > nums[j]:
                minIndex = j
        nums[i], nums[minIndex] = nums[minIndex], nums[i]
    return nums
1
2
3
4
5
6
7
8
9
  • 时间复杂度 O(n2)
  • 空间复杂度 O(1)
  • 不稳定

Warning

一直不解为什么选择排序不稳定，网上看到最多的解释是：选择排序的不稳定在于会改变原有相同数据的相对顺序。
一个例子，现在有3个数，分别为:
index：0 1 2
value：2 2 1
选择排序第一次将3和1替换，也就是index为0和2的数替换，此时序列变成了2-1-0，而稳定的做法应该是index序列为2-0-1。
这看起来是个结论，对于解释为什么改变了原有顺序可能会不稳定，多属性排序似乎是个更好的的例子。
假设现在按照学生的 分数（DESC） 和 姓名(ASC) 对学生进行排序，数据如下：
学生1 学生2 学生3
90 90 100
按照选择排序，此时先按照分数进行排序，则为 学生3-学生2-学生1 ，这改变了学生1，学生2的顺序，然后之后按照姓名排序，发现又需要交换学生1，学生2的位置，为 学生3-学生1-学生2 。
假设这里是冒泡（稳定排序），则不会改成学生1和学生2的相对顺序。

# 插入排序

插入排序的思想则更为简单，想象一下你正在玩扑克牌，对于每次新抽的牌，你总是会将它插入到合适的顺序，插入排序同样如此，我们假设第一个是初始牌(已排序部分)，那么对于第1到n的其他牌(未排序状态)，我们则每次对比该张牌是否比上一张牌更小，如果是则交换。

反复进行比较直至新牌被插入到合适的位置，这样当所有牌都比较完之后，整个牌组也是有序的。

def insertionSort(nums):
    n = len(nums)
    for i in range(1, n):
        cur = nums[i]
        bef = i - 1
        while bef >= 0 and cur < nums[bef]:
            nums[bef + 1] = nums[bef]
            bef -= 1
        nums[bef + 1] = cur
    return nums
1
2
3
4
5
6
7
8
9
10
  • 时间复杂度 O(n2)
  • 空间复杂度 O(1)
  • 稳定

Warning

插入排序的时间不稳定（参考上节warning，理解排序算法不稳定与算法时间不稳定的区别）。
最好的情况为n-1次比较和0次交换。
最差的情况为$\frac{n2}{2}$次比较和$\frac{n2}{2}$次交换。
平均为$\frac{n2}{4}$比较和$\frac{n2}{4}$交换。\

# 希尔排序

希尔排序是插入排序的一种优化，在大部分情况下，希尔排序都要优于插入排序，并且希尔排序的代码比较简单，适合于中等数据量。

希尔排序的基本思想是先将原序列按照一定的间隔分成不同组，通过对不同组的对应部分进行插入排序，首先将序列变为基本有序的状态，之后通过不断调整间隔直至1进行插入排序即可。

希尔排序是不稳定的排序，但是最差的情况会比快排最差好些，同时时间复杂度也比较难推，并且对于不同的增量序列有着不同的时间复杂度，所以这里仅提供Knuth增量序列（h＝3 * h + 1）的最差时间复杂度约为O($n^\frac{3}{2}$)。

  • 增量序列：决定间隔按照何种方式定义以及递减
  • Knuth增量序列：一个性能比较好且较易求出的增量序列，公式为 h = 3 * h + 1，条件是小于长度的 $\frac{1}{3}$
  • 顺带一嘴Knuth就是KMP算法的那个K，同时创立了Tex系统，图灵奖获得者。
def shellsort(nums: list):
    n = len(nums)
    h = 1
    while h < n // 3:
        h = h * 3 + 1
    while h > 0:
        for i in range(h, n):
            j = i - h
            cur = nums[i]
            while j >= 0 and cur < nums[j]:
                nums[j + h] = nums[j]
                j -= h
            nums[j + h] = cur
        h = (h - 1) // 3
    return nums
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  • 时间复杂度 O(nlogn)
  • 空间复杂度 O(1)
  • 不稳定

# 归并排序

归并排序利用了分治的思想（Divide-and-Conquer），将序列进行分成n个组合，随后两两进行比较并排序，通过不断组合子数组达到快速排序的目的。

归并排序的好处在于高效的性能，唯一的不足在于消耗了额外的空间，即tmp数组O(n)。

同时由于以下代码采取了递归的方式，递归的最大深度为logn，因此空间复杂度还需要logn的栈空间。

此外，也可以考虑使用迭代的方式实现，这里不多介绍。

def mergeSort(self, nums: List[int], l: int, r: int) -> None:
    if l == r:
        return
    mid = (l + r) // 2
    self.mergeSort(nums, l, mid)
    self.mergeSort(nums, mid + 1, r)
    tmp = []
    i = l
    j = mid + 1
    while i <= mid or j <= r:
        if i > mid or (j <= r and nums[j] < nums[i]):
            tmp.append(nums[j])
            j += 1
        else:
            tmp.append(nums[i])
            i += 1
    nums[l: r + 1] = tmp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  • 时间复杂度 O(nlogn)
  • 空间复杂度 O(n)
  • 稳定

# 快速排序

快速排序基本称得上是老生常谈的话题了，它的基本思想是从数组中选取一个主元（pivot），然后遍历之后其他元素，大于它的我们将它放到右边，小于它的则放到左边，之后再对左右子序列进行同样的操作，直到结束。

快排的pivot的选择方式很多，这里采用的是随机pivot，复杂度在算法导论第七章证明期望为O(nlogn)，空间复杂度则取决于递归深度，最差O(n)，期望O(logn)

def randomizedPartition(self, nums: List[int], l: int, r: int) -> int:
        pivot = random.randint(l, r)
        nums[pivot], nums[r] = nums[r], nums[pivot]
        i = l - 1
        for j in range(l, r):
            if nums[j] < nums[r]:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]
        i += 1
        nums[i], nums[r] = nums[r], nums[i]
        return i
        
def randomizedQuicksort(self, nums: List[int], l: int, r: int) -> None:
    if l >= r:
        return
    mid = self.randomizedPartition(nums, l, r)
    self.randomizedQuicksort(nums, l, mid - 1)
    self.randomizedQuicksort(nums, mid + 1, r)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  • 时间复杂度 O(nlogn)
  • 空间复杂度 O(logn)
  • 不稳定

Warning

快速排序是不稳定的排序，最差的情况的时间复杂度为O(n2)，但是这种情况不多见，一般对于一个较为随机的大序列而言，快速排序甚至能比一些其他时间复杂度稳定于O(nlogn)的排序算法要快上许多，例如归并排序。

# 堆排序

堆排序是一种基于数据结构的排序，堆是完全二叉树，同时分为小根堆和大根堆，对于升序排序选择大根堆，反之选择小根堆。

因为堆顶的数总是最大或者最小的，基于这个性质，我们可以得到依次获取最大或者最小值，然后对其他数进行同样的操作，因此堆排序也可以认为是优化的选择排序。

堆排序比选择排序的好处在于不必消耗线性时间去搜索比较未排序的部分。

def maxHeapify(self, heap, root, heapLen):
        p = root
        # control the node have sub node and not in last layer
        while p * 2 + 1 < heapLen:
            # sub node index of p
            l, r = p * 2 + 1, p * 2 + 2
            # check which is the smaller sub node
            if heapLen <= r or heap[r] < heap[l]:
                nex = l
            else:
                nex = r
            # compare and swap if needed
            if heap[p] < heap[nex]:
                heap[p], heap[nex] = heap[nex], heap[p]
                p = nex
            else:
                break

    def buildHeap(self, heap):
        for i in range(len(heap) - 1, -1, -1):
            self.maxHeapify(heap, i, len(heap))

    def heapSort(self, nums):
        self.buildHeap(nums)
        for i in range(len(nums) - 1, -1, -1):
            nums[i], nums[0] = nums[0], nums[i]
            self.maxHeapify(nums, 0, i)
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
  • 时间复杂度 O(nlogn)
  • 空间复杂度 O(1)
  • 不稳定

Warning

以上是基于比较的排序算法，接下来的三种排序将是基于非比较的排序算法

Tips

任何非比较的排序算法理论上均要比基于比较的排序算法要快。
非比较排序算法通常时间复杂度为O(n+k)，而基于比较的排序算法是O(nlogn)

# 计数排序

计数排序的思想非常简单，前提是序列是整数且范围确定，创建一个bucket，然后进行一次遍历，统计元素出现的次数，接下来只需要再次遍历bucket，将数填充回原序列即可。时间复杂度为O(n+k)，k为bucket数组的长度。

def countingSort(nums, bucketLen):
    bucket = [0] * bucketLen
    for num in nums:
        bucket[num] += 1
    index = 0
    for i in range(bucketLen):
        while bucket[i] > 0:
            nums[index] = i
            index += 1
            bucket[i] -= 1
    return nums
1
2
3
4
5
6
7
8
9
10
11
  • 时间复杂度 O(n+k)
  • 空间复杂度 O(k)
  • 稳定

# 桶排序

桶排序可以理解为计数排序的通解，只不过桶排序的可以控制每个桶的容量。桶排序的核心思想在于把数分配进不同的桶，最后每个桶进行单独排序，最后顺序遍历桶进行合并结果，此处示例代码使用插入排序对每个桶内元素进行排序。（插入排序对于少量数据而言效率较高）

但是对于其它语言而言，数组需要预先分配内存，而桶排序最差的情况需要为每个桶都分配n的空间（当然也可以考虑初始数组-数据扩容的方案。）。而链表虽然不需要提前分配过多空间，但对于链表排序效率也是问题。

def bucketSort(nums, bucketSize):
    def insertionSort(arr):
        for i in range(1, len(arr)):
            cur = arr[i]
            bef = cur - 1
            while bef >= 0 and arr[bef] > cur:
                arr[bef + 1] = arr[bef]
                bef -= 1
            arr[bef + 1] = cur
        return arr

    buckets = [[] for _ in range(bucketSize)]
    for num in nums:
        buckets[int(bucketSize * num)].append(num)
    for i in range(bucketSize):
        buckets[i] = insertionSort(buckets[i])
    sortIndex = 0
    for i in range(bucketSize):
        for j in range(len(buckets[i])):
            nums[sortIndex] = buckets[i][j]
            sortIndex += 1
    return nums
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  • 时间复杂度 O(n+k)
  • 空间复杂度 O(n+k)
  • 稳定

Warning

桶排序不是稳定的，在数据分布最平均时，可达到最大效率，时间复杂度为O(n)，最差情况是所有数据都被放进1个桶，此时则为完全插入排序，时间复杂度退化到O(n2)。因此桶排序有很多变种，这里不再过多介绍。

# 基数排序

基数排序的思想在于把取出每位数，从低位到高位依次排序，当排到最高位时排序结束，排序结束。

由于每位数的范围为0到9，因此内部排序非常适合使用计数排序。

def radixSort(nums):
    def countingSort(nums, exp, n):
        count = [0] * 10
        output = [0] * n
        for i in range(n):
            count[(nums[i] // exp) % 10] += 1
        # ASC
        for i in range(1, 10):
            count[i] += count[i - 1]
        # DESC
        # for i in range(8, -1, -1):
        #     count[i] += count[i + 1]
        for i in range(n-1, -1, -1):
            num = nums[i] // exp
            output[count[num % 10] - 1] = nums[i]
            count[num % 10] -= 1
        for i in range(n):
            nums[i] = output[i]

    n = len(nums)
    ma = max(nums)        
    exp = 1
    while ma // exp >= 1:
        countingSort(nums, exp, n)
        exp *= 10
    return nums
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
  • 时间复杂度 O(n × k)
  • 空间复杂度 O(n + k)
  • 稳定

# 总结

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性
冒泡排序 O(n2) O(n) O(n2) O(1) In-Place 稳定
选择排序 O(n2) O(n2) O(n2) O(1) In-Place 不稳定
插入排序 O(n2) O(n) O(n2) O(1) In-Place 稳定
希尔排序 O(nlogn) O(nlog2n) O(nlog2n) O(1) In-Place 不稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) Out-Place 稳定
快速排序 O(nlogn) O(nlogn) O(n2) O(logn) In-Place 不稳定
堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) In-Place 不稳定
计数排序 O(n + k) O(n + k) O(n + k) O(k) Out-Place 稳定
桶排序 O(n + k) O(n + k) O(n2) O(n + k) Out-Place 稳定
基数排序 O(n × k) O(n × k) O(n × k) O(n + k) Out-Place 稳定