快排&超详细,Leetcode排序数组题目带你升华掌握(上)

简介: 快排&超详细,Leetcode排序数组题目带你升华掌握

快排的历史及介绍

快速排序由C. A. R. Hoare在1962年提出。

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

 其中Hoare大佬写的版本由于没有那么容易理解且容易出现错误,在后人的智慧下,进行了小小的改变,分化出了挖坑法和双指针法。我们逐个进行讲解。

Hoare版

递归函数分析思路如下

在数组中选定一个关键的点,最右边或者最右边都可以。

 我们选择最左边进行讲解,找到关键位置后设置left和rght然后分别从数组左边和最右边开始遍历,右边先行,找到小于key位置的值就停下了,左边的找大于key位置的值,找到后就互换,直到左下标和右下标相遇,相遇的时候说明左边已经没有大于key位置的值了,右边没有小于key位置的值了,交换相遇位置的值和key位置的值,就可以将该组数分割成以key位置的值分割的两组数。

有了思路我们可以写出以下的代码:

//hoare版本
int PartSort1(int* a, int left, int right)
{
  int key = a[left];//设置关键点
  while (left < right)
  {
    while (a[right] > a[keyi])//从最右边开始找到大于关键点的坐标
    {
      --right;
    }
    //找大
    while (a[left] < a[keyi])//从左边开始找到小于key的坐标
    {
      ++left;
    }
    Swap(&a[left], &a[right]);//交换
  }
  Swap(key, &a[left]);//当left相遇,就交换关键点和相遇点的值
  return left;返回相遇点的坐标
}

Hoare版解答疑惑及易错点指出:

  1. key的选择

 之所以选择最左边的位置设置key,是因为利用这个值在写代码和进行判断时更方便一些,利用right位置的值当做key当然也可以,如果用递归函数传参数组的第二个元素做key,在递归到每个小区间只有一个数时就会出现错误,因为没有key。

  1. 相遇节点为什么可以和key位置的互换呢?为什么相遇点的数值一定会比key位置的值小呢?

大家可以思考一下…

这就要看左右指针谁先行了,如动图所示

如果是right先行,会发生什么呢?其实除了最后left和right相遇,其他的都是一样,如果是right先行的话。

在循环判断中右边先行是一定要注意的。


还有吗?

还有呢。

判断条件怎么写呢?判断条件是大于交换还是大于等于(相对left而言)交换呢?如果是left位置的值大于key的话,就交换有可能会发生森么情况呢?

 看这个图,在交换了组边的6和右边的2之后,right开始–,因为判断条件是a[right]>key,所以当right找到5时,5=key,right就跳出了循环。同理,因为不满足left下标的值小于key,left跳出循环,交换以left为下标和以right为下标的值,交换的还是5和5,再次循环,判断left<right成立,继续循环,left和right还在原来的位置,继续交换,就会陷入死循环,所以这里的判断条件要写为a[left]>=key,a[right]<=key,然后再进行交换。

看动图

判断条件也要注意,这种情况很难想到,所以有时运行错误不知道问题出在哪里

更改上边问题,将判断条件改为a[right] >= key和a[left] <= a[keyi]


 思考了这么多,终于找到相遇的点后交换key和a[left](a[left]都可以),就可以将这个数组分为两个大小不同的的区间啦!

真的吗?

 前边初始化key=a[left],交换key和遍历后的a[left],然而a[0]并没有和找到的值进行交换,而是key这个数和找到的相遇点交换,这个时候a[left]就没有改变为相遇点找到的小于key的值,如果一直递归下去,会变成什么样呢?(上边动图部分,key改成a[left])

再来看排序该组数据

如果是创建的key和找到的点进行交换,就会出现数据污染,好多数据都被更改了,这样的排序一定是错误的,所以初始化条件可以这样。

int keyi=left;

int key=a[keyi]

在判断时利用key,在交换时交换a[keyi]和a[left]即可。


终于结束啦,然而并没有。

 要注意的是在right和left找的过程中left也不能小于right,比如该数组是有序的,在排序的过程中,right先行,但是一直没有找到小于a[keyi]的值,直到到达left的位置再次减一,就会越界访问。

完整代码如下

//hoare版本
int PartSort1(int* a, int left, int right)
{
  //int midi=GetMidi(a,left,right)
  //Swap(&a[left[,&a[midi]);
  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;
}

是不是细节满满,一不小心就会出来好多bug。


挖坑法

同样先看图

挖坑法相较于Hoare大佬的方法,步骤更加清晰明了一点,一步一步实现

上边的动图表现得十分清晰,设置一个坑位,保存left位置的值,设置hole变量等于left,然后从右边找小于a[keyi]即上图key的值,填入坑中,这时将找到的值的位置right设置为坑,然后从左往右找大于a[keyi]的值填入hole,将left所在位置设置为hole,不断循环,直到left等于right,将之前保存的key,即a[keyi]填进坑里,就完成了前边相同的操作。

