排序算法的那些事儿

〇、

对于排序算法的考察是很基础的算法考察，而很多面试都会有手写代码的考察，因此这次总结中代码的实现用了伪代码。

可以了解到：

  1. 常见的排序算法
  2. 算法的实现

（最后来写这个引言，真是毫无生气啊……

一、

排序算法 时间复杂度 空间复杂度 是否稳定
冒泡排序 О($n^2$) О($1$) 是
选择排序 О($n^2$) О($1$) 否
插入排序 О($n^2$) О($1$) 是
希尔排序 О($n\log^2{n}$) О($1$) 否
归并排序 О($n\log{n}$) О($n$) 是
快速排序 О($n\log{n}$) О($\log{n}$) 否
堆排序 О($n\log{n}$) О($1$) 否
计数排序 О($n+k$) О($k$) 是
基数排序 О($nk$) О($n+k$) 是

二、

一）冒泡排序（Bubble Sort）

冒泡排序是思想非常简单的排序算法：重复地比较相邻两个数据的大小，将较小的靠前，较大的靠后，将顺序错误的数据交换过来，直到没有再需要交换的数据为止。

冒泡排序还是原地算法（in-place algorithm），即不需要额外的辅助空间来进行转换的算法，包含了空间复杂度为О(1)的所有算法。

而“稳定”是指，对于数值相同的元素，其排列的顺序在经过排序后并没有发生改变，则称这样的排序算法是稳定的。

冒泡算法虽然简单，但在数列数据较大时很没有效率，因此唯一的用处大概就是学习算法课程的时候，经常被用来介绍算法的概念吧。

伪代码如下：

1
2
3
4
5
6
function bubble_sort (array, length):
    var i, j
    for i <- 0 to length-1:
        for j <- 0 to length-1-i:
            if array[j] > array[j+1]:
                swap(array[j], array[j+1])

上面的pseudo-code只有循环判断过整个数列后才会停止，很可能在后面数列已经排序完成，却进行了许多无用的判断。为了优化此算法，可以加入判断条件，如果一次内循环没有交换过任何数据，即表明数列已经完成了排序。

1
2
3
4
5
6
7
8
9
10
11
12
function bubble_sort_withflag (array, length):
    var i, j
    bool flag
    for i <- 0 to length-1:
        flag <- false
        for j <- 0 to length-1-i):
            if array[j] > array[j+1]:
                swap(array[j], array[j+1])
                flag <- true

        if (flag == false)
            break

还可以继续优化算法，通过尝试已经大部分有序的数列（如2，3，4，5，1），冒泡算法依然要进行完整的循环。但如果此时能够反向的“冒泡”，即可一次循环就将数据“1”排到正确的位置上去。

这种改进的算法叫做鸡尾酒排序（Cocktail Sort），也叫定向冒泡排序，排序时将以两个方向在数列中进行排序，因此对于大部分有序的数列，时间复杂度会接近О($n^2$)，当然平均复杂度依然是О($n^2$)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function cocktail_sort (array, length):
    var left <- 0, right <- length - 1
    bool flag
    while left < right:
        flag <- false
        for var i <- left to right-1:
            if array[i] > array[i + 1]:
                swap(array[i], array[i + 1])
                flag <- true
        right--
        for var j <- right to left+1:
            if array[j] < array[i - 1]:
                swap(array[i], array[i - 1])
                flag <- true
        left++
        if (flag == false)
        break

二）选择排序（Selection Sort）

选择排序的基本思想也很简单：首先在未排序序列中找到最小（或者最大）元素，存放到排序序列的起始（末尾）位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的优势在于交换次数较冒泡排序更少，通常交换操作需要的CPU时间比比较操作的时间更多，因此选择排序是要优于冒泡排序的，但同样也是О($n^2$)的时间复杂度就是了；另外一个优势是原地操作，当空间复杂度要求较高时，可以考虑选择排序，但实际上可以使用的场合非常罕见了。

1
2
3
4
5
6
7
8
function selection_sort(array, length):
    int min
    for int i <- 0 to length-1:
        min <- i
        for int j <- i+1 to length:
            if array[j] < array[i]:
                min <- j
        swap(array[min], array[i])

三）插入排序（Insertion Sort）

插入排序的基本思想是将序列划分为有序部分和未排序部分，对于未排序部分的数据，在有序部分从后向前扫描，找到正确的位置插入。

同时插入排序是在线算法，并不要求输入数据在开始运行前完备。

1
2
3
4
5
6
7
8
9
10
function insertion_sort(array, length):
    int i, j
    int temp
    for i <- 1 to length-1:
        temp <- array[i]
        j <- i
        while j > 0 and array[j-1]>temp:
            array[j] <- array[j-1]
            j--
        array[j] <- temp

四）希尔排序（Shell Sort）

希尔排序是对插入排序的一种改进版本，也叫递减增量排序算法。其基本思想是：将全部元素分为几个区域，提升插入排序的性能（一次性让元素向着最终的位置前进一大步）。通过不断减少步长，到最后插入排序（步长为1时），数列几乎是已经排列好的了。

1
2
3
4
5
6
7
8
9
10
11
12
13
function shell_sort(array, length):
    int i, j, step
    int temp // element type in array
    while step > 0:
        for i <- step to length-1:
            temp <- array[i]
            j <- i
            while j >= step and array[j - step] > temp:
                array[j] <- array[j - step]
                j <- j - step
            array[j] <- temp
        step <- step / 2

