排序算法总结

发表于 | 分类于 | 阅读次数:

综述

本文主要讲解三种经典的排序算法：插入排序，快速排序以及归并排序。本文的完整代码可以在我的github找到。

插入排序

插入排序的基本思想是：假设数组arr在下标j之前的数组已经是有序的，将下标的为j的元素插入到前面的有序数组中。其python代码示例如下：

1
2
3
4
5
6
7
8
def insert_sort(arr):
    for i in range(1, len(arr)):
        t, j = arr[i], i - 1
        while j >= 0 and arr[j] > arr[i]:
            arr[j + 1] = arr[j]
            j -= 1
        
        arr[j + 1] = t

插入排序的时间复杂度可以很清晰的看出为O($n^2$)，其空间复杂度为O(1)。

快速排序

快速排序的基本思想是：找到数组arr一个元素在排序之后的下标j，即当i < j 时，arr[i] < arr[j]；当i > j 时，arr[i] > arr[j]。其python代码示例如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def quick_sort(arr, l=None, r=None):
    if l is None:
        l = 0
    if r is None:
        r = len(arr) - 1
    if l < r:
        i, j = l, l
        while i < r:
            if arr[i] < arr[r]:
                arr[j], arr[i] = arr[i], arr[j]
                j += 1
            
            i += 1
            
        arr[j], arr[r] = arr[r], arr[j]
        quick_sort(arr, l, j - 1)
        quick_sort(arr, j + 1, r)

从代码中可以看出其数组arr的原址上进行排序，因此也被称为原址排序法。从代码中可以看出在数组arr外只使用了常数项的额外空间，因此其空间复杂度为O(1)。时间复杂度最坏情况下，即每次原则用于划分的元素（称为主元）恰好为当前要排序元素的最值，此时每次划分得到的结果都是主元本身和其它元素。因此，最坏情况下其时间复杂度为O($n^2$)。当然如果每次的划分为相对平衡的划分，即最好情况下，其时间复杂度为O(nlogn)。代码中每次选择的主元为数组的最后一位，当然也可随机在[l, r]内选择一个元素作为主元，并将其与最后移位元素交换。

归并排序

归并排序是利用分治策略的排序方法，其基本思想如下：将数组大致分为两半进行归并排序，然后再将两个已经排完序的数组进行归并。其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
def merge_sort(arr, l=None, r=None):
    if l is None:
        l = 0
    if r is None:
        r = len(arr)
    
    if r > l + 1:
        m = (l + r) // 2
        merge_sort(arr, l, m)
        merge_sort(arr, m, r)
       j, k = l, m
        t = []
        for i in range(l, r):
            t1 = arr[j] if j < m else arr[k] + 1
            t2 = arr[k] if k < r else arr[j] + 1
            if t1 < t2:
                t.append(t1)
                j += 1
            else:
                t.append(t2)
                k += 1

        for i in range(l, r):
            arr[i] = t[i - l]

从代码中可以看出，归并排序采用递归的方法对等分的子数组进行归并排序，因此其时间复杂度为O(nlogn)，空间复杂度为O(n)。

Reference

本文主要参考《算法导论》。