当前位置:   article > 正文

【数据结构】快速排序

【数据结构】快速排序

快排其实本质就是把我们这个数放到它应该所在的位置上。就比如7,1,2,3,4,5,那么7是不是最后要排的位置要在最后的那个位置上。

我们实现快排有三种方式,分别是霍尔大佬的方法,挖坑法,前后指针法,

一、霍尔大佬的方法

就拿7,5,4,9,3,1,6来举例。

1.首先我们要选一个基准值,我们就取第一位。然后定义一个i指向最左边,定义一个j,指向右边。

2.然后我们先从右边找,然后再从左边找。(为什么?下面有解释)

我们思考一下,要让key的值处于它本该所在的位置上,那么它右边的值是不是要比它大。它左边的值是不是要比它小。所以我们右边是要找出比key小的,放到key的左边,左边要找比key大的,放到key的右边。

我们开始从右边走,找到了6比key = 7小,左边开始找,找到9比key = 7大,然后交换它们的值。

找到位置

交换值

接着继续右边找小,左边找大。i  < j

最后我们发现i == j,此时找到的值肯定是比key小的。(下面再做解释)

最后我们在相遇的位置和key交换,即完成了一次排序。

接着我们通过递归,去将key的左边排,将key的右边排。划分成一个个小区间。

划分到最后,我们就会发现left  > = right,那么这个就是我们递归的出口。

代码如下:

首先我们首先一个每个区间的步骤

  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. void QuickSort(vector<int>& a,int left, int right)
  5. {
  6. int i = left;
  7. int j = right;
  8. int keyi = left;
  9. while(i < j)
  10. {
  11. //右边找小,循环结束j指向的位置就是比key小的位置
  12. while(i < j && a[j] >= a[keyi]) j--;
  13. //左边找大,循环结束i指向比key大的位置
  14. while(i < j && a[i] <= a[keyi]) i++;
  15. //交换它们的值,使比key大的在key右边,比key小的在左边
  16. swap(a[i],a[j]);
  17. }
  18. //循环结束,i和j相遇,相遇位置必然比key小
  19. swap(a[i],a[keyi]);
  20. .....
  21. 划分小区间,递归
  22. }

然后我们一次排序完,要划分区间,分别是key左边的区间,key右边的区间。然后递归,递归出口是left大于等于right

  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. void QuickSort(vector<int>& a,int left, int right)
  5. {
  6. if(left >= right) return;
  7. int i = left;
  8. int j = right;
  9. int keyi = left;
  10. while(i < j)
  11. {
  12. //右边找小,循环结束j指向的位置就是比key小的位置
  13. while(i < j && a[j] >= a[keyi]) j--;
  14. //左边找大,循环结束i指向比key大的位置
  15. while(i < j && a[i] <= a[keyi]) i++;
  16. //交换它们的值,使比key大的在key右边,比key小的在左边
  17. swap(a[i],a[j]);
  18. }
  19. //循环结束,i和j相遇,相遇位置必然比key小
  20. swap(a[i],a[keyi]);
  21. .....
  22. 划分小区间,递归
  23. QuickSort(a, left , i - 1);
  24. QuickSort(a, i + 1, right);
  25. }

这就是一次完整的霍尔大佬的快排方法。

二、为什么要先右后左?快排的缺陷有哪些?

首先,我们先说结论,如果选左边为key,就要先走右边,最后循环结束i指向的位置必然比key小。如果右边为key,那么就要先走左边,最后循环结束i指向的位置必然大于key。

为什么左边为key,先走右边,最后位置必然比key小呢?

我们先来想想,先走右边,无非就是两种情况。(R是right,L是left)

第一种情况:R找到了小,到L找大,但是没找到,L遇到R。那么最后的位置是不是就是R的位置,R的位置是一个比key小的位置。

