快速排序的基本思想
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法
其基本思想为：
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{
if(right - left <= 1)
return;
// 按照基准值对array数组的 [left, right)区间中的元素进行划分
int div = partion(array, left, right);
// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
// 递归排[left, div)
QuickSort(array, left, div);
// 递归排[div+1, right)
QuickSort(array, div+1, right);
}上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
划分区间的常见方式
将区间按照基准值划分为左右两半部分的常见方式有三种，
- hoare方法
- 挖坑法
- 前后指针法
三种方法是排key左右区间的不同，整体快排的思想是递归
1.hoare方法
https://img-blog.csdnimg.cn/07ddcfdc56874b2a9d12f585534ac87e.gif#pic_center
1.1图示
定义left和right来找大和找小
right先走找大，left再走找小，找到交换
继续找大找小
相遇停下来，和key交换
1.2为什么相遇位置一定比key小
这里我们有一个问题：为什么相遇位置一定比key小？
因为右边先走
相遇有两种情况：
- right遇left -> left先走，right没有遇到比key小的，一直走，直到遇到left停下来，left存的是比key小的值
- left遇right -> right先走，left没有遇到比key大的，一直走，直到遇到right停下来，right存的是比key大的值
- 所以我们得出一个结论，左边做key，右边先走；右边做key，左边先走
如果左边有序，右边也有序，整体就有序了
那么如何让左右有序呢？
类似二叉树，递归左树和右树
第一遍排序后的left和right的范围是：[begin,keyi-1]，keyi，[keyi+1,end]
然后继续递归，直到这个区间只有一个值或者不存在
1.3代码示例
//hoare方法
int PartSort1(int*a,int begin,int end)
{
int midi = GetMidi(a, begin, end);
Swap(&a[midi], &a[begin]);
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;
return keyi;
}2.挖坑法
https://img-blog.csdnimg.cn/c2dde0e21f32461fb43db524559ca36d.gif#pic_center
2.1图示
right找小，left找大，right先走，找到小和坑位交换，然后left走，left找到大之后和坑位交换，交替进行直到相遇
他们一定会相遇到坑的位置
相遇之后将key的值放到坑位中，这时候key左边就是比key小的，key右边就是比key大的
2.2代码示例
我们写一个挖坑法的函数来排keyi左右的数据
先用三数取中方法得到keyi，定义一个key保存keyi的值，定义一个坑位holei先放到begin
- 右边找小，填到左边的坑里，右边成为新的坑
- 左边找大，填到右边的坑里，左边成为新的坑
- 相遇后将key放到坑里，返回坑的下标
//挖坑法
int PartSort2(int* a, int begin, int end)
{
int midi = GetMidi(a, begin, end);
Swap(&a[midi], &a[begin]);
int key = a[begin];
int holei = begin;
while (begin < end)
{
//右边找小
while (begin < end && a[end] <= key)
--end;
a[holei] = a[end];
holei = end;
//左边找大
while (begin < end && a[begin] >= key)
++begin;
a[holei] = a[begin];
holei = begin;
}//相遇
a[holei] = key;
return holei;
}3.前后指针法
https://img-blog.csdnimg.cn/8baec430614e47dfa382926553830c14.gif#pic_center
3.1图示
prev要不就是紧跟cur，要不prev和cur之间就是比key大的值
3.2代码示例
//前后指针法
int PartSort3(int* a, int begin, int end)
{
int midi = GetMidi(a, begin, end);
Swap(&a[midi], &a[begin]);
int keyi = begin;
int prev = begin, cur = begin + 1;
while (cur <= end)
{
//if (a[cur] < a[keyi])
//{
// ++prev;
// Swap(&a[prev], &a[cur]);
// ++cur;
//}
//else
// ++cur;
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
++cur;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
return keyi;
}4.快速排序优化
- 三数取中法选key
- 递归到小的子区间时，可以考虑使用插入排序
4.1三数取中方法
这里我们的key默认取的是第一个数，但是这种情况有个弊端，不能保证key一定是那个中间值，可能是最小的，也可能是最大的
但是理想情况下，key选中间值是效率最高的，每次都是二分
这里就有一个方法能很好的解决这个问题：三数取中
我们写一个取中函数，将中间值与begin交换，还是将key给到begin
int GetMidi(int* a, int begin, int end)
{
int midi = (begin + end) / 2;
if (a[begin] < a[midi])
{
if (a[midi] < a[end])
return midi;
else if (a[begin] > a[end])
return begin;
else
return end;
}
else
{
if (a[midi] > a[end])
return midi;
else if (a[end] > a[begin])
return begin;
else
return end;
}
}三数取中可以排除掉最坏的情况，相对而言可以提高效率
4.2小区间优化
如果是满二叉树，最后一层占50%的节点，倒数第二层占25%，倒数第三层占12.5%
假设我们要对这五个数排序，就需要调用六次递归，这代价是非常大的
我们可以使用插入排序，插入排序对局部的适应性是很好的，所以我们在这个区间缩小的一定范围的时候就可以使用插入排序
一般选择最后三到四层，因为最后三层就占据了将就90%的递归，将最后三层的递归消除是能够明显提高效率的
剩下的区间不一定是从0开始的，也有可能是后半段，所以这里插入排序从begin开始
总代码
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
break;
}
a[end + 1] = tmp;
}
}
int GetMidi(int* a, int begin, int end)
{
int midi = (begin + end) / 2;
if (a[begin] < a[midi])
{
if (a[midi] < a[end])
return midi;
else if (a[begin] > a[end])
return begin;
else
return end;
}
else
{
if (a[midi] > a[end])
return midi;
else if (a[end] > a[begin])
return begin;
else
return end;
}
}
//hoare方法
int PartSort1(int*a,int begin,int end)
{
int midi = GetMidi(a, begin, end);
Swap(&a[midi], &a[begin]);
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;
return keyi;
}
//挖坑法
int PartSort2(int* a, int begin, int end)
{
int midi = GetMidi(a, begin, end);
Swap(&a[midi], &a[begin]);
int key = a[begin];
int holei = begin;
while (begin < end)
{
//右边找小
while (begin < end && a[end] <= key)
--end;
a[holei] = a[end];
holei = end;
//左边找大
while (begin < end && a[begin] >= key)
++begin;
a[holei] = a[begin];
holei = begin;
}//相遇
a[holei] = key;
return holei;
}
//前后指针法
int PartSort3(int* a, int begin, int end)
{
int midi = GetMidi(a, begin, end);
Swap(&a[midi], &a[begin]);
int keyi = begin;
int prev = begin, cur = begin + 1;
while (cur <= end)
{
//if (a[cur] < a[keyi])
//{
// ++prev;
// Swap(&a[prev], &a[cur]);
// ++cur;
//}
//else
// ++cur;
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
++cur;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
return keyi;
}
//快排
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
if (end - begin + 1 <= 10)
InsertSort(a + begin, end - begin + 1);
else
{
//hoare法
//int keyi = PratSort1(a, begin, end);
//int keyi = PartSort2(a, begin, end);
int keyi = PartSort3(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
}
int main()
{
int a[] = { 9,8,7,6,6,5,4,3,2,1,10,14,12,11,15 };
int n = sizeof(a) / sizeof(a[0]);
QuickSort(a, 0, n - 1);
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
return 0;
}
