[数据结构]-玩转八大排序（二）冒泡排序快速排序
前言
作者：小蜗牛向前冲
如果觉的博主的文章还不错的话，还请
点赞，收藏，关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正。
目录
一 冒泡排序
二 快速排序
1 hoare版本实现
2 挖坑法实现
3 前后指针法
三 快速排序的优化
1 三数取中优化key的取值
2 小区间优化
四 非递归实现快速排序
五 快排的特性总结
书接上回！我们前面讲到了八大排序中的插入排序和选择排序。选择排序中的堆排序效率是较高的，其中的希尔排序当数组接近有序效率也是相当高的；那还有哪些更好的排序吗？有的，本篇介绍的快速排序就比较厉害在讲快速排序之前我们先要实现一下我们的老朋友冒泡排序。
其中 冒泡排序和快速排序都属于交换排序：
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
一 冒泡排序
冒泡排序的简单思路就是二个数二二比较，将如果前一个数比后一个数大就交换，以此类推就可以完成数组的排序。
下面我们就用代码来实现一下吧！
//冒泡排序
void BubbleSort(int* a, int n)
{
int i = 0;
//控制排序的趟数
for (i = 0;i < n;i++)
{
int exchange = 0;
//完成一次排序
for (int j = 0;j < n - 1 - i;j++)
{
if (a[j] > a[j + 1])
{
swop(&a[j], &a[j + 1]);
exchange = 1;
}
}
//数组有序直接跳出
if (exchange == 0)
{
break;
}
}
}这里我们测试一下：
冒泡排序的特性总结：
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
二 快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后是左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
对于快速排序其实是有三种方法的，下面我们一一去实现他。
1 hoare版本实现
hoare大佬不得不说是真的厉害，下面我们就去看看大佬是这么实现快速排序的吧！
首先我们可以先排一个数到指定位置：
1 选择一个数key(一般是第一个或者是最后一个)
2 在单趟排序中是要保证小数在key的左边,大数在key的右边。
下面我们走一下这个思路：这里我们要先让R先走(至于为什么后面会有解答),注意R是找小数，找到就停下来，L是找大数，找到也停下来，然后交换R和L位置的数。
最后当他们相遇的时候就停下来，交换此位置的数和key。
这里解释一下我们为什么要让R先走，当key在左边的时候。
其实我们是要保证相遇的位置要比key要小，当R先走的情况，R和L相遇的情况无非有二种情况：
L撞R
R撞L
可以看到，当R先走的时候无论是R撞L还是L撞R都会满足相遇的位置要比key要小。同理，当key在最右边的时候,L就要先出发。
当key换到R和L的相遇位置后，就说明key已经排序好了。
下面我们写个代码实现一下：
// hoare,区间[left,right]
int PartSort1(int* a, int left, int right)
{
int keyi = left;
while (right > left)
{
//R找小
while (right > left && a[right >= a[keyi]])
{
--right;
}
//L找大
while (right > left && a[left] <= a[keyi])
{
++left;
}
//注意这里R和L交换的前提一定要有right > left
if (right > left)
{
swop(&a[left], &a[right]);
}
}
//出来后R和L相遇,与keyi位置的值交换
int meeti = left;
swop(&a[meeti], &a[keyi]);
return meeti;//返回相遇位置的下标
}这里我们实现了一个key的排序，但要排序好整个数组，我们还要选择出无数个key,在排序key,这就不得不用到的递归实现了。
递归实现选出key的排序
我们知道key的左边都是比他小的数，右边都是比他大的数。那么key排序位置就是此位置了。这里时我们只要去排key的左区间的数和右区间的数，同理，我们在这里二个区间继续选key排序,就像展开的二叉树一样。
代码实现：
//快速排序
void QuickSort(int* a, int begin,int end)
{
//递归结束的标志
if (begin >= end)
return;
int keyi = PartSort1(a, begin, end);
//排key的左区间
QuickSort(a, begin, keyi - 1);
//排key的右区间
QuickSort(a, keyi+1,end);
}这里我们测试一下
好了这里就hoare大佬写的版本，但是有另些大佬觉的这个方法不容易理解。所以大佬们就想出了另外一个方法挖坑法。
2 挖坑法实现
该方法其实和hoare大佬写的方法是非常相似的，就只是做一些改动。
我们仍然让R找小数，L找大数，在最左边选出key并形成一个坑位，当R找到小数时，停下来，填到左边坑中去，并在此位置形成新的坑位；在L走找大数，当找到大数时，停下来，将大数填到右边的坑位中，并形成新的坑位；当L和R相遇后，也即是在一个坑位上，这样我们就将key填到坑中去。
大家可能回想这和hoare大佬写的有什么区别吗?
其实是有的，大家可以对比一下二个版本，排第一个key时各个数据的位置。
hoare版本
挖坑法
下面我们实现一下吧！
//挖坑法
int PartSort2(int* a, int left, int right)
{
int hole = left;
int key = a[left];
while (left < right)
{
//R找小数，填到左边坑中
while (left < right && a[right] >= key)
{
--right;
}
a[hole] = a[right];
hole = right;//形成新的右边坑位
//L找到数。填到右边坑位中
while (left < right && a[left] <= key)
{
++left;
}
a[hole] = a[left];
hole = left;//形成新的左边坑位
}
a[hole] = key;
return hole;
}看到这里不少小伙伴肯定觉得，这样应该就是最优写法了吧！，但是大佬们还不满意，他们认为还是容易写错，为什么这么说呢?因为我们很容易漏写在R找小和L找到及交换过程中都要满足right>left这个条件；是的！真的很容易漏写，博主就烦了这样的错误，很显然他报错了。
我调试了一下，发现left++都超出数组范围了。
所以大佬们想了一种更加简单的写法。
3 前后指针法
这种方法我们需要二个指针,prev指向序列的开头，cur指针指向prev的后一个位置，
那么prev指针和cur指针又在干什么呢？
其实，cur指针在找小，遇到比key小的值将停下来，++prev,交换prev和cur位置上的数据；
而prev是有二种状态的，一是紧紧跟这cur,二是在比key大的前一个数停下来；当cur越界后，就将a[prev]的a[keyi]交换。
1 这里我们需要要注意，cur只有遇到比key值小的值才停下来，在观察++prev是否和cur相等，如果相等就没有必要交换了。
2 因为是cur比prev先走，而cur只有遇到比key值小的值才停下来，所以a[perv]的值是一定比key大的。
下面我们写代码实现：
//前后指针法
int PartSort3(int* a, int left, int right)
{
int prev = left;
int cur = left + 1;
int keyi = left;
while (cur <= right)
{
//找小
if (a[cur] < a[keyi] && ++prev != cur)
swop(&a[cur], &a[prev]);
++cur;
}
//cur越界，交换
swop(&a[keyi], &a[prev]);
return prev;
}这里我们测试一下快速排序的性能“
//测试性能
void TestOP()
{
srand(time(0));
const int N = 100000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
}
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
int begin3 = clock();
SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
HeapSort(a4, N);
int end4 = clock();
int begin5 = clock();
QuickSort(a5, 0, N - 1);
int end5 = clock();
int begin6 = clock();
//MergeSort(a6, N);
int end6 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("QuickSort:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
}
int main()
{
//int a[] = { 9,3,4,1,8,0 };
//int n = sizeof(a) / sizeof(a[0]);
TestOP();
//testheap();
/*BubbleTest(a, n);*/
//QuickTest(a, n);
return 0;
} 
我们可以看到快排是非常优秀的，有人可能会问，这么希尔排序会比快速排序还要优秀，其实不然，因为我们的随机数是用rand函数生成的，当生成随机的范围最大就 RAND_MAX(32767),而我们数组中有10万个数，也就意味这会生成许多相同的数，而且由于我们是用时间戳来作为种子，而当我们调用生成随机数速度没有超过1秒，就会生成许多相同的而且连续存放的随机数。我们说过当我们去排一个相对有序序列时希尔排序的效率是非常高的，而快排就要不断递归下去排序。
三 快速排序的优化
他们心里可能回想，这快排都这么快了还这么优化呢？
其实不然，当我们用当前思路去排已经排好的数据会这么样呢？我们上面说到排序一个相对有序的序列时会比不上希尔，但更为重要的是当数组数据较大而接近有序的时候，递归的深度会过高，导致栈溢出。那我们还有上面办法去优化吗？
序列非有序的递归接进二叉树的形式
序列有序的递归的形式
1 三数取中优化key的取值
为了避免出现序列出现有序或者接近有序情况导致快排的效率低下，其实如果我们的key如果每次都是一个中位数就好了，那么排序的时间复杂度就为O(N*longN),为了达到这个目的，我们用三数取中的方式。每次将a[left],a[mid],a[right]三个数的大小进行比较，找到中为数做为key。
下面代码实现一下：
//三数取中
int GetMidIndex(int* a, int left,int right)
{
int mid = (left + right) / 2;
//三数二二比较
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[mid] > a[left])
{
return right;
}
else
{
return left;
}
}
else//(a[left] > a[mid]
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[right] > a[left])
{
return left;
}
else
{
return right;
}
}
}这里我们用已经排序好a4数组验证一下：
那快速排序还能优化吗？有的，其实我们知道当排序到最后几层的时候，就要调用大量的递归，我们最后一层相当要调用1/2的递归。倒数第2层要调用1/4的递归，倒数第3层要调用1/8的递归。
2 小区间优化
三数取中虽然进行了一定程度的优化，那么我们能不能减少递归的调用呢?因为过分的递归调用会消耗大量的栈空间而导致栈溢出。如果我们把最后3层改为插入排序，这样因为原先通常快速排序已经相当有序了，效率也不会太低，还能减少大部分的递归调用。
代码实现：
//快速排序
void QuickSort(int* a, int begin,int end)
{
//递归结束的标志
if (begin >= end)
return;
//最后3层改为插入排序
if (end - begin < 8)
{
InsertSort(a + begin, end - begin - 1);
}
else
{
int keyi = PartSort3(a, begin, end);
//排key的左区间
QuickSort(a, begin, keyi - 1);
//排key的右区间
QuickSort(a, keyi + 1, end);
}
}测试一下
这里可以看到当数组有100万个数据的时候栈还是没有溢出，虽然效率低了，但我们扩大了快速排序的使用范围。
四 非递归实现快速排序
虽然我们优化了快速排序让他不那么容易就栈溢出了，但是当数据非常大的有时候栈还是会溢出，因为栈空间大概只有8MB，而堆上的空间有几个G，我们可以将递归改写为非递归。
我们知道递归的思路是按照区间来排的，先是排整个数组，然后是左右区间，在把左区间分为左右区间，把右区间分为左右区间来排依次类推。数组的边界我们可以用left和right。
那么非递归的思路就出来了：这里我们要借助数据结构的栈，首先我们要将数组的左右边界入栈，然后取出栈顶的right和left(取出来的同时我们还要进行pop),这时我们就可以用left和right表示一个去间了；之后我们调用单趟排序进行排序，排序完成后我们在此区间的左右区间入栈；重复上述操作，直到栈中的元素为空。
//非递归实现
void QuickSortNonR(int* a, 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(a, left, right);
//如果区间中的元素>1
//先入右边的区间
if (right > keyi + 1)
{
StackPush(&st, keyi+1);
StackPush(&st, end);
}
//在入左边区间
if (left < keyi - 1)
{
StackPush(&st, left);
StackPush(&st, keyi-1);
}
}
//销毁栈
StackDestroy(&st);
}
测试一下：
五 快排的特性总结
快速排序的特性总结：
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
这期博客就到这里，下期博客继续和大家分享归并排序和非比较排序。