排序-快速排序

前言

本期主角

是这个小老头

图灵奖得主，

美国国家科学院外籍院士，

美国国家工程院外籍院士，

英国皇家工程院院士，

英国皇家学会院士

鼓掌👏👏👏

感觉这个小老头很叼噢(确实很叼)

从标题就知道，他的作品叫快速排序

希尔排序都是以自己名字命名的，

他的就俩字，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;
}