交换排序（一）

基本概念

根据待排序列中两个元素的比较结果来交换两个元素的位置，这样的排序称为交换排序，主要包括冒泡排序和快速排序。

冒泡排序（Bubble Sort）

基本思想

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

代码实现

void BubbleSort(int L[], int n)
{
    int i, j, flag;
    // flag变量记录是否发生交换
    for (i = 1; i < n; ++i) // n-1趟
    {
        flag = 0;
        // 第 i 趟时，已有 i-1 个元素沉底，不再次参与排序，
        // 剩余 j-(i-1) 个元素进行 j-(i-1)-1 次比较
        for (j = 1; j < n-i+1; ++j)
        {
            if (L[j] > L[j+1]) // 大值沉底
            {
                swap(&L[j], &L[j+1]);
                flag = 1;
            }
        } // 一趟排序
        if (flag == 0) return; // 若一趟排序未发生交换，说明已经有序，不需再排序
    }
}

归纳分析

稳定排序（stable sort）

当 i > j ，L[i] = L[j] 时，不会交换元素，故冒泡排序是稳定排序。

空间复杂度（in-place 原地算法，O(1)）

交换元素需要 1 个辅助空间，冒泡排序的空间复杂度为 O(1)。

时间复杂度

最好情况下，时间复杂度为 O(n)，此时待排序列有序；

不过仍然需要一趟冒泡进行比较验证，此后 flag=false，直接跳出循环，结束排序，因此，比较次数为 n-1 次，移动次数为 0。

最坏情况下，时间复杂度为 O(n²)，此时待排序列逆序；

需要进行 n-1 趟冒泡，第 i 趟冒泡 n-(i-1) 个元素进行 n-i 次比较，每次比较后需要移动 3 次来交换元素，于是

比较次数为 Σ(n-i)= n(n-1)/2，i = {1,…,n-1}；
移动次数为 Σ3(n-i)= 3n(n-1)/2，i = {1,…,n-1}。

平均情况下，冒泡排序的时间复杂度也为 O(n²)。

初态影响

由3分析可知，复杂度受到初始状态影响。

过程特征

一趟排序可以确定一个元素的最终位置（最值），会产生全局有序的有序子序列。

全局有序：每一趟排序结束后都会有一个元素会落到其最终的位置上，有序子序列中的所有元素一定小于或大于无序子序列中的所有元素（直接插入排序是局部有序）。

适用性

插入排序比较适合用于“基本有序”的序列和“数据量不大（不大于50）”的序列，并且冒泡排序移动操作比较少，所以也适合元素本身信息量较大的情况，但不适合用直接插入排序（移动操作较多）。不过元素本身信息量较大时，为避免大量移动操作，可改用*链表**来存储。

算法证明（来自算法导论）

运用两次循环，先证内循环，再证明外循环。

内循环：在每次循环开始前，A[j]是A[j…n]中最小的元素。

初始：j=n，因此A[n]是A[n…n]的最小元素。
保持：当循环开始时，已知A[j]是A[j…n]的最小元素，将A[j]与A[j-1]比较，并将较小者放在j-1位置，因此能够说明A[j-1]是A[j-1…n]的最小元素，因此循环不变式保持。
终止：j=i，已知A[i]是A[i…n]中最小的元素，证毕。

外循环：在每次循环之前，A[1…i-1]包含了A中最小的i-1个元素，且已排序：A[1]<=A[2]<=…<=A[i-1]。

初始：i=1，因此A[1…0]=空，因此成立。
保持：当循环开始时，已知A[1…i-1]是A中最小的i-1个元素，且A[1]<=A[2]<=…<=A[i-1]，根据内循环不变式，终止时A[i]是A[i…n]中最小的元素，因此A[1…i]包含了A中最小的i个元素，且A[1]<=A[2]<=…<=A[i-1]<=A[i]
终止：i=n+1，已知A[1…n]是A中最小的n个元素，且A[1]<=A[2]<=…<=A[n]，得证。

问题

冒泡排序和插入排序哪个更快？

插入排序中移动的次数直接是逆序对的个数，而冒泡排序中交换的次数是逆序对的个数，由前面的分析可知，一次交换需要移动3次元素，因此冒泡排序执行的时间至少是逆序对的个数，因此插入排序的执行时间至少比冒泡排序快。

算法改进

改进 1．设置一标志性变量 pos，用于记录每趟排序中最后一次进行交换的位置。由于 pos 位置之后的记录均已交换到位，故在进行下一趟排序时只要扫描到 pos 位置即可。

// 代码中数组元素从 L[1] 开始，故用 L[0] 来存储标识位置
void BubbleSort_1(int L[], int n)
{
    int i = n, j; // //初始时，比较的最后位置仍为 n
    while (i > 1) // 仅代表排序趟数，没有其他含义（n-1趟）
    {
        L[0] = 1; // 每趟开始时，无记录交换
        for (j = 1; j < i; ++j) // [1,...,i-1, i]
        {
            if (L[j] > L[j+1])
            {
                swap(&L[j], &L[j+1]);
                L[0] = j; // 保存最后一次发生交换的位置
            }
        } // 一趟排序
        i = L[0]; // 下一次比较到 L[0] 即停止
    }
}

改进 2．传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值，考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

void BubbleSort_2(int L[], int n)
{
    int i, low = 1, high = n; // 设置变量的初始值
    while (low < high)
    {
        for (i = low; i < high; ++i) // 正向冒泡，找到最大者
            if (L[i] > L[i+1])
                swap(&L[i], &L[i+1]);

        --high; // 修改high值，前移一位
        for (i = high; i > low; --i) // 反向冒泡，找到最小者
            if (L[i] < L[i-1])
                swap(&L[i], &L[i-1]);
        ++low; // 修改low值，后移一位
    }
}

快速排序（Quick Sort）

快速排序见交换排序（二）

上篇: 选择排序下篇: 交换排序（二）

基本概念
冒泡排序（Bubble Sort）
快速排序（Quick Sort）