数据结构第八章（二）-交换排序

交换排序

什么是“交换排序”？人如其名，就是根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置

换就vans了。

一、冒泡排序

冒泡排序，也是人如其名，像冒泡泡一样，本来是大小顺序不一的泡泡，一点一点往上浮，变成大小顺序一致的泡泡。

什么意思呢？就是从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换它们，直到序列比较完，我们称这样的过程为“一趟”冒泡排序。

1.算法过程

举个栗子，我们的初始顺序表如下，我们要把它变成从小到大排序：

现在我们来进行第1趟冒泡排序

从最后开始，依次往前两两比较，我们要的是从小到大排序，所以前>后就交换。

我们现在比的是“27”和“49”:

27<49，所以不用换。

现在比“13”和“27”

13<27，所以不用换。

现在比“76”和“13”

76>13，所以要“交换”，即：

现在比“13”和“97”

97>13，所以要“交换”：

现在比“65”和“13”

65>13，所以要“交换”：

现在比“38”和“13”

38>13，所以要“交换”：

现在比“49”和“13”

49>13，所以要“交换”：

我们第1趟就结束了。

其实我们可以发现，第一趟排序使关键值最小的一个元素“冒”到最前面了，这是因为两两比较，最小的那个和谁比都最小，所以就会到它应该去的位置。

那我们来进行第2趟

从最后开始，依次往前两两比较，我们要的是从小到大排序，所以前>后就交换，前面已经确定最终位置的元素不用再对比。

我们现在比的是“27”和“49”:

27<49，所以不用换。

现在比“76”和“27”

76>27，所以要“交换”：

现在比“97”和“27”

76>27，所以要“交换”：

现在比“65”和“27”

65>27，所以要“交换”：

现在比“38”和“27”

38>27，所以要“交换”：

现在比“49”和“27”

49>27，所以要“交换”：

我们第2趟就结束了。

其实我们可以发现，第二趟排序结束后，最小的两个元素会“冒”到最前面。

………………

以此类推，前面已经确定最终位置的元素不用再对比，这样一趟一趟对比，就可以得到我们想要的排序结果。

但是，若某一趟排序没有发生“交换”，则说明此时已经整体有序

因为但凡有一个乱序的，都得交换一下，否则这一趟就白走了。

我们最终的结果：

可以看出它是稳定的。

话不多说，上代码：

//交换
void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

//冒泡排序
void BubbleSort(int A[],int n){
    for(int i = 0;i < n-1; i++){
        bool flag = false;          //表示本趟冒泡排序是否发生交换的标志
        
        for(int j = n-1;j > i;j--){ //一趟冒泡排序
            
            if(A[j-1] > A[j]){      //若为逆序
                swap(A[j-1], A[j]); //交换
                
                flag = true;
            }
        }
        
        if(flag == false){
            return;                 //本趟遍历后没有发生交换，说明表已经有序
        }
    }
}

其实走完上面的路程，看这个也很清晰了。需要注意的就是有一个flag可以防止让它一直进行无意义的遍历，因为某一趟排序没有发生“交换”，则说明此时已经整体有序了嘛。

还有这个 i>n-1 ，是指在 i 所指位置之前的元素都已经有序，所以前面的就不用管了。

而且我们只有 A[j-1] > A[j] 的时候才发生交换，所以通过代码也能很明显看出它是稳定的。

2.性能

空间复杂度不用说了，显然是O(1)。

那么时间复杂度我们的最好情况是什么？

那不就是一开始就有序，此时比较次数是 n-1 ，交换次数为 0 ，所以最好的时间复杂度为 O(n)。

那么最坏呢？最坏就是全部逆序，这样的话每一趟都得把一个冒过去，一共要比较的次数就是 (n-1) + (n-2) + ……+ 1 = n(n-1)/2，这也是需要交换的次数（比较一次交换一次），所以最坏时间复杂度为O(n²)。

故平均时间复杂度为O(n²)。

当然我们这里说的交换是指换元素不是指移动元素，只是指执行一次swap。如果要是移动元素的话那我们每执行一次swap函数里面就需要移动元素3次，所以具体交换指什么还是要看情况。

