快速排序
快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
时间复杂度：O(N*logN)
空间复杂度：O(logN)
稳定性：不稳定
一个被大佬选择并加入到函数库的排序,属于是老棒老棒的排序了.
想讲述一下快速排序的思想吧.
快速排序是通过在数组中选出一个基准值(一般选第一个或最后一个)将基准值放在一个左边的数都比基准值小(大)右边的数都比基准数大(小)然后通过基准值又将数组分开成两个然后再进行上述操作.
例: 4 1 3 2 5 8 7 9 以4为基准值经过了一次快速排序后就可以将4放到1 3 2 4 5 8 7 9(注:不同实现方法的顺序是不同的博主的注重点是将4左边数比4小右边比数大的情况.)
这种排序主干有三种实现方法.分hoare版本 挖坑法 前后指针版本
hoare版本实现
思路就是上面的思路,我们先来通过hoare版本来实现一下.
int PartSort1(int* a, int left, int right) { //整体思路是先让right先走找到一个比a[keyi]小的数然后等待left找到比a[keyi]大的数 //然后交换即可. int keyi = left;//不能给零,因为每次递归的时候我们都要通过不同的left来操作. while (left < right) { if (a[right] < a[keyi])//先让right先走为了保证left和right听的位 { while (left < right) { if (a[left] > a[keyi]) { Swap(&a[left], &a[right]); break;//记得break因为我们要先right走. } left++; } } right--; } Swap(&a[left], &a[keyi]);//最后记得把keyi的换位完成 return left; } void QuickSort(int* a, int left, int right) { if (left > right) { return; } int keyi = PartSort1(a, left, right); QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); }
其中PartSort1是我们排序的主干部分,也就是一次排序的经过,然后下面的QuickSort这个函数就是为了给我们的PartSort1提供要排序的空间.
先简单的讲一下QuickSort函数吧,这个函数的作用是为了给PartSort1函数提供要排序的空间然后PartSort1返回基准值的下标我们的QuickSort函数再通过返回的基准值的下标再次将要排序的空间给PartSort1函数,然后PartSort1再进行排序.
可以看懂代码注释的不用看下面部分了
让我们讲一下PartSort1的实现思路吧:
1这个思路属于是有点难理解而且还有部分细节需要注意的,因为他是快排发明者的思路(大佬的思路懂得懂得=.=).
先让right先走(一定是right先走)直到right找到a[right] < a[keyi]的情况这样我们就让right停下让left来走寻找直到left找到a[left] > a[keyi]的情况找到后我们就可以交换left和right的值了,再让left停下让right走.一直这样循环直到left>=right就跳出循环.这时left和right相遇的位置就是我们需要将keyi安放的位置所以最后将keyi和left(或right)的值交换就好.
注意:上面必须right先走不然没法保证left和right相遇的位置可以安放keyi
如果害没理解下面我将用例子来讲解过程.
就用:4,1,5,2,3,7,6,9,8以keyi取左边值做例子.
这样我们的基准值(keyi对应的数组值)左边都是比它小的值了,右边都是比基准值大的值了.
然后通过递归不断的将基准值的左区间和右区间传给PartSort1这样不断更新基准值就可以得到一个有序的序列了.
挖坑法
上面的hoare法有一点难理解,所以就诞生了更易理解的挖坑法.
需要实现的功能一样但是实现思路不同罢了(其实也差不多=.=).
看看代码
int PartSort2(int* a, int left, int right) { //坑法可以不用让right先走了,更加便于理解=.= //下面的思路以升序为例 //整体思路:用一个变量保存keyi的位置的变量并把keyi的位置当做坑位,当right(以此为例) //的找到比a[keyi]大的值的时候直接塞到坑的位置,然后让right当做坑,用left来找.... int keyi = left; int tmp = a[keyi]; int pit = leyi;//上面tmp保存那个值就先用那个地方当坑使. while (left < right) { if (a[right] < a[keyi]) { a[pit] = a[right]; pit = right;//右边搞完了,走左边 while (left < right) { if (a[left] > a[keyi]) { a[pit] = a[left]; pit = left; break;//break记得弄因为我们这时又把坑位给到了left的位置应该走right了 } left++; } } right--; } a[left] = tmp; return left; }
能看懂代码注释就不用看下面的内容了.
例:4,1,5,2,3,7,6,9,8还是以左边为基准值同时也用左边当坑.
用图来看看吧:
不同的方法得到的排序结果不同但最后的排序结果相同.
