排序

冒泡排序

算法思想

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

C语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/** 
 * bubble_sort		-	ascendly bubble sort the array
 *
 * @param array 		the array to be sorted
 * @param length 		the length of the array
 */
extern void bubble_sort(int array[], int length)
{
    int i, j;
    for (i = length; i > 0; i--){
        for (j = 0; j < i-1; j++){
            if (array[j] > array[j+1])
                swap(&array[j], &array[j+1]);
        }
    }
}

特性

• 时间复杂度：\(O(n^2)\)
• 原地：是
• 稳定：是

选择排序

基本思想

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

C语言实现

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

/** 
 * selection_sort	-	ascendly selection sort the array
 *
 * @param array			the array to be sorted 
 * @param length 		the length of the array
 *
 */
extern void selection_sort(int array[], int length)
{
    int i, j, min;
    for (i = 0; i < length; i++) {
        min = i;
        for (j = i; j < length; j++) {
            /* search for the minimum value */
            if (array[min] > array[j]) {
                min = j;
            }            
        }
        if (min != i) {
            /* swap array[j] and min */
            swap(&array[i], &array[min]);
        }
    }
    return;
}

性质

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

• 时间复杂度：\(O(n^2)\)
• 原地：是
• 稳定：否

插入排序

基本思想

插入排序（Insertion Sort）算法类似于玩扑克时抓牌的过程，玩家每拿到一张牌都要插入到手中已有的牌里，使之从小到大排好序。

开始时，我们的左手为空，并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌。

插入排序算法与这个过程类似，但和插入扑克牌有一点不同：不可能在两个相邻的存储单元之间再插入一个单元，因此要将插入点之后的数据依次往后移动一个单元。排序算法如下：

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；
6. 重复步骤2~5。

过程演示

C语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/**
 * insertion_sort	-	ascendly insertion sort the array
 * @param array			the array to be sorted
 * @param length		the length of the array
 *
 * Sorting the array ascendly by using the insertion sort algorithms.
 *
 */
extern void insertion_sort(int array[], int length)
{
    int i, j, key;
    for (i = 1; i < length; j++){
        key = array[i];
        for (j = i - 1; j >= 0 && array[j] > key; j--){
        	array[j+1] = array[j];
        }
        array[j+1] = key;
    }
    return;
}

另外一个用递归实现的插入排序。

性质

• 算法复杂度：\(O(n^2)\) 。当 n 比较小时（e.g. \(n \le 30\)），使用插入排序比较适合；当 n 比较大时，插入排序就显得很慢了。
• 原址^[1]：是
• 稳定^[2]：是

改进版本

• 希尔排序：带步长的采样数据，从而将元素分成若干组进行插入排序。然后再改用更小的步长。
• 二叉查找树排序：利用二叉查找树，快速确定元素的插入位置，从而改进插入排序的效率。
• 图书馆排序：排列图书时，如果在每本书之间留一定的空隙，那么在进行插入时就有可能会少移动一些书。说白了就是在插入排序的基础上，给书与书之间留一定的空隙，这个空隙越大，需要移动的书就越少，这是它的思路——用空间换时间。
• 耐心排序：先将元素入桶，最后用插入排序。

希尔排序

基本思想

希尔排序（Shell Sort）算法是 D.L. Shell 于1959年发明的，它是插入排序的一种高速而稳定的改进版本。

希尔排序通过将比较的全部元素分为若干组来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了。

一个更好理解的希尔排序实现：将数组列在一个表中并对列排序（用插入排序）。重复这过程，不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序。

过程演示

例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

1
2
3
4

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序：

1
2
3
4

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：

1
2
3
4
5
6

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后变为：

1
2
3
4
5
6

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

C语言实现

下面的函数是对整型数组进行排序的Shell排序算法。步长使用了 \(\frac{n}{2}\) 并且对步长取半直到步长达到 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/**
 * shell_sort	-	ascendly shell sort the array
 * @param array		the array to be sorted
 * @param length	the length of the array
 *
 *
 * Sorting the array ascendly by using the shell sort algorithms. 
 *
 */
void shell_sort(int array[], int length)
{
    int gap, i, j, key;
    for (gap = length/2; gap > 0; gap /= 2)
        for (i = gap; i < length; i++)
            for (j=i-gap; j>=0 && array[j]>array[j+gap]; j-=gap) {
                // swap the two elements
                key = array[j];
                array[j] = array[j+gap];
                array[j+gap] = key;
            }
    return;
}

性质

步长的选择

1. 步长的选择是希尔排序的重要部分。只要最终步长为1（此时为插入排序）任何步长串行都可以工作。
2. Donald Shell 最初建议步长选择为 \(\frac{n}{2}\) 并且对步长取半直到步长达到 1。虽然这样取可以比 \(O(n^2)\) 类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。