如果冒泡排序用于链表，那我们可以从前往后“冒泡”（因为这样比较好交换），每一趟将更大的元素“冒”到链尾就可以了。

再提一句，冒泡排序是稳定的哈

二、快速排序

有没有发现这个排序的名字起得就很自信，直接就叫快速排序。这个排序算法很重要哈，非常重要。

算法思想：

在待排序表 L[1……n] 中任取一个元素 pivot 作为枢轴（或基准，通常取首元素），通过一趟排序将待排序表划分为独立的两部分 L[1……k] 和 L[k+1……n]，使得 L[1……k] 中的所有元素小于 pivot，L[k+1……n] 中的所有元素大于等于 pivot，则 pivot 放在了其最终位置 L(k) 上，这个过程称为一次“划分”。

然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

1.算法过程

还是用栗子来表述，我们的初始顺序表如下，我们要把它变成从小到大排序：

第1个piviot

我们现在以第一个元素“49”为基准，把更小的元素都交换到左边，更大的元素都交换到右边（其实等于的不论在哪边，不用动接着扫就可以了）

我们有两个指针：low，high，这两个指针指向的是开头和结尾下标（0，7）。

我又有一点想说的（弱弱），我们为什么要弄这个 low high？首先我们的目的是什么？
目的是把比基准小的放左边，把大于基准的放右边吧？

那么我们这个 low high 其实就相当于一个扫描器，说白了就是 high 往左边扫描，遇见比基准更小的了，这不对啊见比基准更小的应该放在左边，然后和 low 指的元素交换，接着 low 往右边扫描，遇见大于基准的了，再和 high 指的元素换，完了 high 往左边接着扫……说白了，就是谁扫到了不符合标准就换，换了就接着另一个扫，俩指针都是往中间移的，直到 low==high 为止，这就是基准应该待的地方。

好了回到正题，现在我们把基准拎出来：

49

先看 high 。我们 high 指向的是“49”，和基准一样

再接着往左边扫，发现“27”不对了，27<49，应该放到基准左边才是，我 high 所到之处都得是比基准大的才对，所以把 high 指向的元素 换到 low 指向的里面，也就是：

好了换了，刚刚说的什么？换了就接着另一个扫是吧，所以现在 low 开始扫了。

low 指向的元素是“27”，27<49，没毛病。再接着往右边扫，38<49，也没毛病。再扫，发现“65”不对了

65>49，应该放到基准右边才是，我 low 所到之处都得是比基准小的才对，所以把 low 指向的元素 换到 high 指向的里面，也就是：

好了换了，换了就接着另一个扫，所以现在 high 开始扫了。

high 指向的元素是“65”，65>49，没毛病。再接着往左边扫，发现“13”不对了

13<49，应该放到基准左边才是，我 high 所到之处都得是比基准大的才对，所以把 high 指向的元素 换到 low 指向的里面，也就是：

好了换了，换了就接着另一个扫，所以现在 low 又开始扫了。

low 指向的元素是“13”，13<49，没毛病。再接着往右边扫，发现“97”不对了

97>49，应该放到基准右边才是，我 low 所到之处都得是比基准小的才对，所以把 low 指向的元素 换到 high 指向的里面，也就是：

好了换了，换了就接着另一个扫，所以现在 high 开始扫了。

high 指向的元素是“97”，97>49，没毛病。再接着往左边扫，76>49，也没毛病。再往左，你会发现什么？

low == high， low 和 high 碰头了，也就是 low 不再小于high 了，这说明我们 pivot 放的位置找到了，xxx，就是现在！

我们的目的是用第一个元素把待排序序列“划分”为两个部分，做变更小，右边更大。现在该元素的最终位置已确定：

我们就可以以基准为分界线，分别再对左半部分和右半部分进行一次这样的操作。

第2个piviot

“49”的左半部分：

我们的两个指针 low，high 指向的仍然是开头和结尾下标（0，2）。

现在我们把基准拎出来：

27

先看 high 。我们 high 指向的是“13”，

13<27，应该放到基准左边才是，我 high 所到之处都得是比基准大的才对，所以把 high 指向的元素 换到 low 指向的里面，也就是：

