前言
本期主角
是这个小老头
图灵奖得主，
美国国家科学院外籍院士，
美国国家工程院外籍院士，
英国皇家工程院院士，
英国皇家学会院士
鼓掌????????????
感觉这个小老头很叼噢(确实很叼)
从标题就知道，他的作品叫快速排序
希尔排序都是以自己名字命名的，
他的就俩字，Quick
可见这个算法的优秀性，
目前，快速排序是效率最快的排序之一
基本思想
-
从待排序的数组中选取一个基准值.
(我们把基准值记为key) -
再将数组分为两部分:
1. 左子数组所有元素小于基准值
2. 右子数组所有元素大于基准值 -
左右子数组再选基准值重复这个过程
hoare版图示理解
(共三个版本，hoare版是最初版)
先定义一个乱序数组
思路：
- 将第一个元素6作为基准值
- 定义两个指针指向:第一和最后的位置
- 左边的指针(L)找比基准值大的值
- 右边的指针( R)找比基准值小的值
- R先走，找到满足要求的值后停止
- L后走，找到满足要求的值后停止
- L和R都停止，交换L和R的值
- 重复循环，直到L和R指向同一个值
- 交换基准值与L的值
图示：
看图可知：
基准值的左边全部小于它基准值的右边全部大于它这说明这个基准值6
已经放在了数组中的正确位置!我们只要不断递归左右子数组
最终这个数组就会变成有序!
单趟排序代码实现
//hoare
int PartSort1(vector<int>& f,int left,int right)
{
int key = left;
while (left < right)
{
//右找小
while (left<right&&f[right] >= f[key])
right--;
//左找大
while (left<right&&f[left] <= f[key])
left++;swap(f[left], f[right]);
}
swap(f[key], f[left]);
return left;
}
注意：
内层循环注意加上left<right否则可能会越界
完整代码
//hoare
int PartSort1(vector<int>& f,int left,int right)
{
int key = left;
while (left < right)
{
//右找小
while (left<right&&f[right] >= f[key])
right--;
//左找大
while (left<right&&f[left] <= f[key])
left++;swap(f[left], f[right]);
}
swap(f[key], f[left]);
return left;
}void QuickSort(vector<int>& f, int begin, int end)
{
if (begin >= end)
return;
int key = PartSort3(f, begin, end);
QuickSort(f, begin, key - 1);
QuickSort(f, key + 1, end);
}
缺陷及优化
缺陷：
当原数组已经有序时
再使用快排可能会导致栈溢出因为R每次都走完了全部元素
一共要走:N+(N-1)+(N-2)+...+1次
时间复杂度：O(N^2)
优化：
三数取中法：
从最左,最右和中间的元素中
选取一个既不是最大也不是最小的
元素做基准值key.
选好后都将它与最左边的值交换
相当于还是用最左边做key.
即使原数组有序也不会影响到效率
代码实现：
原理就是取三个数的中间值然后与最左值交换，原理实现什么方法都是可以的
int GetMidIndex(vector<int>&f,int left,int right)
{
int mid = (left + right) / 2;
if (f[left] > f[mid])
{
if (f[mid] > f[right])
return mid;
else if (f[left] < f[right])
return left;
else
return right;
}
else if (f[left] < f[mid])
{
if (f[mid] < f[right])
return mid;
else if (f[left] > f[right])
return left;
else
return right;
}
return mid;
}
结语
第一种方法都这么叼了，那后面的方法是不是更厉害？
准确的来说，在效率上并不是，
但是hoare这个版本有坑，容易写错，
下两个版本会好理解，并且更容易实现
然而不管是hoare,挖坑,前后指针法
都是使用递归的手段解决问题
还有一种方法:快排非递归法它可以解决栈溢出的问题