［数据结构］冒泡排序、快速排序
文章目录
- 交换排序
- 冒泡排序
- 快速排序
- hoare版本
- 挖坑法
- 前后指针法
- 快速排序的优化
- 三数取中
- 小区间优化
- 快速排序的非递归实现
交换排序
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。冒泡排序和快速排序是两个经典的交换排序
冒泡排序
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
动图演示：
参考代码：
// 冒泡排序
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n; ++i)
{
// 标志位，判断过程中是否已经有序
int exchange = 0;
for (int j = 0; j < n - i - 1; ++j)
{
if (a[j] > a[j + 1])
{
Swap(&a[j], &a[j + 1]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
在代码中，设置了一个变量exchange来判断在第一趟冒泡排序的过程中，序列是否已经有序，如果已经有序就无需进行其余的判断操作。
冒泡排序的特性总结：
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
快速排序
快速排序是对冒泡排序的一种改进，由 C.A.R.Hoare（Charles Antony Richard Hoare，东尼·霍尔）在 1962 年提出。
快速排序的基本思想是：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
// 按照基准值对array数组的 [left, right)区间中的元素进行划分
int mid = PartSort(a, left, right);
//[left, mid-1] mid [mid+1, right]
QuickSort(a, left, mid - 1);
QuickSort(a, mid + 1, right);
}
上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像：
将区间按照基准值划分为左右两半部分的常见方式有：hoare版本，挖坑法和前后指针法：
hoare版本
动图演示：
基本步骤：
- 在序列中选择一个基准值key，key一般取最左边或者最右边
- 定义left和right变量分别指向最左边和最右边，left从最左边开始移动，right从最右边开始移动，如果key取最左边，必须让right先移动，如果key取最右边，必须让left先移动
- 当right遇到比key小的值停下，left开始往右边移动，当left遇到比key大的值则停下，交换left和right指向的值，重复上述动作，直到left和right相遇，交换key和相遇位置的值
经过一次单趟排序，最终使得key左边的数据全部都小于key，key右边的数据全部都大于key。
参考代码：
int PartSort1(int* a, int left, int right)
{
int keyi = left;
while (left < right)
{
while (left < right && a[keyi] <= a[right])
right--;
while (left < right && a[keyi] >= a[left])
left++;
if (left < right)
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
return left;
}
挖坑法
动图演示：
基本步骤：
- 选择最左边或者最右边作为key，定义一个变量保存key值，原来key值的位置设置为pivot坑位
- 定义left和right分别指向最左边和最右边，如果选择最左边作为坑位，right先移动，如果选择最右边作为坑位，left先移动
- 选择最左边为key，right先向左边移动，当遇到比key大的值，将坑位的值设置为right指向的值，right作为新的坑位，然后left开始向右移动，当遇到比key小的值，将坑位的值设置为left指向的值，left作为新的坑位
- 重复上述操作，当left和right相遇，将当前坑位的值置为key，由此一来，单趟排序就结束了，最后key所在的位置，前面的值都比key要小，后面的值都比key要大
参考代码：
int PartSort2(int* a, int left, int right)
{
int key = a[left];
int pivot = left;
while (left < right)
{
while (left < right && a[right] > key)
right--;
a[pivot] = a[right];
pivot = right;
while (left < right && a[left] < key)
left++;
a[pivot] = a[left];
pivot = left;
}
a[pivot] = key;
return pivot;
}
前后指针法
动图演示：
基本步骤：
- 选取最左边或者最右边作为key值，定义prev指向序列的开始，cur指向prev的后一个位置
- cur开始向右移动，当遇到比key小的值时，prev先向后移动一位，交换cur指向的位置和prev指向的位置的值，当遇到比key大的值时，cur向右移动，直到遇到比key小的值
- 当cur越界时，将prev指向的值与key交换，由此一来，就完成了一次
单趟排序，key所在的位置，前面的值都比key要小，后面的值都比key要大
参考代码：
int PartSort3(int* a, int left, int right)
{
int keyi = left;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
// ++prev != cur 保证交换的不是同一个位置
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[cur], &a[prev]);
cur++;
}
Swap(&a[prev], &a[keyi]);
return prev;
}
快速排序的优化
三数取中
快速排序的时间复杂度是O(N*logN)，这是我们假设的理想情况，每次走完一次单趟排序，以key值分割的序列的左右区间的长度是相同的，每次递归将当前序列分割成两半，一直递归下去：
但是在极端情况下，key选取到了序列中最小或者最大的数，也就是序列本身已经有序或者接近有序，那么快速排序的时间复杂度就会被降到O(N^2)：
由此我们可以看出，影响快速排序效率的因素之一是单趟排序中选取的key值，key越接近于序列的中位数，快速排序的效率就越高，由此就可以得到快速排序的第一个优化三数取中：
- 三数取中的思想是在进行单趟排序之前，先取最左边的数，最右边的数，以及中间的数的中间值做为key，这就保证了我们选取的key值一定不是序列的最大或者最小值
参考代码：
// 三数取中
int GetMidIndex(int* a, int left, int right)
{
int mid = left + ((right - left) >> 1);
if (a[mid] < a[left])
{
if (a[left] < a[right])
{
return left;
}
else if (a[right] < a[mid])
{
return mid;
}
else
{
return right;
}
}
else // a[mid] > a[left]
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[right] < a[left])
{
return left;
}
else
{
return right;
}
}
}
在单趟排序的最开始，先三数取中取得key值，再与最左边的值交换作为key值（以hoare版本为例）：
int PartSort1(int* a, int left, int right)
{
int midi = GetMidIndex(a, left, right);
Swap(&a[midi], &a[left]);
int keyi = left;
while (left < right)
{
while (left < right && a[keyi] <= a[right])
right--;
while (left < right && a[keyi] >= a[left])
left++;
if (left < right)
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
return left;
}
小区间优化
通过我们的分析，就算快速排序在理想情况下，每次都取到中间值作为key值，每次往下递归也必须开辟上一层递归层数的两倍的函数栈帧，而栈的空间是有限的，如果遇到数据比较大的序列，有可能会导致栈溢出，所以这也是快速排序可以优化的一个点。
当快速排序向下递归，越往下递归的层数会越来越多，所以我们可以控制在下层的小区间进行优化，让小区间的数不进行递归排序，进行直接插入排序，这样就无需额外开辟过多的栈空间，可以避免栈溢出。
参考代码：
// 快速排序
void QuickSort(int* a, int left, int right)
{
if (left >= right)
return;
if (right - left + 1 < 10)
{
InsertSort(a + left, right - left + 1);
}
else
{
int mid = PartSort1(a, left, right);
//[left, mid-1] mid [mid+1, right]
QuickSort(a, left, mid - 1);
QuickSort(a, mid + 1, right);
}
}
快速排序的非递归实现
为了解决快速排序在遇到海量数据的情况下，我们可以实现一个非递归的版本来解决这个问题。
参考代码：
// 快速排序非递归实现
void QuickSortNonR(int* a, int left, int right)
{
Stack st;
StackInit(&st);
StackPush(&st, left);
StackPush(&st, right);
while (!StackEmpty(&st))
{
int end = StackTop(&st);
StackPop(&st);
int begin = StackTop(&st);
StackPop(&st);
int keyi = PartSort1(a, begin, end);
//[begin, keyi - 1] keyi [key + 1, end]
if (begin <= keyi - 1) {
StackPush(&st, begin);
StackPush(&st, keyi - 1);
}
if (keyi + 1 <= end) {
StackPush(&st, keyi + 1);
StackPush(&st, end);
}
}
StackDestroy(&st);
}
快速排序的特性总结：
- 快速排序整体的综合性能和使用场景都是比较好的
- 时间复杂度：O(N*logN)
- 空间复杂度：O(logN)
- 稳定性：不稳定