3. 已知的最好步长串行是由Sedgewick提出的 (1, 5, 19, 41, 109,…)，该串行的项来自 \(9 * 4^i - 9 * 2^i + 1 和 4^i - 3 * 2^i + 1\)。用这样步长串行的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。
4. 另一个在大数组中表现优异的步长串行是(斐波那契数列除去0和1将剩余的数以黄金分区比的两倍的幂进行运算得到的数列：(1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713, …)。

综合评价

1. 时间复杂度： \(O(n\lg{n})\)
2. 原址：是
3. 稳定：否

归并排序

算法思想

归并排序（Merge Sort）算法完全遵循分治模式，直观上其操作如下：

1. 分解：把长度为n的输入序列分成两个长度为n/2的子序列。
2. 解决：对这两个子序列分别采用归并排序。
3. 合并：将两个排序好的子序列合并成一个最终的排序序列。

在描述归并排序的步骤时又调用了归并排序本身，可见这是一个递归的过程。

归并排序算法的一个核心操作是合并步骤中两个已排序序列的合并。回到我们玩扑克牌的例子，假设桌上有两堆牌，每堆都已排序，最小的牌在顶上。我们希望把这两堆牌合并成单一的排好序的输出堆。我们的基本步骤包括在两堆牌的顶上的两张牌中选取较小的一张并将该牌放置到输出堆。重复这个步骤，直到一个输入堆为空，这时，我们只是拿起剩余的输出堆并牌面朝下的将该堆放置到输出堆。

这个合并算法需要 \(\Theta(n)\) 的时间。

过程演示

总体框架

合并过程

C语言实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

/**
 * merge	-	merge array
 * @param array	the array to be merge
 * @param start	the start of the array
 * @param mid	the end of the left array
 * @param end	the end of the whole array
 *
 * A key subroutine of merge sort.
 *
 */
static void merge(int array[], int start, int mid, int end)
{
    // Logically divide the array into two and treat them respectively
    int n1 = mid - start + 1;
    int n2 = end - mid;
    int left[n1], right[n2];
    int i, j, k;
    
    for (i = 0; i < n1; i++)  // left holds array[start...mid]
        left[i] = array[start + i];
    for (j = 0; j < n2; j++)  // right holds array[mid+1..end]
        right[j] = array[mid + 1 + j];
    
    i = j = 0;
    k = start;
    while (i < n1 && j < n2){
    if (left[i] < right[j])
        array[k++] = left[i++];
    else
        array[k++] = right[j++];
    }
    // append the rest to the array
    while (i < n1)  // left[] is not exhausted
        array[k++] = left[i++];
    while (j < n2)
        array[k++] = right[j++];
    
    return;
}


/**
 * msort	-	ascendly merge sort the array
 * @param array	the array to be sorted
 * @param start	the start of the array
 * @param end	the end of the array
 *
 * Sorting the array ascendly by using the merge sort algorithms.
 * The core of merge sort.
 *
 */
static void msort(int array[], int start, int end)
{
    int mid;
    if (start < end){
        mid = (start + end) / 2;
        msort(array, start, mid);
        msort(array, mid + 1, end);
        merge(array, start, mid, end);
    }
    return;
}


/**
 * merge_sort	-	ascendly merge sort the array
 * @param array		the array to be sorted
 * @param length	the length of the array
 *
 * The interface of merge sort.
 * @returns 0 after sorting.
 *
 */
extern void merge_sort(int array[], int length)
{
    msort(array, 0, length-1);
    return;
}

性质

• 算法复杂度：\(O(n\lg{n})\)
• 原址：否
• 稳定：是

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

算法思想

堆

这里的堆(二叉堆)，指得不是堆栈的那个堆，而是一种数据结构。

堆是一个数组，它可以被看成一个近似的完全二叉树。完全二叉树的一个优秀的性质是，除了最底层之外，每一层都是满的，而且是从左向右填充。因此，树上的每一个结点可以对应数组中的一个元素。这使得堆可以利用数组来表示。每一个结点对应数组中的一个元素。

二叉堆一般分为两种：最大堆和最小堆。

最大堆

堆中每个父节点的元素值都大于等于其孩子结点（如果存在）,这样的堆就是一个最大堆。因此,最大堆中的最大元素值出现在根结点(堆顶)。堆排序算法使用的是最大堆。

最小堆

最小堆的组织方式正好相反：最小堆性质是指每个父节点的元素值都小于或等于其孩子结点（如果存在）。因此，最小堆中的最小元素存放在根节点中。最小堆通常用于构造优先队列。

堆节点的访问

通常堆是通过一维数组来实现的。在起始数组为 0 的情形中：

• 父节点i的左子节点在位置 (2*i+1);
• 父节点i的右子节点在位置 (2*i+2);
• 子节点i的父节点在位置 floor((i-1)/2);

堆排序

堆排序是一种利用堆这种数据结构，进行原地排序的排序算法，其时间复杂度是\(O(n\lg{n})\)，而且只和数据规模有关。

堆排序算法是一种很漂亮的算法，这里需要用到三个函数：MaxHeapify、BuildMaxHeap 和 HeapSort。

• 最大堆调整（MaxHeapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。其时间复杂度为 \(O(\lg{n})\) 。
• 创建最大堆（BuildMaxHeap）：将堆所有数据重新排序。具有线性时间复杂度。
• 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。其时间复杂度为 \(O(n\lg{n})\)。

过程演示

MaxHeapify

下图演示了 MaxHeapify 的执行过程。在程序的每一步中，从 A[i]、A[LEFT(i)] 和 A[RIGHT(i)] 中挑选出最大的，并将其下标存储在变量 largest 中。如果 A[i] 是最大的，那么以 i 为根结点的子树已经是最大堆，程序结束。否则，最大元素是 i 的某个孩子结点，则交换 A[i] 和 A[largest] 的值。从而使 i 及其孩子都满足最大堆的性质。在交换后，下标为 largest 的结点的值是原来的 A[i]，于是以该结点为根的子树又有可能会违反最大堆的性质。因此，需要对该子树递归调用 MaxHeapify 。

其中：(a)初始状态，在结点 i=2 处，A[2]违背了 最大堆性质，因为它的值不大于它的孩子。在(b)中，通过交换A[2]和A[4]的值，结点2恢复了最大堆的性质，但又导致结点4违反了最大堆的性质。递归调用 MaxHeapify(A, 4)，此时 i = 4。在©中，通过交换 A[4] 和 A[9] 的值，结点4的最大堆性质得到了恢复。在此递归调用 MaxHeapify(A, 9)，此时不再有新的数据交换。

BuildMaxHeap

BuildMaxHeap中自下而上的调用MaxHeapify来改造数组，建立最大堆。因为MaxHeapify能够保证下标i的结点之后结点都满足最大堆的性质，所以自下而上的调用MaxHeapify能够在改造过程中保持这一性质。

如果最大堆的数量元素是n，那么BuildMaxHeap从PARENT(n)开始，往上依次调用MaxHeapify。

这基于一个定理：如果最大堆有n个元素，那么从PARENT(n)+1，PARENT(n)+2…n都是叶子结点（叶子结点指没有儿子结点的结点）。

HeapSort

HeapSort是堆排序的接口算法，接受数组和元素个数两个参数。

HeapSort先调用BuildMaxHeap将数组改造为最大堆，然后将堆顶和堆底元素交换，之后将底部上升，最后重新调用MaxHeapify保持最大堆性质。

由于堆顶元素必然是堆中最大的元素，所以一次操作之后，堆中存在的最大元素被分离出堆。

重复n-1次之后，数组排列完毕。过程演示如下：

性质

• 时间复杂度：\(\Theta(n\lg{n})\)
• 原地：是
• 稳定：否

快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 \(Ο(n\log n)\) 次比较。在最坏状况下则需要 \(Ο(n^2)\) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他\(Ο(n\log n)\) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

算法思想

快速排序使用分治法策略来把一个串行（list）分为两个子串行（sub-lists）。

1. 分解：从数列中挑出一个元素，称为 “主元”（pivot），并以此将数列分成两个子数列（partition）：所有元素比主元值小的摆放在主元前面，所有元素比主元值大的摆在主元的后面（相同的数可以到任一边），该主元处于数列的中间位置。
2. 排序：递归地把小于主元值元素的子数列和大于主元值元素的子数列排序。
3. 合并：合并子数列。

可见，归并排序做的是是递归地“合并”，而快速排序做的是递归地“分区”。

过程演示

下图是 partition 过程的一个示例。\(A[r]\) 是主元，用浅灰色标记的元素是小于或等于主元的子数列，而深灰色标记的元素是比主元大的子数列。未用颜色标记的元素是尚未被分区的元素。

C语言实现

不依赖标准库的实现

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

/** 
 * sway	-	swap two integers
 *
 * @param a	the first integer
 * @param b	the second integer
 *
 */
static void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
    return;
}


