数据结构：交换排序

交换排序的基本思想是：每趟排序，两两比较待排序记录的关键字，若不满足排序要求就进行交换，直到整个序列有序为止。常用的交换排序算法是冒泡排序和快速排序。

一、冒泡排序

冒泡排序（Bubble Sort）是最简单的交换排序方法，它通过两两比较相邻记录的关键字，如果发生逆序，则进行交换。这样，每趟排序就能使关键字小的记录如气泡一般逐渐往上“漂浮”（左移），或者使关键字大的记录如石块一样逐渐向下“坠落”（右移）。

1.1、算法步骤

冒泡排序算法的步骤为：

设待排序记录存放在数组r[1…n]中。
首先，将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序（即L.r[1].key>L.r[2].key），则交换两个记录。接着，继续比较第二个记录和第三个记录的关键字。依此类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。该过程，称作第一趟冒泡排序，其结果是关键字最大的记录被安置到最后一个位置上。
然后，进行第二趟冒泡排序，对前n-1个记录也进行上述操作，其结果是关键字次大的记录被安置到第n-1个位置上。
重复上述比较和交换过程，第i趟冒泡排序是从L.r[1]到L.r[n-i+1]，依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i+1的位置上。直到在某一趟排序过程中，没有进行过记录交换操作，说明序列已全部达到排序要求，排序完成。

如下图，是对一组关键字序列为 $\{49,38,65,97,76,13,27, \overline{49}\}$ 的待排序记录，进行冒泡排序的过程。待排序记录总共有8个，在第六趟排序过程中没有进行过交换记录的操作，则完成排序。

1.2、算法描述

// 对顺序表L做冒泡排序
void BubbleSort(SqList &L) {
    // m用来标记每趟排序需要进行比较的次数
    m=L.length-1;
    // flag用来标记某一趟排序是否发生交换
    flag=1;

    while( (m>0)&&(flag==1) ) {
        // flag为0，表示本趟排序没有发生交换，则不会执行下一趟排序
        flag=0;

        // 两两比较相邻记录
        for(j=1;j<=m;j++) {
            // 相邻记录逆序，交换两个记录
            if(L.r[j].key>L.r[j+1].key) {
                // flag置为1，表示本趟排序发生了交换 
                flag=1;
                // 交换前后两个记录
                t=L.r[j];
                L.r[j]=L.r[j+1];
                L.r[j+1]=t;
            }
        }

        // 下一趟排序需要进行m-1次比较
        --m;
    }
}

1.3、算法分析

从时间上来看，最好情况（初始序列为正序），只需进行一趟排序，在排序过程中进行n−1次关键字间的比较，且不移动记录。最坏情况（初始序列为逆序），需进行n−1趟排序，总的关键字比较次数KCN和记录移动次数RMN（每次交换都要移动3次记录）分别为

KCN= \sum_{i=n}^{2} (i-1) = \frac{n(n-1)}{2} \approx \frac{n^2}{2}

RMN= 3 \sum_{i=n}^{2} (i-1) = \frac{3n(n-1)}{2} \approx \frac{3n^2}{2}

所以，冒泡排序在平均情况下，关键字比较次数和记录移动次数分别约为 $\frac{n^2}{4}$ 和 $\frac{3n^2}{4}$ ，即时间复杂度为 $O(n^2)$ 。

从空间上来看，冒泡排序在交换两个记录的位置时需要一个辅助空间用于暂存记录，所以空间复杂度为O(1)。

1.4、算法特点

冒泡排序算法的特点为：

稳定排序。
可用于链式存储结构。
移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时，此算法不宜采用。

二、快速排序

快速排序（Quick Sort）是对冒泡排序的改进。在冒泡排序中，只对相邻的两个记录进行比较，因此每趟排序只能消除一个逆序。如果能通过两个（不相邻）记录的一次交换，消除多个逆序，则排序速度会大大加快。在快速排序中，一次交换可能消除多个逆序。

2.1、算法步骤

快速排序算法的步骤为：

在待排序的n个记录中任取一个记录（通常取第一个记录）作为支点（也称为枢轴），并设其关键字为pivotkey。
执行一趟排序，把所有关键字小于pivotkey的记录交换到支点前面，把所有关键字大于pivotkey的记录交换到支点后面，支点则放置在分界处的位置。这样，经过一趟排序后，就能以支点为分界点，将待排序记录分成左、右两个子表。
分别对左、右子表重复上述过程，直到每个子表中只有一个记录时，排序完成。

其中，一趟排序的具体步骤如下：

选择待排序表中的第一个记录作为支点，并将其暂存在r[0]的位置上。附设两个指针low和high，初始时分别指向表的下界和上界（第一趟排序时，low=1，high=L.length）。
从表的最右侧位置依次向左搜索，找到第一个关键字小于支点关键字pivotkey的记录，将其移到low处。具体操作是：当low<high时，若high所指记录的关键字大于等于pivotkey，则向左移动指针high（即执行操作–high）；否则将high所指记录与支点记录交换（即将high所指记录移动low处）。
从表的最左侧位置，依次向右搜索找到第一个关键字大于pivotkey的记录，将其移到high处。具体操作是：当low<high时，若low所指记录的关键字小于等于pivotkey，则向右移动指针low（即执行操作++low）；否则将low所指记录和支点记录交换（即将low所指记录移动high处）。
重复第二步和第三步，直到low与high相等，此时一趟排序完成，low或high的位置即为支点在此趟排序中的最终位置，原表被分成左、右两个子表。

交换两个记录，一般需要移动3次。在上述过程中，记录交换都是与支点进行，如果先将支点记录暂存在r[0]位置上，那么交换时只移动要与支点进行交换的记录。也就是，只做r[low]或r[high]的单向移动，直到每趟排序结束后再将支点记录移至正确位置上。

如下图，是对一组关键字序列为 $\{49,38,65,97,76,13,27, \overline{49}\}$ 的待排序记录，进行快速排序的过程。

2.2、算法描述

// 对顺序表L中的子表L.r[low..high]执行一趟排序，返回支点位置
int Partition(SqList &L, int low, int high) {
    // 用子表的第一个记录做支点记录，并将其暂存到r[0]中
    L.r[0]=L.r[low];
    // 将支点记录的关键字保存在pivotkey中
    pivotkey=L.r[low].key;

    // 从子表的两端交替地向中间扫描
    while(low<high) {
        while(low<high&&L.r[high].key>=pivotkey) --high;
        // 将关键字小于pivotkey的记录移到low处
        L.r[low]=L.r[high];
        while(low<high&&L.r[low].key<=pivotkey) ++low;
        // 将关键字大于pivotkey的记录移到high处
        L.r[high]=L.r[low];
    }
    // 将支点记录放置的正确位置
    L.[low]=L.r[0];

    // 返回支点位置
    return low;
}


// 对顺序表L中的子表L.r[low..high]进行快速排序
void QSort(SqList &L, int low, int high) {
    // 表的长度大于1
    if(low<high) {
        // 将L.r[low..high]一分为二，pivotloc是支点位置
        pivotloc=Partition(L, low, high);
        // 对左子表进行快速排序
        Qsort(L, low, pivotloc-1);
        // 对右子表进行快速排序
        Qsort(L, pivotloc+1, high);
    }
}

// 对顺序表L进行快速排序
void QuickSort(SqList &L) {
    QSort(L, 1, L.length);
}