排序算法，伪代码实现

一、插入排序

1. 直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 使用插入排序算法，将目标数组从小到大排列
 * @param array  待排序的目标数组
 * @param n  数组长度
 */
void InsertSort(int array[], int n) {
    int i, j;
    int tmp;
    for (i = 1; i < n; i++) {
        // 遍历待排序元素
        tmp = array[i];
        for (j = i - 1; j >= 0 && array[j] > tmp; j--) {
            // 遍历已排序元素
            array[j + 1] = array[j];
        }
        array[j + 1] = tmp;
    }
}

时间复杂度 O(n^2)，空间复杂度 O(1)。直接插入排序是稳定的排序算法。

2. 希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 使用希尔排序算法，将目标数组从小到大排列
 * @param arrray  待排序的目标数组
 * @param n  数组长度
 */
void ShellSort(int array[], int n) {
    int dk, i, j;
    int tmp;
    for (dk = n / 2; dk >= 1; dk = dk / 2) {
        // 步长变化
        for (i = dk; i < n; i++) {
            // 遍历待排序元素
            if (array[i] < array[i - dk]) {
                tmp = array[i];
                for (j = i - dk; j >= 0 && tmp < array[j]; j -= dk) {
                    // 遍历已排序元素
                    array[j + dk] = array[j];
                }
                array[j + dk] = tmp;
            } // if
        }
    }
}

由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以其时间复杂度分析比较困难。当 n 在某个特定范围时，希尔排序的时间复杂度约为 O(n^1.3)。在最坏情况下希尔排序的时间复杂度为 O(n^2)。

空间复杂度 O(1)。

希尔排序是不稳定的排序算法。

二、交换排序

1. 冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 使用冒泡排序算法，将目标数组从小到大排列
 * @param array  待排序的目标数组
 * @param n  数组长度
 */
void BubbleSort(int array[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool flag = false;     // 本趟冒泡是否发生交换的标志
        for (int j = n - 1; j > i; j--) {
            if (array[j - 1] > array[j]) {
                // 交换
                int tmp = array[j - 1];
                array[j - 1] = array[j];
                array[j] = tmp;

                flag = true;
             }
         }
         if (!flag) {
             // 本趟遍历没有发生交换，说明已有序
             break;
         }
     }
 }

时间复杂度 O(n^2)，空间复杂度 O(1)。冒泡排序是稳定的排序算法。

2. 快速排序

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
/**
 * 使用快速排序算法，将目标数组从小到大排列
 * @param array  待排序的目标数组
 * @param low  起始下标
 * @param high  结束下标
 */
void QuickSort(int array[], int low, int high) {
    if (low < high) {
        int pivotPos = Partition(array, low, high); // 划分
        QuickSort(array, low, pivotPos - 1);
        QuickSort(array, pivotPos + 1, high);
    }
}
/**
 *  将数组划分成两个部分
 *  @param array  待排序的目标数组
 *  @param low  起始下标
 *  @param high  结束下标
 *  @return  已在最终位置元素的下标
 */
int Partition(int array[], int low, int high) {
    int pivot = array[low];             // 将第一个元素设为枢轴值，对表进行划分
    while (low < high) {
        while (low < high && array[high] >= pivot) {
            --high;
        }
        array[low] = array[high];       // 将比枢轴值小的元素移动到左端
        while (low < high && array[low] <= pivot) {
            ++low;
        }
        array[high] = array[low];       // 将比枢轴值大的元素移动到右端
    }
    array[low] = pivot;                 // 枢轴值存放到最终位置
    return low;
}

时间复杂度 O(nlogn)，空间复杂度 O(logn)。快速排序是不稳定的排序算法。

三、选择排序

1. 简单选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 使用简单选择排序算法，将目标数组从小到大排列
 * @param array  待排序的目标数组
 * @param n  数组长度
 */
void SelectSort(int array[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // 遍历所有待排序元素，每一轮遍历，找出最小元素并交换到最终位置
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (array[j] < array[min]) {
                min = j;
            }
        }
        if (min != i) {
            // 交换
            int tmp = array[min];
            array[min] = array[i];
            array[i] = tmp;
        }
    }
}

时间复杂度 O(n^2)，空间复杂度 O(1)。简单选择排序是不稳定的排序算法。

2. 堆排序

堆的定义如下：n 个关键字序列 L[1…n] 称为堆，当且仅当该序列满足：

(1) L(i) <= L(2i) 且 L(i) <= L(2i + 1) 或 (2) L(i) >= L(2i) 且 L(i) >= L(2i + 1)

（1 <= i <= n/2）

满足第(1)种情况的堆称为小根堆（小顶堆），满足第(2)种情况的堆称为大根堆（大顶堆）。

