当前位置:   article > 正文

[数据结构] 基于交换的排序 冒泡排序&&快速排序

[数据结构] 基于交换的排序 冒泡排序&&快速排序

标题:[数据结构] 基于交换的排序 冒泡排序&&快速排序

@水墨不写bug


(图片来源于网络) 


目录

(一)冒泡排序

优化后实现:

(二)快速排序

I、实现方法: 

(1)hoare法

hoare法实现快排:

 (2)挖坑法

挖坑法实现:

(3)双指针法 

双指针法实现: 

 II、快速排序复杂度分析:

比较完备的快速排序实现如下:


正文开始:

(一)冒泡排序

 

时间复杂度:O(N^2)

空间复杂度:O(1)

特点:数组接近有序时,可通过优化来提高效率。

稳定性:稳定

冒泡排序:

        基本思想:大数下沉,小数上浮。

        实现思路:从内循环到外循环,从一趟到多趟。

        冒泡排序通过两层循环来实现,内层循环实现其中的一趟遍历,在一趟的遍历中,需要注意要控制好左右区间边界,冒泡排序的实现方式是多样的,无论用何种实现方式,最主要的是控制好边界,以及内外层循环的衔接;以下是一种冒泡排序的写法:

  1. void BubbleSort(vector<int>& nums)
  2. {
  3. int n = nums.size();
  4. for (int j = 0; j < n - 1; ++j)
  5. {
  6. for (int i = 0; i < n - 1 - j; ++i)
  7. {
  8. if (nums[i] > nums[i + 1])
  9. {
  10. ::swap(nums[i], nums[i + 1]);
  11. }
  12. }
  13. }
  14. }

优化:

        如果在一次遍历的过程中,没有进入if()交换,这已经说明数组已经有序,可以直接停止排序。

优化后实现:

  1. void BubbleSort(vector<int>& nums)
  2. {
  3. int n = nums.size();
  4. for (int j = 0; j < n - 1; ++j)
  5. {
  6. int ex = 0;
  7. for (int i = 0; i < n - 1 - j; ++i)
  8. {
  9. if (nums[i] > nums[i + 1])
  10. {
  11. ex = 1;
  12. ::swap(nums[i], nums[i + 1]);
  13. }
  14. }
  15. if (ex == 0)
  16. break;
  17. }
  18. }


(二)快速排序

时间复杂度:O(NlogN)

空间复杂度:

特点:当数据接近有序,比如逆序的时候;或者选取的key在数据中大量存在时,快速排序时间复杂度会退化为O(N^2),这是相当严重的缺陷。

稳定性:不稳定。

        快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。

        基本思想:任取待排序元素序列中的某元素(记为key)作为基准值,按照key值将待排序集合分割成两子序列,左子序列中所有元素均小于基准值key,右子序列中所有元素均大于基准值key。然后递归,左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

        本质就是将数组根据key值分为两部分,一部分比key大,一部分比key小。对于每一个部分,再次进行如上操作,直到数组不可再分为止。这就是递归实现的浅层次的直观理解。但是递归不是本文的重点,关于递归,我会在后面与你分享。 

I、实现方法: 

(1)hoare法

        hoare法是快排的提出者hoare提供的方法,是一种经典的实现方法。

实现原理:

        定义两个下标:左下标L  和  右下标R;

        随机选取一个key值,习惯上我们选择区间的最左侧的元素为key;

        让右下标先走,向左寻找比key小的值,找到后停下来:

 停下来后:

 左下标再向右寻找比key大的值,找到后停下来:

此时,交换两个下标对应的值:

 

接下来继续执行上述步骤(R先走),我展示关键步骤:

 两下标找到要求目标并交换:

直到遇到特殊情况:两下标相遇

 

 这时停止停止循环,将最左侧元素与相遇处的元素交换位置:
即可完成一次二分。

        接下来,对于左右区间再次进行上述操作,直到区间不可再分为止。


但是如何保证相遇处的值一定小于key呢?

对于相遇这个事件,有且仅有两种情况:

只可能是R向左移动遇到L;或者是L向右移动遇到R;

        (1)R向左移动遇到L:有两种可能情况

                        a,第一次R由于没有找到比key小的值,直接一路向左遇到left,此时left就是key,然后执行自己与自己交换:此时相遇的位置的值就是key本身。

                        b,第一次之后R向左遇到L,你要想清楚,在此之前L停止的地方是被交换后的原先R的值(它是比key小的);在这样的前提条件下,R向左移动与L相遇了,说明R没有找到小于key的元素,与L相遇后指向L的比key小的值。

        (2)L向右移动遇到R

                        R先走,在找到比key小的位置停下,在此前提下,L向右移动与R相遇了,L指向R的比key小的值。

