快排的历史及介绍
快速排序由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版解答疑惑及易错点指出:
- key的选择
之所以选择最左边的位置设置key,是因为利用这个值在写代码和进行判断时更方便一些,利用right位置的值当做key当然也可以,如果用递归函数传参数组的第二个元素做key,在递归到每个小区间只有一个数时就会出现错误,因为没有key。
- 相遇节点为什么可以和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(nlogn)。
至于空间复杂度从上边的图就可以看出,因为递归开辟的空间是在栈上的,每次开辟的空间都可知小于n,故每次递归开辟空间为O(1),所以快排的时间复杂度为递归深度乘于O(1),最坏情况为O(N),最好的情况为O(logN)。