代码如下,很容易理解

//挖坑法
int PartSort2(int* a, int left, int right)
{
  int key = a[left];
  //保存key值以后。左边形成一个坑
  int hole = left;
  while (left < right)
  {
    while (left < right && a[right] >= key)
    {
      --right;
    }
    a[hole] = a[right];
    hole = right;
    //左边再走,找大,填到右边的坑,左边重新形成新的坑位
    while (left < right && a[left] <= key)
    {
      ++left;
    }
    a[hole] = a[left];
    hole = left;
  }
  a[hole] = key;
  return hole;
}

最后返回right,left,hole都可以,反正最后他们在同一个位置上。


双指针法

看几遍动图,不管他们用什么方法进行实现,最终实现的效果都是相同的。双指针法只要懂得了原理,还是很容易实现的。

双指针法和前边两种方法略有不同,来体验一下。先看代码后进行讲解

//前后指针法
int PartSort3(int* a, int left, int right)
{
  int midi = GetMidi(a, left, right);
  Swap(&a[left], &a[midi]);
  int prev = left;
  int cur = prev + 1;
  int keyi = left;
  while (cur <= right)
  {
    if (a[cur] < a[keyi])
    {
      ++prev;
      if (prev != cur)
      {
        Swap(&a[prev], &a[cur]);
      }
    }
    ++cur;
  }
  Swap(&a[prev], &a[keyi]);
  return prev;
}

还是一样选择left位置的值作为key,设置两个指针,一个指向数组最前边的位置,一个在他的后边,前后指针法因此得名。

具体思路:

 设置前后指针,后边的指针只要不越界访问,cur就一直往后走,如果prev的下一个位置不是cur,且cur找到小于key的值时,就交换prev位置和cur位置的值。直到最后cur大于right结束循环。此时prev位置的值一定小于或等于key,因为cur在后边查找的过程中最不济的情况也就是一个也没找到,prev和他自己换,照样也不变,在找到第一个之前cur和prev一直一起移动并一直在cur的后一位,当cur找到大于key位置的坐标后,prev不动,cur继续移动,所以当cur找到小于key的位置时,prev的下一个位置一定是大于key的,可以放心交换。

直到最后cur走到数组尽头,就如前边所说,prev的下一位一定大于key,而prev位置的值一定小于等于key,交换a[prev]和a[keyi]的值,就可以将数组分成以prev位置为中心的两组,左边的值都小于等于key,右边的值都大于key。

循环有一种更简单的方法表示,效果相同

while (cur <= right)
  {
    if (a[cur] < a[keyi] && ++prev != cur)
    {
      Swap(&a[prev], &a[cur]);
    }
    ++cur;
  }

&&操作符,当前一条件为假,后一条件就不走,如果前一条件为真后,才会走后一条件,然后prev才会++,与上边实现的效果相同。


递归函数

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);
}

begin和end是传进来的数组段的第一个位置和最后一个位置的下标。要注意接下来的递归数组的区间还有结束判断条件。

举一个例子说明递归流程。

递归结束后,数组就变为有序的了。至于先往右递归还是先往左都可以,没有区别。

上边递归时用的Hoare大佬的版本,用挖坑法和双指针法也都可以。

时间复杂度与空间复杂度

快排的时间复杂度为O(nlogN),空间复杂度为O(N),如果情况比较好的话为O(log2n),空间是可以复用的,一边用完另一边还可以用。
时间复杂度最坏的情况是若该数组为有序数组。最好情况就是一直取到中间位置。
最坏情况:

若数组数量为n,一次只排好了一个数据,right第一次跑n次,第二次跑n-1次,则时间复杂度明显为O(n^2)。
假使每次都能找到中间值,此时时间复杂度最低。2^h=n,所以n=log2 ^n。

最好情况时间复杂度为O(n
logn)。

至于空间复杂度从上边的图就可以看出,因为递归开辟的空间是在栈上的,每次开辟的空间都可知小于n,故每次递归开辟空间为O(1),所以快排的时间复杂度为递归深度乘于O(1),最坏情况为O(N),最好的情况为O(logN)。

目录
相关文章
|
1月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
38 0
|
1月前
|
程序员 C语言
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
|
1月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
19 4
|
1月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
18 0
Leetcode第三十三题(搜索旋转排序数组)
|
1月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
56 0
|
1月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
16 0
|
3月前
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
|
2月前
|
SQL Oracle 关系型数据库
CASE WHEN 语句的语法及示例,LeetCode 题目 “确认率” 练习
本文介绍了SQL中CASE语句的两种形式和语法,并通过LeetCode题目“确认率”的SQL查询示例展示了CASE语句在实际问题中的应用,解释了如何使用CASE语句计算特定条件的比率。
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行