数据机构之排序算法 ————快排

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据机构之排序算法 ————快排，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3347字，纯文字阅读大概需要5分钟。

内容图文

快排：快速排序，是一种基于二分思想的快速，有效的排序方式，也是实际使用场景中经常会用到的排序算法，我们有必要了解他们；
注意本篇博客不涉及原理讨论，只提供一种实现的代码设计

1. 基于霍尔划分的快速排序

   int haroPart(int* array, int begin, int end)
   {
   int start = begin;//保留一下最初的begin，逻辑最后需要交换
   //先从后往前找，第一个比begin位置小的
   while (begin < end)
   {
       while (begin < end && array[end] >= array[start])
       {
           --end;
       }//当前end所在位置一定比begin位置小
       //从前往后找，第一个比begin位置大的值
       while (begin < end && array[begin] < array[start])
       {
           ++begin;
       }
       Swap(array, begin, end);
   }
   
   if (begin == end)
   {
   
       Swap(array, start, begin);
   }
   return begin;
   }

   2.基于挖坑法的快速排序

   int digPart(int* array, int begin, int end)
   {
   int key = array[begin];
   while (begin < end)
   {
       while (begin < end && array[end] >= key)
       {
           --end;
       }
       array[begin] = array[end];
       while (begin < end && array[begin] <= key)
       {
           ++begin;
       }
       array[end] = array[begin];
   
   }
   array[begin] = key;
   return begin;
   }

   3.基于快慢指针（思想）的一种快速排序方法

   int prevPart(int* array, int begin, int end)
   {
   int prev = begin;
   int cur = prev + 1;//最开始的时候，cur是prev的下一个
   int key = array[begin];//基准值
   while (cur <= end)//cur 移动的快，找每次小于基准值得位置
   {
   
           //判断条件是，prev和cur如果不连续的话，说明prev的下一个位置是大于基准值的，
           if (array[cur] < key && ++prev != cur)//这里我们判断条件里写了++prev，其实是有风险的，如果调换判断位置，排序就会失效了
           {
               Swap(array, prev, cur);
           }
           cur++;//处理完成后cur后移，prev已经后移；
   }
   Swap(array, begin, prev);
   return prev;
   }

   4.快排主体--递归写法

   void quickSort(int* array, int begin, int end)
   {
   //cout << "我是霍尔划分哦：" << endl;
   if (begin >= end)
   {
       return;
   }//如果begin位置大于等于end，那排序就结束了，end开始表示最后一个位置
   //获取基准值
   int keyPos = prevPart(array, begin, end);
   //递归写法
   quickSort(array, begin, keyPos - 1);
   quickSort(array, keyPos + 1, end);
   }

---

总结

• 无论哪种划分思想，首先必须注意的是排序后我们要求的序列式哪种，递增or递减，这个对我们的代码设计有很大影响（其实也不能绝对这么说，但是不注意就会出错，划不来）
• 基于霍尔排序的快排思想：

  对于要求为递增序列来说，首先应该循环的，由后向前找到第一个比基准值小的值，再由前向后，找到第一个比基准值大的值，跳出各自遍历的循环，交换找到的这俩个值的位置
  当二者在同一个位置的时候，代表本轮排序完成，交换基准值和这个共同位置，然后执行下一轮快排

• 基于挖坑划分的快排思想：

  对于要求递增结果的排序来说，首先，借助第三变量保留基准值，将本来基准值的位置“挖空”，
  然后循环的，由后向前的找到第一个小于基准值的位置，交换它去“空坑”
  循环的，由前向后找到第一个大于基准值的位置，交换它去“空坑”，这个时候这个空坑位置其实是“我们标记的由后向前寻找的那个位置的索引（各位看官不理解请看代码哦）”
  待到俩个方向的“索引”到同一位置时，将基准值填入其中，一轮快排结束
  循环多轮结束排序

• 基于前后指针思想的快排：（快慢指针）

  对于要求递增序列结果的排序来说，首先是建立索引位置，快指针思想的索引cur，慢指针思想的prev； 加上begin，end
  从前向后找，cur位置是prev的下一个（最开始），prev是begin位置
  循环的，找到下一个比基准值小的，标记为cur， prev是目前已经有序的子序列中最后一个元素的位置
  判断cur 是否为prev的下一个位置，是的话说明俩索引共同移动，不是的话说明，prev的下一个元素就是无序子序列的第一个大于基准值的值，prev指向这个位置，并且将这个位置利用prev和cur进行交换，
  当快索引cur遍历完后，即代表一次快排完成
  多轮完成快排

• 各位宝贝一点要看着代码看总结哦，这样更好理解，现在有了这样的认识，思考一下是不是还可以进行一定的优化呢？问题就留给你们啦
• 欢迎各位大佬批评指正，

内容总结

以上是互联网集市为您收集整理的数据机构之排序算法 ————快排全部内容，希望文章能够帮你解决数据机构之排序算法 ————快排所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---