快排&超详细，Leetcode排序数组题目带你升华掌握（下）-阿里云开发者社区

优化

给一个数组，要求给他排序，要求很简单，却只有50%的通过率，力扣标记简单不一定简单，标记中等那一定是有点难。

这题很显然，普通的排序比如冒泡排序，插入排序，选择排序是过不了的，我们刚刚学习了快排，何不尝试一波。

void Swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}
 void QuickSort1(int* a, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
  int keyi = PartSort1(a, begin, end);
  QuickSort1(a, begin, keyi - 1);
  QuickSort1(a, keyi + 1, end);
}
//hoare版本
int PartSort1(int* a, int left, int right)
{
  int keyi = left;
  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[keyi], &a[left]);
  return left;
}
int* sortArray(int* nums, int numsSize, int* returnSize){
    QuickSort1(nums, 0, numsSize-1);
    *returnSize=numsSize;
    return nums;
}

快排解题的代码如下

然而却发现

用hoare大佬的方法走一遍，发现时间复杂度在这组用例上为O(N^2)，right一直向右移，不会分成左右两组，一直递归n次，right向前的次数从n到1，这样的话花费的时间太多了，针对这种情况进行优化，就要介绍三数取中。

三数取中

如何防止上面最坏的情况发生？

只需要防止最左边的数为该组数里最小的数即可。

可以找出left位置的值和right位置的值及（left+right)/2数组中间下标的值，找出他们三个中间大小的一个，与a[left]进行交换，这样就可以防止left是数组中最小的元素这种情况的发生。

将三数取中抽离成函数

