交换排序详解——冒泡排序+快速排序

交换排序

基本思想：

所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动（升序），降序则相反。

4.1 冒泡排序

算法思想

冒泡排序大家应该都比较熟悉，思想也很简单：

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。 那相邻两个数据进行比较，如果有N个数，第一趟我们应该比较N-1次： 经过第一趟，最大值已经在最后一个位置了（升序），那第二趟我们就不用管最后一个数了，所以第二趟比较N-2次，第三趟比较N-3次......， 一趟搞定一个数，当只剩最后一个数时就有序了，总共N-1趟。

代码实现

//冒泡排序
void SelectSort(int* arr, int n)
{
    int i = 0;
    for (i = 0; i < n - 1; i++)
    {
        int j = 0;
        for (j = 0; j < n - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

我们测试一下： 🆗，没问题，不过我们还可以对它进行一下优化：

怎么优化呢？ 每趟过后，我们都可以判断一下是否已经有序了，如果已经有序了，就不再继续循环比较了。

//冒泡排序
void BubbleSort(int* arr, int n)
{
    int i = 0;
    for (i = 0; i < n - 1; i++)
    {
        int j = 0;
        int flag = 0;
        for (j = 0; j < n - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(&arr[j], &arr[j + 1]);
                flag = 1;
            }
        }
        // 一趟冒泡过程中，没有发生交换，说明已经有序了，不需要再处理
        if (flag == 0)
            break;
    }
}

🆗，那冒泡排序就完成了。

冒泡排序特性总结

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度：O(N^2) 

3. 空间复杂度：O(1)

4. 稳定性：稳定

那接着我们来看另一种交换排序——快速排序。

4.2 快速排序（递归）

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。 其基本思想为：取待排序元素序列中的某元素作为基准值（一般取第一个或最后一个元素），按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值（升序），然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

那么，将区间按照基准值划分为左右两半部分（即一趟快排）的常见方式有：

1. hoare版本

思路讲解

怎么划分呢？ 对应着图，再给大家简单解释一下：

上图选择最右边的元素（即第一个，一般选第一个或最后一个）作为基准值Key，两个“指针”L和R分别指向最左边和最右边，R先出发向左找比Key小的值，找到就停下，然后L开始向右找大于Key的值，找到就停下，然后交换L和R位置的元素，接着重复上述操作，当L和R相遇时，再将Key对应的值与相遇位置的值交换，这时Key的左边都是比它小的值，右边都是比它大的值。 这就是一趟的过程。

对于上面的动图：

L和R在值为3处相遇，正好小于Key的值，所以和Key交换后左边都是小的，右边都是大的。 那如果相遇位置的值比Key大呢，这样的话交换之后是不是就不对了啊：

那我们现在提出一个问题：如何确保相遇位置的值比Key小？

🆗，其实很简单，这里是左边第一个做Key，我们只需要让R先走就能保证了。 R先走，相遇的情况其实只有两种：

1. R停止，L在向右找大的过程中相遇。 此时相遇点是R停止的位置，一定是小于Key的。

2. L停止，R在向左找小的过程中相遇。 此时相遇的位置是L停止的位置，虽然L是在值大于Key的位置停止，但是在R出发之前 R位置的大值已经和L位置的小值进行了交换，所以当L、R相遇时相遇位置的值还是小于Key的。

那么同理，如果我们选择右边的第一个值（最后一个）作为Key，就应该让L先走。 这时是需要大家注意的一点。

那一趟排序能达到一个什么样的目的呢？

1. 当前的Key对应的值已经处在了最终正确的位置 🆗，这样一趟过后，当前的Key对应的值是不是就已经处在了最终的位置了，是吧，因为此时它左边的值都是比它小的，右边的值都是比它大的。

2. 以Key为分割线，分割出两个子区间。 那如果再将这两个子区间变有序，是不是整体就有序了。 那如何对子区间进行排序，是不是就是与原问题类似的规模较小的子问题啊，那就可以递归了。

代码实现

上面讲清楚了一趟快速排序的过程，那我们就先实现一下一趟的代码：

//一趟快速排序 [left,right]
int PartSort(int* arr, int left, int right)
{
    int keyi = left;
    while (left < right)
    {
        //R先走，向左找小
        while (left < right && arr[right] >= arr[keyi])
        {
            right--;
        }
        //L向右找大
        while (left < right && arr[left] <= arr[keyi])
        {
            left++;
        }
        if (left < right)
            swap(&arr[left], &arr[right]);
    }
    int meeti = left;
    swap(&arr[meeti], arr[keyi]);
    return meeti;
}

这里我们返回一下相遇位置的下标，该位置两侧的数据就是被分割的两个子区间。

那一趟的搞定了，接下来我们就能写完整的快速排序的代码了：

//快速排序
void QuickSort(int* arr, int begin, int end)
{
    if (begin >= end)
        return;
    int keyi = PartSort(arr, begin, end);
    //[begin,keyi-1] keyi [keyi+1,end]
    
    //排keyi左边
    QuickSort(arr, begin, keyi - 1);
    //排keyi右边
    QuickSort(arr, keyi + 1, end);
}

其实就是先对整体进行一趟快排，然后再去排分隔的左右两个区间。 在上面一开始快速排序的概念我们就提到，快速排序一种二叉树结构的交换排序方法，现在我们再看上面的代码会发现快速排序递归实现的主框架，与二叉树前序遍历规则非常像。 大家也可以自己画一下递归展开图帮助自己理解。

代码写好了，我们测试一下： 没毛病。

优化1：三数取中法选key

但是呢？

我们刚才这种固定选Key的方法（选第一个或最后一个元素），如果去排原本已经有序或者接近有序的数据，效率其实反而会变的比较慢。 为什么呢？ 首先比较理想的状态，即我们的数据是比较随机的情况下，我们选取第一个或最后一个数作为Key值，最后交换之后Key可能正好处在比较中间的位置，正好从中间把数据分成两个部分，然后然后再去递归排两个子区间。 这种情况下效率其实还是很好的： 一趟排序，那就从两头向中间进行遍历再加几次交换，时间复杂度差不多是O(N)，虽然每层递归排的数据一直在减少，但N比较大的时候，后面减的就可以忽略，那总层数其实就是一棵二叉树的高度log2N。 所以这种情况下时间复杂度可以认为是O(N*log2N)

而在有序或接近有序的情况下：

我们还选择两边的数据作为Key的话，这样会导致递归的深度或者说层次会变的多很多，那这种情况下，不仅效率会变慢，而且很容易可能就出现栈溢出了。 在VS上Debug版本下10000个数据，有序的情况下就溢出了，当然调到release版本下会好一点。

所以，我们要考虑进行一个优化：

怎么优化呢？ 🆗，那既然固定选择Key不太好，那我们就改变一下选Key的方法。 针对如何去选K，也有人提出了好几个方法，其中比较优的一种是这样的，我们把它叫做三数取中： 如何选Key呢，对一组待排序的数据，我们从第一个数，中间位置的数和最后一个数中选取中间值（即值的大小处在中间的那个数）。

接下来我们就写一个函数，返回这三个数的中间值的下标：

//三数取中
int GetMidIndex(int* arr, int left, int right)
{
    //int mid = (left + right) / 2;
    
    //防止left和right太大溢出
    int mid = left + (right - left) / 2;
    if (arr[mid] > arr[left])
    {
        if (arr[right] > arr[mid])
            return mid;
        else if (arr[left] > arr[right])
            return left;
        else
            return right;
    }
    //arr[mid] < arr[left]
    else    
    {
        if (arr[right] < arr[mid])
            return mid;
        else if (arr[left] > arr[right])
            return right;
        else
            return left;
    }
}

那我们的一趟快排Part Sort也应该修改一下：

//一趟快速排序 [left,right]
int PartSort(int* arr, int left, int right)
{
    int mid = GetMidIndex(arr, left, right);
    swap(&arr[mid], &arr[left]);
    int keyi = left;
    while (left < right)
    {
        //R先走，向左找小
        while (left < right && arr[right] >= arr[keyi])
        {
            right--;
        }
        //L向右找大
        while (left < right && arr[left] <= arr[keyi])
        {
            left++;
        }
        if (left < right)
            swap(&arr[left], &arr[right]);
    }
    int meeti = left;
    swap(&arr[meeti], &arr[keyi]);
    return meeti;
}

🆗，这样优化之后，我们的快排就能应对各种情况了，即使待排数据是有序的或接近有序，且数量比较大，也不会导致递归层次特别深，现在我们的程序就不会像上面那样轻易的就栈溢出了。

优化2：小区间优化

快速排序在上面的基础上呢，其实还可以再做一些小优化：

通过之前的学习，我们知道，一趟快排的作用其实就是让一个数能够去到它最终的位置，那如果待排区间比较小或者说待排数据比较少的时候（比如10个左右的时候），如果我们还像上面那样递归去排，递归一次建立一个栈帧。只排10几个数我们也需要递归调用好多次去搞定。 所以，我们可以再做一点小优化，就是在待排区间比较小的时候，我们可以直接用一个直接插入排序（相比与其它排序比较好一点）去单独排一下这几个数，从而达到一个优化的效果 与全部数据都用快排的方式相比。

那我们直接对前面写好的快排进行一些修改就行了：

//快速排序[begin,end]
void QuickSort(int* arr, int begin, int end)
{
    if (begin >= end)
        return;
    if (end - begin + 1 < 8)
    {
        // 小区间用直接插入排序，减少递归调用次数
        SInsertSort(arr + begin, end - begin + 1);
    }
    else
    {
        int keyi = PartSort(arr, begin, end);
        //[begin,keyi-1] keyi [keyi+1,end]
​
        //排keyi左边
        QuickSort(arr, begin, keyi - 1);
        //排keyi右边
        QuickSort(arr, keyi + 1, end);
    }
}

至于这个区间的大小，我们一般选的大小是在10左右，这里我们选了8。

这样我们快排的效率会更快一点点。

2. 挖坑法

我们上面提到将区间按照基准值划分为左右两半部分有好几种方法

上面我们讲的hoare版本是第一种，接下来我们再来看一种在hoare的基础上优化的版本——挖坑法。

思路讲解

挖坑法的思想是这样的：

首先选取一个位置作为初始的坑位（一般取第一个或最后一个），上面动图中还是选取最右边第一个作为坑位，先定义一个变量Key保存一下该坑位的值，然后还是两个“指针”L和R分别指向首尾，让R先走向左寻找比Key小的值，找到停下，把该位置的值填到坑的位置，然后让该位置成为新的坑，接着让L开始向右找大于Key的值，找到停下，将其放入坑中，再让该位置成为新的坑，依次循环往复，直到L和R相遇停止，然后把Key填到相遇的位置。 那这种方法呢，就会好一点，不像上面hoare版本需要注意那么多细节，比如要确保相遇位置的值一定要比Key大或比Key小。

代码实现

理清了思路，我们来实现一下：

//一趟快速排序 [left,right]（挖坑法）
int PartSort2(int* arr, int left, int right)
{
    int mid = GetMidIndex(arr, left, right);
    swap(&arr[mid], &arr[left]);
    
    int key = arr[left];
    //变量pit标识坑的位置
    int pit = left;
    while (left < right)
    {
        //R向左找小于Key的值
        if (left < right && arr[right] >= key)
        {
            right--;
        }
        arr[pit] = arr[right];
        pit = right;//更新坑
​
        //L向右找大于Key的值
        if (left < right && arr[left] <= key)
        {
            left++;
        }
        arr[pit] = arr[left];
        pit = left;//更新坑
    }
​
    arr[pit] = key;
    return pit;
}

那我们来测试一下，替换一下之前代码里hoare版本的一趟快排就行了： 这里换成Part Sort2就行了： 也是没问题的。

3. 前后指针法

接下来我们再来学习将区间按照基准值划分为左右两半部分的第3种方法——前后指针法：

思路讲解

对照着图，再给大家解释一下：

还是选取第一个数作为基准值Key，然后有两个“指针” ，初始时，prev指向第一个元素，cur指向第二个： 然后判断cur指向的值是否小于Key对应的值，如果小，就让prev++，然后交换Prev和cur 位置的值（当然这种prev++之后和cur处在同一位置的情况交不交换都一样），再让cur++： 然后再次判断，如果cur指向的值是否小于Key对应的值，如果小，就让prev++，然后交换Prev和cur 位置的值，再让cur++： 然后继续判断，当cur指向的数大于Key时，只让cur++，prev不动。 cur继续走，直到再次遇到小于Key的值，停下，然后让prev++，交换Prev和cur 位置的值，再让cur++ 然后继续往后走，比大小进行相应操作，当cur与所有数据比完停止，交换prev和Key对应的值。

代码实现

思路理清，我们来实现一下代码：

//一趟快速排序 [left,right]（前后指针法）
int PartSort3(int* arr, int left, int right)
{
    int mid = GetMidIndex(arr, left, right);
    swap(&arr[mid], &arr[left]);
​
    int keyi = left;
    int prev = keyi;
    int cur = keyi + 1;
    while (cur <= right)
    {
        /*if (arr[cur] < arr[keyi])
        {
            prev++;
            swap(&arr[prev], &arr[cur]);
        }*/
        //或
        if (arr[cur] < arr[keyi] && ++prev != cur)
            swap(&arr[prev], &arr[cur]);
    
        cur++;
    }
    swap(&arr[prev], &arr[keyi]);
    return prev;
}

🆗，那我们先走把PartSort3替换到快排中再测试一下： 没问题。

4.3 快速排序（非递归）

我们上面学习了递归实现快速排序算法，虽然经过我们的不断改进，我们的快排在大多数情况下一般都不会再出现递归层次太深导致栈溢出了。 但是，不排除在某些极端情况下可能还是会溢出，因为栈区的空间毕竟还是没有特别大。

所以，我们接下来再来学习快排的非递归实现：

快排的非递归需要我们借助栈这种数据结构来实现，栈我们之前也已经学习过了，我们的栈使用的空间是在堆上开辟的，与栈区相比，堆区的空间就比较大了。一般不会出现什么问题。

思路讲解

那非递归实现的思路是什么呢？

大家思考一下，我们上面使用递归来实现快排，每次递归调用的区别是什么？ 🆗，我们上面对一个数组进行排序的时候，每次递归传的数组是不是都是同一个，唯一不同的地方在哪，是不是就是每次传的区间不一样啊： 每一个不同的区间，我们都是先对整体进行划分，然后然处理它的左右两个子区间。 那我们现在非递归去实现，其实还是模拟递归的这个过程，上面提到要使用栈，其实栈的作用就是帮助我们去控制这个区间的。

那具体怎么做呢？接下来我们一起来走一遍：

首先，初始化一个栈，先把我们要排序数据的整个大区间的左右端点入栈： 然后，我们需要一个循环来模拟整个递归的过程，循环结束条件我们先不管。 进入循环，首先我们要进行第一次快排，原数据的区间端点我们已经存进栈里了，就可以直接拿到（拿出保存后我们从栈中删掉），进行第一趟排序了： 那我们现在拿到第一趟之后的基准值Keyi了，Keyi现在将整个区间分成两个子区间，那我们通过Keyi就可以拿到这两个子区间的端点值了，拿到之后，我们再将这些端点值存到栈里。 🆗，那到这里相信大家就猜出循环结束的条件了——只要栈不为空，就继续，说明此时还有未被排完的子区间，栈为空时，就排完了，结束循环。 当然每次划分出来的区间并不一定都是有效的，区间里的数据个数大于1个，才需要再排，所以我们可以加一个判断：

🆗，那我们非递归的快排就写完了，给大家展示一下完整代码：

代码实现

//快速排序（非递归）
void QuickSortNonR(int* arr, int begin, int end)
{
    ST st;
    StackInit(&st);
​
    StackPush(&st, begin);
    StackPush(&st, end);
    while (!StackEmpty(&st))
    {
        //栈是先进后出，我们取到的顺序是先右后左
        int right = StackTop(&st);
        StackPop(&st);
​
        int left = StackTop(&st);
        StackPop(&st);
​
        int keyi = PartSort3(arr, left, right);
        //[left,keyi-1] keyi [keyi+1,right]
​
        if (right > keyi + 1)
        {
            StackPush(&st, keyi + 1);
            StackPush(&st, right);
        }
        if (keyi - 1 > left)
        {
            StackPush(&st, left);
            StackPush(&st, keyi - 1);
        }
    }
    StackDestroy(&st);
}

那再来测试一下非递归： 没什么问题的。

快速排序特性总结

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(logN)

4. 稳定性：不稳定