第二种情况:R找小,没找到,直接到L的位置,这种情况下,有两种结果,第一种结果,就是L还没有动,这时候L位置就是key的位置,key和key自己交换,没什么影响。第二种结果,就是R第一次找到了小,L找到了大,然后它们完成了交换,此时还未相遇,交换后,L位置是比key小的位置,然后R继续找小,没找到,遇到了L,那么L此时位置上的值比key小的。

所以两种情况下,最后相遇时,i位置上的值都是比key小的,我们key选左边,左边刚好需要的就是比key小的,直接交换就可以了。


那么快排是最好的排序算法吗?是否所有场景都可以用?

我们可以仔细思考思考,如果我们要排序的数组是个降序的,但我们又想排升序呢?那么快排每次是不是都要让我们的第一个key跑到最后一个位置上,然后key的右区间是没有的,就一直划分成左区间,这时候的效率是不是非常低,会导致右边区间不起作用,时间复杂度直接来到了O(n^2),数据量大的时候,还可能会造成栈溢出。

那么我们要如何解决?首先,引起这个问题出现的原因是我们key的选择,我们key只选了最左边,如果我们取的不是最左边,而是其他位置的值,那么我们的右区间就可以发挥作用起来了。

这里我们提供了两种选key的方法,第一种是随机数法,就是取一个随机数rand % (区间的长度)+left,就可以得到一个随机位置的key。但这种方法不是很稳定。第二种方法是我们的三数取中法,就是left , right, mid这三个对应位置上的数取大小在中间的作为key。

实现方法也很简单,无非就是利用if语句来判断大小即可。

  1. int Getmid(vector<int>& a,int left,int right)
  2. {
  3. int mid = (left + right) / 2;
  4. if(a[left] > a[right])
  5. {
  6. if(a[left] < a[mid])
  7. return left;
  8. else
  9. {
  10. if(a[mid] > a[right])
  11. return mid;
  12. else
  13. return right;
  14. }
  15. }
  16. else
  17. {
  18. if(a[right] < a[mid])
  19. return right;
  20. else
  21. {
  22. if(a[left] > a[mid])
  23. return left;
  24. else
  25. return mid;
  26. }
  27. }
  28. }

三、挖坑法

在我看来,挖坑法和霍尔大佬的方法差不多,它就是将key的值存好,然后将key位置视作一个坑,然后右边找小,将值填入那个坑,然后右边小的那个位置就变成了新的坑,然后左边找大,将大的填入那个坑,然后左边位置又变成了新的坑。

代码如下

  1. void _QuickSort3(vector<int>& a, int left, int right)
  2. {
  3. if (left >= right) return;
  4. int i = left;
  5. int j = right;
  6. int key = a[left];
  7. int hole = left;
  8. while (i < j)
  9. {
  10. //右边找小
  11. while (i < j && a[j] >= key) j--;
  12. a[hole] = a[j];
  13. hole = j;
  14. //左边找大
  15. while (i < j && a[i] <= key) i++;
  16. a[hole] = a[i];
  17. hole = i;
  18. }
  19. a[hole] = key;
  20. _QuickSort3(a, left, i - 1);
  21. _QuickSort3(a, i + 1, right);
  22. }

三、前后指针法

就是定义一个prev指针,和一个cur指针,然后cur指针走,,如果a[cur]  > key,那么就只++cur,如果a[cur] < key,那么就先++prev,然后再交换a[prev],a[cur],然后++cur,直到cur走完数组。

代码如下:

  1. void _QuickSort4(vector<int>& a, int left, int right)
  2. {
  3. if (left >= right) return;
  4. int prev = left;
  5. int cur = left + 1;
  6. int key = a[left];
  7. while (cur <= right)
  8. {
  9. if (a[cur] < key)
  10. {
  11. ++prev;
  12. swap(a[prev], a[cur]);
  13. ++cur;
  14. }
  15. else
  16. {
  17. ++cur;
  18. }
  19. }
  20. swap(a[prev], a[left]);
  21. _QuickSort4(a, left, prev-1);
  22. _QuickSort4(a, prev + 1, right);
  23. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/代码探险家/article/detail/820369
推荐阅读
相关标签
  

闽ICP备14008679号