下面代码都是构造和维护大根堆。

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
/**
 * 使用堆排序算法，将目标数组从小到大排列
 */
void HeapSort(int A[], int len) {
    BuildMaxHeap(A, len);       // 初始建堆
    for (i = len; i > 1; i--) {
        // n - 1 趟的交换和建堆过程
        // 输出堆顶元素（和堆底元素交换）
        int tmp = A[i];
        A[i] = A[1];
        A[1] = tmp;

        // 整理，把剩余的 i - 1 个元素整理成堆
        AdjustDown(A, 1, i - 1);
    } // for
}
/**
 * 建立大根堆，注意 A[0] 中不存储元素，实际存储从 A[1] 开始
 */
void BuildMaxHeap(int A[], int len) {
    for (int i = len/2; i > 0; i--) {   // 从 len/2 ~ 1，反复调整堆
        AdjustDown(A, i, len);
    }
}
/**
 * 将元素 k 向下进行调整
 */
void AdjustDown(int A[], int k, int len) {
    A[0] = A[k];            // A[0] 暂存
    for (i = 2 * k; i <= len; i*= 2) {
        // 沿 key 较大的子结点向下筛选
        if (i < len && A[i] < A[i + 1]) {
            // 取 key 较大的子结点的下标
            i++;
        }
        if (A[0] >= A[i]) {
            // 筛选结束
            break;
        } else {
            A[k] = A[i];    // 将 A[i] 调整到双亲结点上
            k = i;          // 修改 k 值，以便继续向下筛选
        }
    } // for
    A[k] = A[0];            // 被筛选结点的值放入最终位置
}
1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 参数 k 为向上调整的结点，也为堆的元素个数
 */
void AdjustUp(int A[], int k) {
    A[0] = A[k];
    int i = k / 2;  // 若结点值大于双亲结点，则将双亲结点向下调，并继续向上比较
    while (i > 0 && A[i] < A[0]) {
        A[k] = A[i];
        k = i;
        i = k / 2;
    } // while
    A[k] = A[0];
}

注意：堆最重要的操作就是函数 AdjustDown 和 AdjustUp，其余操作均通过这两个操作完成。

时间复杂度 O(nlogn)，空间复杂度 O(1)。堆排序是不稳定的排序算法。

四、归并排序

1. 二路归并排序

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
/**
 * 使用二路归并排序算法，将目标数组从小到大排列
 * @param array  待排序的目标数组
 * @param low  起始下标
 * @param high  结束下标
 */
void MergeSort(int array[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        MergeSort(array, low, mid);        // 对左侧子序列进行递归排序
        MergeSort(array, mid + 1, high);   // 对右侧子序列进行递归排序
        Merge(array, low, mid, high);          // 归并
    }
}
int *B = (int *)malloc((n) * sizeof(int));  // 辅助数组
void Merge(int array[], int low, int mid, int high) {
    int i, j, k;
    for (k = low; k <= high; k++) {
        // 将 array 中元素拷贝到 B 中
        B[k] = array[k];
    }
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
        // 比较 B 中左右两段中的元素，将较小值拷贝到 array 中
        if (B[i] < B[j]) {
            array[k] = B[i++];
        } else {
            array[k] = B[j++];
        }
    } // for
    // 下面两个 while 循环只有一个会执行
    while (i <= mid) {
        // 第一个表未检测完
        array[k++] = B[i++];
    }
    while (j <= high) {
        // 第二个表未检测完
        array[k++] = B[j++];
    }
 }

时间复杂度 O(nlogn)，空间复杂度 O(n)。二路归并排序是稳定的排序算法。

原地归并排序不需要辅助数组即可归并，空间复杂度 O(1)。关键在于 Merge 函数，如下所示。

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
/**
 * 将长度为 n 的数组逆序
 */
void reverse(int array[], int n) {
    int i = 0;
    int j = n - 1;
    while (i < j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;

        i++;
        j--;
    }
}
/**
 * 将含有 n 个元素的数组向左循环移位 i 个位置
 */
void exchange(int array[], int n, int i) {
    reverse(array, i);
    reverse(array + i, n - i);
    reverse(array, n);
}
void Merge(int array[], int low, int mid, int high) {
    int i = low;
    int j = mid + 1;
    while (i < j && j <= high) {
        int step = 0;
        while (i < j && array[i] <= array[j]) {
            i++;
        }
        while (j <= high && array[j] <= array[i]) {
            j++;
            step++;
        }
        // array + i 为子数组首地址，j - i 为子数组元素个数，j - i - step 为左循环移位的个数
        exchange(array + i, j - i, j - i - step);
        i += step;
    }
}

2. 多路归并排序

外部排序指的是大文件的排序，即待排序的记录存储在外部存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。

外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行归并排序。

参考文献：

王道论坛. 程序员求职宝典. 电子工业出版社.