devbox
我家自动化
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构-排序：快速排序的多种实现方法（Hoare，挖坑，双指针，非递归）_快速排序用队列实现

作者：我家自动化 | 2024-04-27 22:32:07

赞

踩

快速排序用队列实现

快速排序是交换排序的一种，这是因为快速排序的核心还是交换两个合适的元素。快排有很多实现方法，类似更新迭代，但是核心思想都一样。Hoare法，挖坑法，前后指针法，非递归法（栈实现，队列实现）  下面一一介绍。

目录

快速排序，Hoare版本：

快速排序，挖坑法：

快速排序，前后指针法，带三数取中等优化：

快速排序非递归（栈实现）

快速排序非递归（队列实现）

快速排序，Hoare版本：

Hoare 左闭右闭

  1. void QuickSort(int* arr, int begin, int end) {  // [begin, end]
  2.     int left = begin;
  3.     int right = end;
  4.     int keyi = begin;  // 设置下标是因为后面要交换数据
  5.     while(left < right) {
  6.         // 右边找小
  7.         while(left < right && arr[right] >= arr[keyi]) {
  8.             right--;
  9.         }
  10.         // 左边找大
  11.         while(left < right && arr[left] <= arr[keyi]) {
  12.             left++;
  13.         }
  14.         // 这里不管是否left<right都交换，等于也无妨。
  15.         swap(arr[left], arr[right]);
  16.     }
  17.     // 这里出循环之后，一定符合left == right。
  18.     swap(arr[keyi],arr[left]);
  19.     // [begin, left-1] left [left+1, end]
  20.     if(left-1>begin)
  21.         QuickSort(arr,begin,left-1);
  22.     if(left+1<end)
  23.         QuickSort(arr,left+1,end);
  24. }

单趟排序目的：找一个key下标的值，单趟排序结束后key的左边比它小，右边比它大，这样为一次单趟排序。

这里暂时先不使用三数取中的优化，先找一个key值（一般为最左边或最右边），这里默认为left下标处的值。然后定义left，right。右边找小于key的值，左边找大于key的值，且必须是right先走。（这里有原因，后序解答）。当右边找到小，左边找到大，交换左右下标的值，使得大值去右边，小值去左边。当left和right相遇之后循环退出，再交换key下标的值，和相遇处的值（这里取left和right都可以） 至此，单趟排序结束。

细节1：右边一定要找小于key的值，左边一定要找大于key的值，也就是while循环中必须为arr[right]>=arr[key]。不可以为arr[right] > arr[key]  为了防止如下情况：5 5 1 2 3 4 5 这样就会陷入死循环。

细节2：每个循环都要写left<right这个条件。而不管在任何一个循环处达到了left=right  都可以正常停下，while里的swap也只是没有意义的交换，然后退出大的while。

为什么key在左边必须右边先走？举例所有情况，你会发现，只有右边先走才可以达成相遇处的值<= arr[key]  情况1：右边去遇到左边：此时left或者为初始的key下标。或者是上一次left right交换之后的left。初始的key说明key右边的所有值都大于等于key下标的值，相遇之后相当于自己交换。而上一次交换之后的left一定小于key。   所以综上情况1的两种可能，都可以达到相遇处的值小于等于arr[key]（事实上可能性1的概率很小）  这样交换之后才可以保证key左边的值小于它，右边的值大于他。（左边做key右边先走，右边做key左边先走）

单趟排序结束后，进行递归，这里类似于二叉树的前序遍历：对根节点进行处理，然后递归左子树，左子树递归完递归右子树。而这里是递归左区间，然后递归右区间。当左右区间都有序了，整体也就有序了。

不过要注意，这里是递归左区间，然后左区间的左区间，无限递归下去，当某一次左区间的元素个数<=1 时，停止递归，再递归右区间。可以想象二叉树的前序遍历。

注意QuickSort的left和right  是左闭右闭形式的。也就使得，单趟排序之后，整个区间被划分为了        [begin, left-1] left [left+1, end]  也就得出了递归的条件： left-1 > begin   left+1 < end。左闭右开的话情况类似，需要改变右递归条件为 left+1 < end-1 注意这里的left的值是交换之后的最初的key的值。你也可以把left赋值给key  key = left  然后用key去划分这个区间。

讲的有点过于详细了。。。。。 

快速排序性能总结：

时间复杂度：O(N*LogN)