/**
 * partition	-	divide the array into two parts by using a pivot
 * @param array	the array to be divided
 * @param start	the start of the array
 * @param end	the end of the array
 *
 *
 * A key subroutine of quick sort.
 *
 */
static int partition(int array[], int start, int end)
{
    int pivot = array[end];
    int mid = start;
    int i;
    for (i = start; i < end; i++) {
        if(array[i] <= pivot){
            swap(&array[i], &array[mid]);
            mid++;
        }
    }
    swap(&array[end], &array[mid]);
    return mid;
}


/**
 * msort	-	ascendly quick sort the array
 * @param array	the array to be sorted
 * @param start	the start of the array
 * @param end	the end of the array
 *
 * Sorting the array ascendly by using the quick sort algorithms.
 * The core of quick sort.
 *
 */
static int q_sort(int array[], int start, int end)
{
    int mid;
    if (end > start) {
        mid = partition(array, start, end);
        q_sort(array, start, mid-1);
        q_sort(array, mid+1, end);
    }
}


/**
 * quick_sort - ascendly quick sort the array
 * @param array		the array to be sorted
 * @param length	the length of the array
 *
 * The interface of quick sort.
 *
 */
extern void quick_sort(int array[], int length)
{
    q_sort(array, 0, length-1);
    return;
}