好了换了，换了就接着另一个扫，所以现在 low 又开始扫了。

low 指向的元素是“13”，13<27，没毛病。再接着往右边扫，发现“38”不对了

38>27，应该放到基准右边才是，我 low 所到之处都得是比基准小的才对，所以把 low 指向的元素 换到 high 指向的里面，也就是：

high 指向的元素是“38”，38>27，没毛病。再接着往左边扫，我们又会发现low == high， low 和 high 碰头了，这说明我们 pivot 放的位置找到了

现在该元素的最终位置已确定，可以放了：

如果我们再以基准（27）为分界线，分别再对左半部分和右半部分进行一次这样的操作，就会发现，其实我们左、右两边已经分别只有一个元素了，所以之前的基准（49）左边的其实都已经排好序了。

第3个piviot

“49”的右半部分：

我们的两个指针 low，high 指向的仍然是开头和结尾下标（4，7）。

现在我们把基准拎出来：

76

先看 high 。我们 high 指向的是“49”，

49<76，应该放到基准左边才是，我 high 所到之处都得是比基准大的才对，所以把 high 指向的元素 换到 low 指向的里面，也就是：

好了换了，换了就接着另一个扫，所以现在 low 又开始扫了。

low 指向的元素是“49”，49<76，没毛病。再接着往右边扫，发现“97”不对了

97>76，应该放到基准右边才是，我 low 所到之处都得是比基准小的才对，所以把 low 指向的元素 换到 high 指向的里面，也就是：

好了换了，换了就接着另一个扫，所以现在 high 开始扫了。

high 指向的元素是“97”，97>76 ，没毛病。再接着往左边扫，发现“65”不对了

65<76，应该放到基准左边才是，我 high 所到之处都得是比基准大的才对，所以把 high 指向的元素 换到 low 指向的里面，也就是：

好了换了，换了就接着另一个扫，所以现在 low 又开始扫了。

low 指向的元素是“65”，65<76，没毛病。再接着往右边扫，我们又会发现low == high， low 和 high 碰头了，这说明我们 pivot 放的位置找到了

现在该元素的最终位置已确定，可以放了：

如果我们再以基准（76）为分界线，分别再对左半部分和右半部分进行一次这样的操作，就会发现，其实我们右边已经只有一个元素了，所以只要对基准（76）左边再进行一次这样的操作就可以了：

第4个piviot

“76”的左半部分：

我们的两个指针 low，high 指向的仍然是开头和结尾下标（4，5）。

现在我们把基准拎出来：

49

先看 high 。我们 high 指向的是“65”，65>49，没毛病。再接着往左边扫，发现low == high， low 和 high 碰头了，这说明我们 pivot 放的位置找到了

现在该元素的最终位置已确定，可以放了：

终于，我们这个顺序表的快速排序完成了。

来看看代码，理解了上面的过程代码就更加清晰，我们用递归实现：

//用第一个元素将待排序序列划分成左右两个部分
int Partition(int A[], int low, int high){
    int pivot = A[low];             //第一个元素作为枢轴
    
    while(low < high){              //用low、high搜索枢轴的最终位置
        
        while(low < high && A[high] >= pivot){
            high-- ;
        }
        A[low] = A[high];           //比枢轴小的元素移动到左端
        
        while(low < high && A[low] <= pivot){
            low++;
        }
        A[high] = A[low];           //比枢轴大的元素移动到右端
    }
    
    A[low] = pivot;                 //枢轴元素存放到最终位置
    
    return low;                     //返回存放枢轴的最终位置
}

//快速排序
void quickSort(int A[], int low, int high){
    if(low < high){ //递归跳出的条件
        
        int pivotPos = Partition(A, low , high); //划分
        
        quickSort(A, low, pivotPos-1);           //划分左子表
        
        quickSort(A, pivotPos+1, high);          //划分右子表
    }
    return;
}

要注意的就是我们 Partition 的大前提是 low<high，我们 quickSort 递归的大前提也是 low<high，只有这样才能进行下去，否则就跳出递归或排好序了。还有就是我们相等的是不移动的哈，这个在Partition 里面也很明显了。

2.性能