//三数取中
int GetMidi(int* a, int left, int right)
{
  int mid = (left + right) / 2;
  //left mid right
  if (a[left] < a[mid])
  {
    if (a[mid] < a[right])
    {
      return mid;
    }
    else if (a[left] > a[right])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
  else
  {
    if (a[mid] > a[right])
    {
      return mid;
    }
    else if (a[left] > a[right])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
}

在每次partsort前搞来中间值的坐标，与left进行交换

int midi=GetMidi(a,left,right)

Swap(&a[left[,&a[midi]);

加上三数取中再次运行

然而。。。。

再次出乎意料，如果是全部数字都一样或者有大量重复数据，right还是像刚才有序数组的情况一样，right一直向左，时间复杂度为O(N^2)，此时三数取中也没用了，无论怎么取，取到的都是2。针对这种情况怎么办？

三路分化

将hoare大佬的方法和双指针法结合起来，将数组分为三个部分，左边小于key，中间的区段是等于key的，右边的部分是大于key的。

设置三个指针，两个指针用于位置的交换是数组划分为三个区间，一个指针用于遍历。

看思路

最后在left和right之间的部分就是等于5的部分，left之前皆小于key，right之后皆大于key。

总结下来只有以下三种情况

cur的值小于key，交换cur的值和left的值，cur++,left++。

cur的值等于key，直接++cur

cur的值大于key，交换cur和right的值，cur不能动。

代码实现

void QuickSort1(int* a, int left, int right)
{
  if (left >= right)
  {
    return;
  }
  int begin = left;//记录左右边界
  int end = right;
  int midi = GetMidi(a, left, right);
  Swap(&a[left], &a[midi]);
  int key = a[left];
  int cur = left + 1;
  while (cur <= right)
  {
    if (a[cur] < key)//重点理解
    {
      Swap(&a[cur], &a[left]);
      ++left;
      ++cur;
    }
    else if (a[cur] > key)
    {
      Swap(&a[cur], &a[right]);
    }
    else
    {
      ++cur;
    }
  }
  QuickSort1(a, begin, left-1);
  QuickSort1(a, right+1, end);
}

这次我们信心满满，如果数组的元素全部为2的话，遍历一遍，right和left直接相遇，甚至只需要O(N)的时间就可以完成。

更改代码后运行。

还是超出时间限制，这又是为什么呢？这道题对快速排序做了针对性的处理，普通的快排很难过这道题，他会检测我们的三数取中，然后搞出对应的一串数字，让每次取出的数都是数组中倒数第二大，这样的话时间复杂度还是很大。

解决方法：

选取数组中任意位置的数和left位置和right作比较选出keyi，而不是一直取中间坐标与他们相比较，用rand函数进行操作，使我们选数位置没有规律可循，这样编译器就不能根据我们所写的代码搞出针对性用例。

代码如下：

int GetMidi(int* a, int left, int right)
{
  //int mid = (left + right) / 2;
  int mid =left+(rand()%(right-left));
  //left mid right
  if (a[left] < a[mid])
  {
    if (a[mid] < a[right])
    {
      return mid;
    }
    else if (a[left] > a[right])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
  else
  {
    if (a[mid] > a[right])
    {
      return mid;
    }
    else if (a[left] > a[right])
    {
      return left;
    }
    else
    {
      return right;
    }
  }
}
void Swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}
void QuickSort1(int* a, int left, int right)
{
  if (left >= right)
  {
    return;
  }
  int begin = left;//记录左右边界
  int end = right;
  int midi = GetMidi(a, left, right);
  Swap(&a[left], &a[midi]);
  int key = a[left];
  int cur = left + 1;
  while (cur <= right)
  {
    if (a[cur] < key)
    {
      Swap(&a[cur], &a[left]);
      ++left;
      ++cur;
    }
    else if (a[cur] > key)
    {
      Swap(&a[cur], &a[right]);
      --right;
    }
    else
    {
      ++cur;
    }
  }
  QuickSort1(a, begin, left-1);
  QuickSort1(a, right+1, end);
}
int* sortArray(int* nums, int numsSize, int* returnSize){
  srand(time(NULL));
    QuickSort1(nums, 0, numsSize-1);
    *returnSize=numsSize;
    return nums;
}

运行后如图

可以发现所用时间还是很长，这道题如果用堆排序和shell排序都是很好过的，放在这里是为了提升我们对快排的理解和掌握。

小区间优化

在上边显示递归流程的图中，我们可以看到递归的过程，类比树的结构，树的每一个节点都是一次递归，树的最后一排的节点个数占全部节点的50%，倒数第二行占总个数的25%，如果分成的数组的量的变小到一定的个数的时候可以不再使用递归，而是选择其他的方法进行排序，可以减少大量的递归次数。

这种方法叫做小区间优化，使用什么排序比较好呢？冒泡排序和选择排序的时间复杂度为O（N²），选择排序的时间复杂度最高为O（N²），可以使用选择排序进行小区间优化，从而减少大量的递归次数

插入排序及小区间优化后的代码如下

//插入排序
void InsertSort(int* a, int n)
{
  //[0,end]有序，把end+1的位置插入到前序序列
  //控制[0,end+1]有序
  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];
      }
      else
      {
        break;
      }-+
      --end;
    }
    a[end + 1] = tmp;
  }
}
//加上小区间优化
void QuickSort2(int* a, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
  if ((end - begin + 1) > 10)//如果一个数组的元素小于10，就进行插入排序
  {
    int keyi = PartSort2(a, begin, end);
    QuickSort2(a, begin, keyi - 1);
    QuickSort2(a, keyi + 1, end);
  }
  else
  {
    InsertSort(a + begin, end - begin + 1);
  }
}
//加上小区间优化
void QuickSort2(int* a, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
  if ((end - begin + 1) > 10)
  {
    int keyi = PartSort2(a, begin, end);
    QuickSort2(a, begin, keyi - 1);
    QuickSort2(a, keyi + 1, end);
  }
  else
  {
    InsertSort(a + begin, end - begin + 1);
  }
}

快排非递归版

复习一下：它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

将一整个数组不断细分，在不断划分的过程中进行有序化，最终完成排序的功能。在前边partsort函数中，我们只要通过某种方法得到分成一组一组的小数组段的left和right即可。

上边的说明递归的流程图是直接全部展开的，实际上是一直向左划分，直到分出的数组left和right相等，然后回到上步。

如图所示

结合代码就很容易明白。

在非递归版本我们想和递归的步骤相同，如何得到上述递归过程中的left和right?这是问题之所在，而且在递归过程中向partsort1传入不同的left和right。

可以借助栈先进先出的功能来实现，push起始的left和right，进行第一次partsort，知道了left和right后，将他们再pop掉。

void QuickSortNonR(int* a, int begin, int end)
{
  ST st;
  STInit(&st);
  STPush(&st, end);
  STPush(&st, begin);
  while (!STEmpty(&st))
  {
    int left = STTop(&st);
    STPop(&st);
    int right = STTop(&st);
    STPop(&st);
    int keyi = PartSort1(a, left, right);
    if (keyi + 1 < right)
    {
      STPush(&st, right);
      STPush(&st, keyi + 1);
    }
    if (left < keyi - 1)
    {
      STPush(&st, keyi - 1);
      STPush(&st, left);
    }
  }
  STDestroy(&st);
}