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

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遍历完后，即代表一次快排完成
  多轮完成快排

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

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

原文：https://blog.51cto.com/14632688/2686091