空间复杂度：O(LogN)

稳定性：不稳定。

Hoare 左闭右开：

  1. void QuickSort(int* arr, int begin, int end) {  // [begin, end)
  2.     // 对数组arr的begin到end下标的元素进行排序
  3.     // 先进行单趟排序
  4.     int left = begin;;
  5.     int right = end-1;
  6.     int keyIndex = left;
  7.     while(left < right) {
  8.         while(left < right && arr[right] <= arr[keyIndex]) {
  9.             right--;
  10.         }
  11.         while(left < right && arr[left] >= arr[keyIndex]) {
  12.             left++;
  13.         }
  14.         // 这里可能相遇了，可能没相遇。即使相遇了交换也不影响
  15.         swap(arr[left], arr[right]);
  16.     }
  17.     swap(arr[keyIndex], arr[left]);
  18.     keyIndex = left;
  19.     // 保证左面至少有两个元素才进行递归。
  20.     if(keyIndex-1 > begin)
  21.         QuickSort(arr,begin,keyIndex);
  22.     // 保证右面至少有两个元素才进行递归。
  23.     if(left+1<end-1)
  24.         QuickSort(arr,keyIndex+1,end);
  25. }

改变的仅仅是right的取值还有右递归的条件。 

快速排序，挖坑法：

  1. void QuickSort(int* arr,int begin, int end) { // [begin, end]
  2.     int left = begin, right = end;  // left和right为范围，因为最后还要使用begin和end进行递归。
  3.     int key = arr[left];  // arr[begin] 保存元素值而不是下标是因为left下标的值会被改变。单趟排序的最后要把这个元素值放入最后一个坑中。
  4.     while(left < right) {
  5.         // 右边找小，填入坑中
  6.         while(left < right && arr[right] >= key) {
  7.             right--;
  8.         }
  9.         // 这里left right是否相遇都无所谓。相遇就是自赋值，不相遇正和目的。
  10.         arr[left] = arr[right];
  11.         // 左边找大， 填入坑中
  12.         while(left < right && arr[left] <= key) {
  13.             left++;
  14.         }
  15.         // 这里left right是否相遇都无所谓。相遇就是自赋值，不相遇正和目的。
  16.         arr[right] = arr[left];
  17.     }
  18.     arr[left] = key; // 这个时候其实left right都是一样的。
  19.     // 下面的left就是最终的key值所在位置。
  20.     if(left-1>begin)
  21.         QuickSort(arr,begin,left-1);
  22.     if(left+1<end)
  23.         QuickSort(arr,left+1,end);
  24. }

这里的key是左下标的值，而不是左下标。因为这里的值会被覆盖。

总结：右边找小，填入左边，左边找大，填入右边。相遇之后，将相遇点的值改为key。然后递归

快速排序，前后指针法，带三数取中等优化：

  1. int GetMiddleIndex(int* arr, int begin, int end) { // 注意，写的是左闭右闭的版本 [begin,end]
  2.     int mid = (begin+end)/2;
  3.     if(arr[begin] < arr[end]) {
  4.         if(arr[mid] < arr[begin]) {
  5.             return begin;
  6.         }else if(arr[end] < arr[mid]) {
  7.             return end;
  8.         }else {
  9.             return mid;
  10.         }
  11.     }else {
  12.         if(arr[begin] < arr[mid]) {
  13.             return begin;
  14.         }else if(arr[end] > arr[mid]) {
  15.             return end;
  16.         }else {
  17.             return mid;
  18.         }
  19.     }
  20. }
  21. // 前后指针法
  22. void QuickSort(int* arr, int begin, int end) {  // [begin, end]
  23.     if(end - begin > 12) {
  24.         int prev = begin;
  25.         int cur = begin + 1;
  26.         // 三数取中
  27.         int mid = GetMiddleIndex(arr, begin, end);
  28.         swap(arr[mid], arr[begin]);
  29.         // 三数取中结束
  30.         int keyIndex = begin; // 这里保存下标而不是元素值，是因为最后要进行一次交换操作。
  31.         while (cur <= end) {
  32.             // 前方为真才++prev。
  33. //            if (arr[cur] < arr[keyIndex] && ++prev != cur) {
  34. //                swap(arr[prev], arr[cur]);
  35. //            }
  36.             if(arr[cur] < arr[keyIndex]) {
  37.                 ++prev;
  38.                 swap(arr[cur], arr[prev]);
  39.             }
  40.             // 小于key值，就处理。处理完移动cur
  41.             // 不小于key值，直接移动cur。
  42.             ++cur;
  43.         }
  44.         swap(arr[keyIndex], arr[prev]);
  45.         // 此时prev就是那个分割线，并且这是一种前闭后开的形式
  46.         if (prev - 1 > begin) {
  47.             QuickSort(arr, begin, prev-1);
  48.         }
  49.         if (prev + 1 < end) {
  50.             QuickSort(arr, prev + 1, end);
  51.         }
  52.     }else {
  53.         InsertSort(arr+begin, end-begin+1);
  54.     }
  55. }

 直接看if条件里面的即可。

