【数据结构】排序之交换排序（冒泡 | 快排）

1. 前言

在之前的博客中介绍了插入排序，有需要的可以点这个链接: link，这次来介绍交换排序，包括冒泡和快排。
话不多说，正文开始。

2. 交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置。

交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

交换排序这里介绍冒泡排序和快速排序，来一起看看。

3. 冒泡排序

动图形象的展示了冒泡排序的过程。

冒泡排序的特性总结：

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定

3.1 分析

交换排序肯定离不开交换，就先写一个Swap。

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}

同样的方法，先实现单趟排序，如果前一个大于后一个就交换，把最大的放在了最后。
得注意把控区间的位置，如果if中的代码是a[i+1]>a[i],那么上面循环的区间就是从0到n-1。

第一趟的位置在n-1，那么第j趟就是n-j。
所以对于总的来排，就在外面套一个循环，也就是：

来看看使用结果

如果说没有给定的数据已经排好序了，就不用经行交换了，就加一个标志bool exchange = false，如果交换了就变为true。

3.2 代码实现

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){bool exchange = false;for (int i = 1; i < n - j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = true;}}if (exchange == false)break;}}

4. 快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。

其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

快速排序有三种实现方法，下面来介绍。

4.1 hoare版本

hoare版本是怎么实现的？
来看看动图：

可以看到这里，先选取了一个关键的值key，

然后右边边开始走，可以发现，当右边找到第一个比key小的值，就停下来。然后走左边，左边找到第一个比key大的值，然后左右两边交换；交换完，又继续。

当左右两边相遇就结束，然后将key与这个位置交换。

为什么要相遇位置比key的值小？
因为是从右边先走，相遇就有两种情况：

1. R遇到L，R没有找到比key小的值，就一直走，直到遇见L，相遇位置是L，比key小。
2. L遇到R，R先走，找到小于key的值就停下,L找大，一直找，没有找到，但是遇见R就停下来，相遇位置就是R找到小的位置，也比key要小。

4.1.1 分析

用keyi来记录交换值的下标。

同样先看单趟排序，在上面已经分析了。
首先右边先走，找小，那么它的代码是

左边找大。

但是走到结尾会发生错误，可能会错位，出现right<left的情况，所以在循环里面多加一个判断。

循环出来后就交换。
要让keyi到它最终的位置，就得用while ( left < right)来走，当走完后，交换key和left。任何继续排下一个数。
这里的keyi将区间分为三部分：[begin,keyi-1],keyi,[keyi+1,end]。
如果左边有序，右边有序，那么整体就有序。

用递归实现，当这个区间只有一个值或者没有值时候，结束。否则就调用左区间和右区间。

实现结果：

4.1.2 hoare版本代码

void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int left = begin, right = end;int keyi = begin;while ( left < right){// 右边找小while (left < right && a[right] >= a[keyi]){--right;}// 左边找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;// [begin, keyi-1] keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}

4.2 挖坑法

看动图展示一下：

把左边位置的值先挖出来，用key先保存起来。形成了第一个坑位。

然后右边先走，找到比key要小的值，然后就把这个值，取出来放到这个坑中。
然后形成了新的坑。

然后左边找大，找到大以后，将它扔到坑中。

直到它们两个相遇就终止了，然后把key填上。

4.2.1 分析

挖坑法没有hoare版的复杂，先找到右边找到小放在坑里，左边找到大的放坑里，在相遇时候把key放进去就行。
为了方便递归，重新写递归部分在，将坑位置的值传进去就行。

举个例子实现一下：

4.2.2 挖坑法代码实现

int PartSort2(int* a, int begin, int end)
{int key = a[begin];int hole = begin;while (begin < end){// 右边找小，填到左边的坑while (begin < end && a[end] >= key){--end;}a[hole] = a[end];hole = end;// 左边找大，填到右边的坑while (begin < end && a[begin] <= key){++begin;}a[hole] = a[begin];hole = begin;}a[hole] = key;return hole;	
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort2(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

4.3 前后指针版本

cur遇到比key大的值，就++cur;
cur遇到比key小的值，就++prev,交换prev和cur位置的值

cur先走

当cur遇到比key小的值，
先加加prev，再与cur交换。

然后cur继续往后走，又遇见比key小的

然后先加加prev，再与cur交换。

cur继续往后找小

cur比end大，就结束，然后将key与prev交换。

4.3.1 分析

先定义一下cur和prev，让int cur = prev + 1，int prev = begin。
当cur比key的值小时就继续走，否则就++prev，然后prev与cur交换。
就直接写一个循环就行，将加加放在条件里面。

当cur出去后，再将key与prev交换。

这里也是先写好单趟，然后调用就行。

举个例子看看：

4.3.2 前后指针版本代码实现

int PartSort3(int* a, int begin, int end)
{int keyi = begin;int prev = begin;int cur = prev + 1;while (cur <= end){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);

有问题请指出，大家一起进步吧！