罗朝辉（飘飘白云）

排序算法之交换排序   

罗朝辉（http://www.cppblog.com/kesalin）

转载请注明出处

排序是数据处理中经常使用的一种重要运算，在计算机及其应用系统中，花费在排序上的时间在系统运行时间中占有很大比重，其重要性无需多言。下文将介绍常用的如下排序方法，对它们进行简单的分析和比较，并提供 C 语言实现。

所谓排序，就是要将一堆记录，使之按关键字递增(或递减)次序排列起来。根据排序所采用的策略，可以分为如下五种：

1、插入排序（直接插入排序、希尔排序）；

2、交换排序（冒泡排序、快速排序）；

3、选择排序（直接选择排序、堆排序）；

4、归并排序；

5、桶排序（桶排序，基数排序）；

---------------------------------------------------------------------------------

前面我们讲了插入排序，下面接着来讲交换排序。

交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。应用交换排序基本思想的主要排序方法有：冒泡排序和快速排序。

冒泡排序（Bubble Sorting）

基本思想：从后往前扫描序列，通过相邻元素之间的比较与交换，使值较小的元素逐渐从后部移向前部（从下标较大的单元移向下标较小的单元），就象水底下的气泡一样逐渐向上冒。故称为冒泡排序法。

C 代码实现：

 1void bubble_sort(int* array, int length)
 2{
 3    assert(array && length >= 0);
 4
 5    int i, j, temp;
 6
 7    for (i = 1; i < length; ++i) {
 8        for (j = length - 1; j >= i; --j) {
 9            if (array[j] < array[j - 1]) {
10                temp = array[j];
11                array[j] = array[j - 1];
12                array[j - 1] = temp;
13            }
14        }
15    }
16}

   若在某一趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则，因此，冒泡排序过程可在此趟排序后终止。因此，上面的实现可以优化如下：

 1void bubble_sort(int* array, int length)
 2{
 3    assert(array && length >= 0);
 4
 5    int i, j, temp;
 6    bool exchange;
 7
 8    for (i = 1; i < length; ++i) {
 9        exchange = false;
10
11        for (j = length - 1; j >= i; --j) {
12            if (array[j] < array[j - 1]) {
13                temp = array[j];
14                array[j] = array[j - 1];
15                array[j - 1] = temp;
16
17                exchange = true;
18            }
19        }
20
21        if (!exchange) {
22            break;
23        }
24    }
25}

   还可以通过减少排序的趟数作进一步的优化。在每趟扫描中，记住最后一次交换发生的位置 lastExchange （该位置之前的相邻记录均已有序）。下一趟排序开始时，array[1..lastExchange - 1] 是有序区， array[lastExchange..n] 是无序区。这样，一趟排序可能使当前有序区扩充多个记录，从而减少排序的趟数。实现如下：

 1void bubble_sort(int* array, int length)
 2{
 3    assert(array && length >= 0);
 4
 5    int i, j, temp;
 6    bool exchange;
 7    int lastExchange = 1;
 8
 9    for (i = 1; i < length;) {
10        exchange = false;
11
12        for (j = length - 1; j >= i; --j) {
13            if (array[j] < array[j - 1]) {
14                temp = array[j];
15                array[j] = array[j - 1];
16                array[j - 1] = temp;
17
18                lastExchange = j;
19                exchange = true;
20            }
21        }
22
23        if (!exchange) {
24            break;
25        }
26
27        i = lastExchange + 1;
28    }
29}

   如果待排序序列是基本有序（比如只有第一个元素是最大的，其他的都已有序，在这种情况下，本该只需要 1 趟排序就可以完成），如果用上面的实现 ，这时平均时间复杂达到最坏 O(n^2）。 在这种情况下，可以通过交替改变扫描方向（从后往前，从前往后，再从后往前...）改变不对称性达到优化的目的。具体实现就留着当作业啦，^_^

时间复杂度：
最好的情况下，待排序记录已经有序，只需要一趟排序就可以完成，所以冒泡排序的最好时间复杂度为 O(n)。
最坏的情况下，待排序记录反序，这时需要 n - 1 趟排序，每趟排序需要比较 n - i 次比较操作，这时比较和移动的次数达到最大值，所以冒泡排序的最坏时间复杂度为 O(n ^ 2)。

冒泡排序的平均时间复杂度为 O(n ^ 2)。因为它移动的次数较多，其平均时间性能还不如直接插入排序。

空间复杂度：
很明显，O(1)。

补充：
冒泡排序是就地排序，且是稳定排序。

快速排序

基本思想：采用分治法。设当前待排序的无序区为 array[low..high]，在其中任选一个记录作为基准(Pivot)，调整基准在序列中的位置 prvotpos，使左边子区间中所有记录的关键字均小于等于基准记录的关键字，右边的子区间中所有记录的关键字均大于等于基准记录的关键字。即基准将当前无序区划分为左、右两个较小的子区间 array[low..pivotpos - 1] 和 array[pivotpos + 1..high]，而基准记录已经处在正确的位置上，它无须参加后续的排序。这时，排序问题就分解成两个子区间的排序问题（这就是分而治之的思想啊）， 递归对左右子区间进行快速排序，就可以完成排序。

BTW，分治法的基本思想：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

代码实现：

 1// 对 [low, high] 做划分，并返回基准记录的位置
 2int quick_partition(int* array, int low, int high)
 3{
 4    assert(array && low >= 0 && low <= high);
 5
 6    int pivot = array[low]; // 用区间的第 1 个记录作为基准
 7
 8    while (low < high) {
 9        while (low < high && array[high] >= pivot) {
10            --high;
11        }
12
13        if (low < high) {
14            array[low++] = array[high];
15        }
16
17        while (low < high && array[low] <= pivot) {
18            ++low;
19        }
20
21        if (low < high) {
22            array[high--] = array[low];
23        }
24    }
25
26    array[low] = pivot;
27
28    return low;
29}
30
31void quick_sort_impl(int* array, int low, int high)
32{
33    if (low < high) {
34        int pivotPos = quick_partition(array, low, high);
35
36        quick_sort_impl(array, low, pivotPos - 1);
37        quick_sort_impl(array, pivotPos + 1, high);
38    }
39}
40
41// 快速排序
42//
43void quick_sort(int* array, int length)
44{
45    assert(array && length >= 0);
46
47    if (length <= 1) {
48        return;
49    }
50
51    quick_sort_impl( array, 0, length - 1);
52}

时间复杂度分析：
最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。此时，时间复杂度为 O(n ^ 2)。

在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：0(nlgn)。

尽管快速排序的最坏时间为 O(n ^ 2)，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为 O(nlgn)。

空间复杂度分析：
快速排序需要一个栈来实现递归。若每次划分较为均匀（也就是对半分，基准值总是中值），则其递归树的高度为O(lgn)，故递归后需栈空间为O(lgn)。最坏情况下，递归树的高度为O(n)，所需的栈空间为O(n)。

补充：
快速排序是非稳定的。例如，对 [5, 5, 1] 进行排序。

对时间复杂度进行分析之后，可以看出，在当前无序区中选取划分的基准关键字是决定算法性能的关键。可以对这个进行一定程度的优化：
第一办法是，取中值，即比较当前无序区间的第一个，中间那个以及最后一个记录的大小，取中间的那个记录作为基准，进行快速排序；
第二个办法是，在当前无需区间中进行随机选取。

测试：
在前文《排序算法之插入排序》测试代码的基础上添加两行代码即可：