cur一直往前走，遇到小于keyIndex下标的值，则停下处理。循环结束后交换prev和keyIndex下标处的值。

上方为单趟排序，之后进行前序递归即可。

快速排序非递归（栈实现）

  1. // 快排改非递归用循环很难，可以在堆上创建数据结构：栈 来模拟递归过程。(因为堆很大
  2. void QuickSortNoRecursionStack(int* arr, int begin, int end)  // recursion  [begin, end]
  3. {
  4.     stack<int> st;
  5.     st.push(end);
  6.     st.push(begin);
  7.     while(!st.empty()) {
  8.         int left = st.top();
  9.         st.pop();
  10.         int right = st.top();
  11.         st.pop();
  12.         // 这里就是一个全新的范围，进行单趟排序即可。
  13.         int prev = left;
  14.         int cur = left+1;
  15.         int mid = GetMiddleIndex(arr,left,right);
  16.         swap(arr[left], arr[mid]);
  17.         int keyIndex = left;
  18.         while(cur <= right) {
  19.             if(arr[cur] < arr[keyIndex] && ++prev != cur) {
  20.                 swap(arr[prev], arr[cur]);
  21.             }
  22.             cur++;
  23.         }
  24.         swap(arr[keyIndex], arr[prev]);
  25.         // 单趟排序结束
  26.         // [begin, prev-1] prev [prev+1, end]
  27.         if(prev+1 < right) {
  28.             st.push(right);
  29.             st.push(prev+1);
  30.         }
  31.         if(prev-1 > left) {
  32.             st.push(prev-1);
  33.             st.push(left);
  34.         }
  35.     }
  36. }

其实非常简单，只需要每次确定好left和right的范围即可。确定好之后进行单趟排序。

之后按顺序压栈right prev+1  prev-1 left  然后出栈时，即可完全模拟递归的前序递归。其实先压左边的范围，后压右边也可以。只是递归的顺序改变了。此处的单趟排序用Hoare 挖坑 快慢指针方法之一即可，都可以。  

注意后面压栈时，使用的是left right  而不是begin end。因为每次单趟排序之后，整体的范围是left right 而不是 begin end

快速排序非递归（队列实现）

  1. void QuickSortNoRecursionQueue(int* arr, int begin, int end) {
  2.     queue<int> q;
  3.     q.push(begin);
  4.     q.push(end);
  5.     while(!q.empty()) {
  6.         int left = q.front();
  7.         q.pop();
  8.         int right = q.front();
  9.         q.pop();
  10.         int prev = left;
  11.         int cur = left+1;
  12.         int mid = GetMiddleIndex(arr,left,right);
  13.         swap(arr[left], arr[mid]);
  14.         int keyIndex = left;
  15.         while(cur <= right) {
  16.             if(arr[cur] < arr[keyIndex] && ++prev != cur) {
  17.                 swap(arr[prev], arr[cur]);
  18.             }
  19.             ++cur;
  20.         }
  21.         swap(arr[keyIndex], arr[prev]);
  22.         // 单趟完成
  23.         // [left, prev-1] prev [prev+1, right]
  24.         if(prev-1 > left) {
  25.             q.push(left);
  26.             q.push(prev-1);
  27.         }
  28.         if(prev+1 < right) {
  29.             q.push(prev+1);
  30.             q.push(right);
  31.         }
  32.     }
  33. }

使用队列实现快排，这里类似二叉树的层序遍历，而不是前序遍历了。

因为一次单趟之后，有左右两个区间（可能），而这里调用front 和 pop时，出左范围，入左范围的两个子区间，再出右范围，入右范围的两个子区间。之后是四个区间依次排序，依次入区间，最终变为8个区间（可能）。

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

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号