hoare法实现快排:

  1. void QuickSort(vector<int>& nums,int left,int right)
  2. {
  3. //递归出口,此时区间不存在或者只有一个值
  4. if (left >= right)
  5. return;
  6. //保存左右下标的值,便于在递归时找到原来的区间边界
  7. int begin = left, end = right;
  8. //keyi来记录左区间的下标
  9. int keyi = left;
  10. while (left < right)
  11. {
  12. //右下标先走,找小
  13. while (left < right && nums[keyi] <= nums[right])
  14. {
  15. --right;
  16. }//左区间再走,找大
  17. while (left < right && nums[left] <= nums[keyi])
  18. {
  19. ++left;
  20. }
  21. ::swap(nums[left], nums[right]);
  22. }//此时一趟完毕,将key与相遇位置交换
  23. ::swap(nums[left], nums[keyi]);
  24. keyi = left;//更新keyi
  25. //递归左右区间
  26. QuickSort(nums, begin, keyi);
  27. QuickSort(nums, keyi+1, end);
  28. }

 (2)挖坑法

实现原理:

        由于左边有坑,所以右下标先走。

        找小,找到后停下来,将找到的值放在坑中,R的位置就成为了新的坑:

此时坑在右边,左边下标先走,找大:

找到后交换,左边又成为新的坑。

以此类推,直到左右相遇,相遇的位置一定是坑,此时将key放到坑中,完成单趟:

依然是左边都是比6小,右边都是比6大,说明没有错误。

挖坑法实现:

  1. void QuickSort_(vector<int>& nums, int left, int right)
  2. {
  3. if (left >= right)
  4. return;
  5. int begin = left, end = right;
  6. int key = nums[left];//记住key的值
  7. int hole = left;//开始挖坑
  8. while (left < right)
  9. {
  10. //右先找比key大的
  11. while (left < right && nums[right] >= key)
  12. right--;
  13. //找到后,填坑,然后挖新坑
  14. nums[hole] = nums[right];
  15. hole = right;
  16. //左找比key小的
  17. while (left < right && nums[left] <= key)
  18. left++;
  19. //找到后,填坑,然后挖新坑
  20. nums[hole] = nums[left];
  21. hole = left;
  22. }
  23. //此时相遇了,把key值放在坑里
  24. nums[hole] = key;
  25. QuickSort_(nums,begin,hole);
  26. QuickSort_(nums,hole + 1,end);
  27. }

(3)双指针法 

 

// 设置前指针prev,指向首元素,遍历指针cur指向第二个元素,
// 接下来cur开始找小,如果没找到小,就一直往前走;

//如果找到小的了,就先停下来,然后prev往前走一步,再和cur交换值,然后cur继续向后,重复上述步骤,
// 最后cur走出数组后,循环终止!此时prev指向的位置和keyi的位置交换。

我们详细看一下过程:

        

双指针法实现: 

  1. void QuickSort__(vector<int>& nums, int left, int right)
  2. {
  3. if (left >= right)
  4. return;
  5. int begin = left, end = right;
  6. int prev = left;
  7. int cur = left + 1;
  8. int keyi = left;
  9. while (cur <= right)//cur走出数组循环停止
  10. {
  11. //cur一直在走,如果遇到比keyi小的,就停下来等perv走一步后交换,再接着走
  12. if (nums[cur] < nums[keyi] && ++prev != cur)
  13. swap(nums[prev], nums[cur]);
  14. cur++;
  15. }
  16. //cur出去后,prev的值和keyi交换
  17. swap(nums[keyi], nums[prev]);
  18. QuickSort__(nums,left,keyi);
  19. QuickSort__(nums,keyi+1,end);
  20. }

 II、快速排序复杂度分析:

        传统的快速排序在处理一些极端问题时会显得无力,接下来我们就来讨论这些极端情况,并且给出应对极端情况的方法:

1.对于选择key不合适的问题:

        在数组元素接近逆序的时候,由于我们总是在区间的最左侧选取key,如果数组接近逆序,这时选取的key无法有效的将数组分为两个等大的数组,这就导致一次只能排序一个元素,这导致快速排序的复杂度会退化为O(N^2),这就需要我们不能随便取key。可以通过随机数法在区间内随机取一个元素作为key即可。

2.关于选择key大量出现的问题:

        如果key大量出现,也会导致上述的情况,一次只能排序一个数,所以我们不能随便分区间,这就要求我们将数组分为三部分,左侧区间都小于key,中间区间则是数值等于key的元素,右侧区间是大于key的数值。

比较完备的快速排序实现如下:

  1. class Solution {
  2. public:
  3. vector<int> sortArray(vector<int>& nums) {
  4. srand(time(NULL));
  5. qsort(nums,0,nums.size()-1);
  6. return nums;
  7. }
  8. void qsort(vector<int>& nums,int l,int r){
  9. //递归出口
  10. if(l >= r) return;
  11. //数组分三块
  12. int key = GetRandom(nums,l,r);
  13. int cur = l,left = l-1,right = r+1;
  14. while(cur < right){
  15. if(nums[cur] < key) swap(nums[++left],nums[cur++]);
  16. else if(nums[cur] == key) cur++;
  17. else swap(nums[--right],nums[cur]);
  18. }
  19. //递归排序子区间
  20. qsort(nums,l,left);
  21. qsort(nums,right,r);
  22. }
  23. int GetRandom(vector<int>& nums,int left,int right){
  24. return nums[ rand() % ( right - left + 1 ) + left];
  25. }
  26. };

 完~

未经作者同意禁止转载

本文内容由网友自发贡献,转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号