五）归并排序（Merge Sort）

归并排序的基本思想是采用分治法（Divide and Conquer），基于归并操作，首先与插入算法类似地将每个元素看作已经排好序的子序列，之后两两进行归并操作，直到完成序列的排序。

进行归并操作需要О($n$)的额外空间，在较大数据排序的效率上可以接受，但特别大的数据在空间上不可接受。

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
function merge_sort(arr, length):
    int[] temp = arr
    merge_sort_recursive(arr, temp, 0, length-1)

function merge_sort_recursive(arr, temp, left, right):
    // 分割问题
    if left >= right:
        return
    int mid <- (right - left) >> 1 + left
    int l1 <- left, l2 <- mid+1
    int r1 <- mid, r2 <- right
    merge_sort_recursive(arr, temp, l1, r1)
    merge_sort_recursive(arr, temp, l2, r2)
    // 处理问题
    int i <- left
    while l1 <= r1 and l2 <= r2:
        if arr[l1] < arr[l2]:
            temp[i++] <- arr[l1++]
        else:
            temp[i++] <- arr[l2++]
    while l1 <= r1:
        temp[i++] <- arr[l1++]
    while l2 <= r2:
        temp[i++] <- arr[l2++]
    for k <- left to right:
        arr[k] <- temp[k]

六）快速排序（Quick Sort

快速排序，又称划分交换排序（partition-exchange sort），简称快排。都说是经常会被拿出来考的算法。基本思想也是使用了分治法，选定一个pivot值，将序列分为两个子序列，其中左侧的子序列全部小于pivot，右侧的子序列全部大于pivot，直到每个子序列只有一个数据排序完成。

由于使用递归，每次递归需要О($1$)的额外空间，因此原地（in-place）的快速排序算法平均需要О($\log{n}$)的额外空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function quick_sort(arr, length):
    quick_sort_recursive(arr, 0, length-1)
    
function quick_sort_recursive(arr, left, right):
    if left < right:
        int l <- left, r <- right, cur <- right
        int pivot <- arr[right]
        while l < r:
            while l < r and arr[l] < pivot: l++
            while l < r and arr[r] >= pivot: r--
            arr[cur] <- arr[l]
            arr[l] <- arr[r]
            cur <- r
        arr[cur] <- pivot
        quick_sort_recursive(arr, left, cur-1)
        quick_sort_recursive(arr, cur+1, right)

为了避免递归过深，在内省排序（introsort）算法中，当递归深度超过一定深度（深度为排序元素数量的对数值）后转为堆排序。2000年SGI的C++标准模板库中的不稳定排序算法就采用了Introsort。

七）堆排序（Heap Sort）

堆排序的基本思想是利用堆数据结构，利用最大堆调整，将数列保存到最大堆中，之后将根节点与堆尾互换完成排序。

最大堆调整（Max_Heapify）是将堆的末端子节点作调整，使得子节点永远小于父节点，以符合最大堆的结构要求。

将最大堆存入数组中，对于节点i与其相关节点之间的关系为（索引从1开始）：节点i的父亲节点为$\lfloor{\frac{i}{2}}\rfloor$，节点i的左子节点为$2i$，节点i的右子节点为$2i+1$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function max_heapify(arr, start, end):
    p <- start
    c <- p * 2 + 1
    while c <= end:
        if c + 1 <= end and arr[c] < arr[c+1]:
            c++
        if arr[p] > arr[c]:
            return
        else:
            swap(arr[p], arr[c])
            p <- c
            c <- p * 2 + 1

function heap_sort(arr, len):
    for i <- len/2 to 0:
        max_heapify(arr, i, len-1)
    for i <- len-1 to 0:
        swap(arr[0], arr[i])
        max_heapify(arr, 0, i-1)

八）计数排序（Counting Sort）

计数排序与基数排序不同于上面的排序，并不是基于比较的排序算法，因此可以突破О($n\log{n}$)的极限，称为线性时间排序算法。

计数排序的方法是使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。

过程：

  1. 找出待排序的数组中最大和最小的元素
  2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
  3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
  4. 反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1
1
2
3
4
5
6
7
8
9
10
11
12
function counting_sort(arr, len):
    m <- max(elements in arr)
    counts <- new array(m + 1)
    sorted <- new array(len)
    for i <- 0 to m:
        counts[i] <- 0
    for i <- 0 to len:
        connts[arr[i]]++
    for i <- 1 to m:
        counts[i] += counts[i-1]
    for i <- len-1 to 0:
        sorted[--counts[arr[i]]] = arr[i]

九）基数排序（Radix Sort）

基数排序的原理是将整数按位数切割成不同的数字，然后按每个位数分别比较，从低位到高位进行排序。

1
2
3
4
5
6
7
function radix_sort(arr, len):
    m <- max_bit(arr)
    radix <- 1
    for i <- 0 to m-1:
        counting_sort_by_bit(arr, len, radix)
        radix <- 10*radix
    return arr

三、

问题：

  1. 基于比较的排序算法的极限时间复杂度是？为什么？
  2. 从数组到链表时间复杂度显著增大的排序方法有哪些？