直接调用标准库函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <stdio.h>
#include <stdlib.h>
#include "dbg.h"

int array[8] = {2, 8, 7, 1, 3, 5, 6, 4};

int cmp_int ( const void *a , const void *b )
{
    return *(int *)a - *(int *)b;
}

int main(void)
{
    qsort(&array[0], 8, sizeof(int), cmp_int);
    
    int i;
    for (i = 0; i < 8; i++){
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

性质

• 算法复杂度：
  • 最坏情况下（当数据是已排序的时候），快速排序的时间复杂度是 \(\Theta(n^{2})\) ；
  • 大多数情况下，快速排序的时间复杂度是：\(\Theta(n\lg{n})\)。
• 原址：是
• 稳定：否

改进：快速排序的随机化版本

在排序前先将数列随机化，或者采用随机选择主元的方式可以将快速排序的时间复杂度始终限制在 \(\Theta(n\lg{n})\)。在实践中，快速排序往往能够比归并排序快三倍。

线性时间排序

排序算法的下界

比较排序可以被抽象为一棵决策树。决策树是一棵完全二叉树，它可以表示在给定输入规模情况下，某一特定排序算法对所有元素的比较操作。

在决策树种，从根结点到任意一个可达叶结点之间最长简单路径的长度，表示的是对应的排序算法中最坏情况下的比较次数。因此，一个比较排序算法中的最坏情况比较次数就等于其决策树的高度。同时，当决策树中每种排列都是以可达的叶结点的形式出现时，该决策树高度的下界也就是比较排序算法运行时间的下界。

因此，在最坏情况下，任何比较排序算法都需要做 \(\Omega(n\lg{n})\) 次比较。下面介绍两个非比较型整数排序算法，在适当的假设条件下可以达到线性的复杂度。

计数排序

计数排序假设 \(n\) 个输入元素中的每一个都是在 0 到 \(k\) 区间内的一个整数，其中 \(k\) 为某个整数，当 \(k = O(n)\) 时，排序的运行时间为 \(\Theta(n)\) 。

算法思想

对每一个输入元素 x，确定小于 x 的元素个数。利用这一信息，就可以直接把 x 放到它在输出数组中的位置上了。

过程演示

下图是计数排序在输入数组A[1…8]上的处理过程，其中\(A\)中的每一个元素都是不大于 \(k = 5\) 的非负整数。(a) 第5行执行后数组A和辅助数组C的情况。(b)第8行执行后，数组C的情况。©~(e)分别显示了第10~12行的循环体迭代了一次、两次和三次之后，输出数组B和辅助数组C的情况。(f)最终排好序的输出数组B。

性质

• 算法复杂度： \(\Theta(k+n)\) 。在实际工作中，当 \(k = O(n)\) 时，我们一般会采用计数排序，这时的运行时间为 \(\Theta(n)\)。
• 原址：否
• 稳定：是

基数排序

基数排序的发明可以追溯到1887年赫尔曼·何乐礼（Herman Hollerith）在打孔卡片制表机（Tabulation Machine）上的贡献。

基本思想

将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由最低位开始，而MSD则相反，由键值的最高位开始。现在的基数排序通常使用更加高效的LSD的方案。

过程演示

性质

• 算法复杂度： \(\Theta(d(k+n))\)
• 原址：否
• 稳定：是

各种算法的运行时间

其他参考材料

1. 最酷的排序算法演示（冒泡排序 vs. 快速排序）

2. MIT算法导论：课程简介及算法分析

3. MIT算法导论：快排及随机化算法

4. MIT算法导论：线性时间排序

5. 经典排序算法集绵