【面试问题实践】三路快排的partition算法不仅仅能用在实现快排上哦：）

来源：3-8 三路快速排序法

liuyubobobo

2016-12-26

在这一小节，我们介绍了三路快排的partition算法。事实上，这个partition的算法思路不一定只用于实现快排哦。有兴趣的同学，可以看看这个面试题。取自 Microsoft ， Facebook 的面试题哦。

https://leetcode.com/problems/sort-colors/

请大家不要仅仅思考，一定落实到编码。为大家提供原始OJ链接，也是为了方便大家实践，来检验自己的掌握水平哦。另外，leetcode支持诸多语言，包括最新的swift。所以请不要被语言束缚。用你喜欢的熟悉的顺手的语言，来解决问题吧！

题目大意：给出一个有n个元素的数组。这n个元素的取值只有0，1，2三种。为这个数组排序。

提示：有些同学可能能使用计数排序的思路，扫描两遍数组得到答案。想想看，能不能只扫描一遍数组得到答案？

大家加油！：）

注：和这个课程相关的额外分享，我将根据分享内容对应的小节，放在相应的课程小节问答区。如果想要获得课程完整分享内容的同学，可以加入课程的官方群，在群文件中找到哦。大家加油：）

=====

该问题的题解，见这里：http://www.imooc.com/article/16141

写回答

3回答

Lawrence

2017-03-27

template<typename T>
void QuickSort3ways2(T arr[], int n)
{
 srand(NULL);
 Sub_QuickSort3ways2(arr, 0, n - 1);
}
template<typename T>
void Sub_QuickSort3ways2(T arr[], int L, int R)
{
 if (R - L <= 15)
 {
  InsertionSort(arr, L, R);
  return;
 }
 int x = rand() % (R - L + 1) + L;
 swap(arr[L], arr[x]);
 T v = arr[L];
 int lt = L;
 int gt = R + 1;
 int i = L + 1;
 while (i < gt)
 {
  if (arr[i] < v)
  {
   swap(arr[i], arr[lt + 1]);
   lt++;
   i++;
  }
  else if (arr[i] > v)
  {
   if (arr[gt - 1] <= v)
   {
    swap(arr[i], arr[gt - 1]);
    if (arr[gt - 1] < v)
     lt++;
    else
     i++;
   }
   
   //swap(arr[i], arr[gt - 1]);
   gt--;
  }
  else
   i++;
 }
 swap(arr[L], arr[lt]);
 Sub_QuickSort3ways(arr, L, lt - 1);
 Sub_QuickSort3ways(arr, gt, R);
}

对三路快排在arr[gt-1]>v的情况做细分处理，可以略微提升一下这个算法的性能 //szimg.mukewang.com/58d8e0fe0001e65704120237.jpg