显然快排的空间消耗主要是在递归工作栈里，所以空间复杂度其实就是栈的深度O(栈深)。

我们把每一层的 quickSort 处理都展示出来，就是下面这个样子，绿色是每一次 quickSort 排好序的元素：

其实我们可以看出，每一层的 quickSort 只需要处理剩余的待排序元素，时间复杂度是不超过O(n)的（要处理的肯定比顺序表的总个数少）

而它一共有多少层呢？它的层数其实也就是递归的深度，所以时间复杂度=O(n * 递归深度)。

所以我们的时间复杂度、空间复杂度都和栈的深度有关系，这个“栈的深度”就是我们计算性能的关键。

我们把每一层排好序的元素当成一个结点，把 n 个元素组织成二叉树，就可以生成这样一棵树，二叉树的层数就是递归调用的层数：

n 个结点的二叉树的最小高度是 ⌊log₂n⌋ + 1，最大高度是 n，所以

时间复杂度：

最好时间复杂度为O(n²)
最坏时间复杂度为O(nlog₂n)

空间复杂度：

最好空间复杂度为O(n)
最坏空间复杂度为O(log₂n)

比较好的情况是什么呢？就是这个树的高度小，也就是每一次选中的“枢轴”将待排序序列划分为均匀的两个部分，这样递归深度是最小的，算法效率也是最高的。

最坏的情况也就是每一次选中的“枢轴”将待排序序列划分为很不均匀地两个部分，这样会导致递归深度增加(n层)，算法效率变低。

所以由此我们可以知道，如果初始序列有序或逆序，则快速排序的性能最差（因为每次选择的都是靠边的元素）。

那么我们怎么优化呢？也就是尽量让它平均，即

尽量选择可以把数据中分的枢轴元素，比如选头、中、尾巴三个位置的元素，取中间值作为枢轴元素啊，或者随机选一个元素作为枢轴元素等等。

我们快速排序的平均时间复杂度是O(nlog₂n)，看起来也不是很低，但是不可否认的是，我们的快速排序徐是所有内部排序算法中平均性能最优的排序算法。

那么快排稳定吗？

来举个栗子，简单说说不弄表格了。比如我们现在有三个元素 2 2 1，即 2(1)， 2(2)，1

把第一个“2”作为基准，还是先把基准拎出来，low是0，high是1。

先看 high 。我们 high 指向的是“1”，

1<2，应该放到基准左边才是，我 high 所到之处都得是比基准大的才对，所以把 high 指向的元素 换到 low 指向的里面，也就是：

1 2(2) 空

那么我们换了就接着另一个扫，所以现在 low 又开始扫了。

low 指向的元素是“2”，等于的不用动，所以 low 继续向前扫。这时我们发现 low==high，两个碰头，所以把拎出来的放进去，也就是 1，2(2)， 2(1)

所以快排是不稳定的。

但是还有一个要注意的点就是，书上把每一层称为一趟，有的书是把一个基准找到位置称为一趟，我们以考试为主，每一层称为一趟即可。

总结

冒泡排序是稳定的，快速排序是不稳定的。上一篇我们学的插入排序是稳定的，希尔排序是不稳定的。

冒泡排序要注意的就是某一趟排序没有发生“交换”，则说明此时已经整体有序了，就不用再往下了，这个在代码中也有体现；

快排主要就是low、high两个指针，我上面也说了一下， low high 其实就相当于一个扫描器，说白了就是 high 往左边扫描，遇见比基准更小的了，这不对啊见比基准更小的应该放在左边，然后和 low 指的元素交换，接着 low 往右边扫描，遇见大于基准的了，再和 high 指的元素换，完了 high 往左边接着扫……说白了，就是谁扫到了不符合标准就换，换了就接着另一个扫，俩指针都是往中间移的，直到 low==high 为止，这就是基准应该待的地方，了解过程就会写代码了。

快排代码里面要注意的就是我们 Partition 的大前提是 low<high，我们 quickSort 递归的大前提也是 low<high，只有这样才能进行下去，否则就跳出递归或排好序了。还有就是我们相等的是不移动的，把这些别遗漏，就差不多了。

再说一遍，快排是重要的，代码也重要。