#ifndef QUICKSORT3_H
#define QUICKSORT3_H
//三路快速排序算法
#include <iostream> 
#include <stdlib.h>

using namespace std;

template <typename T>
void __QuickSort3way(T *arr,int l,int r)
{
 //遞歸的終止條件
 if (l>=r) 
 {
 return;
 }
 else
 {
 //隨機(jī)快速排序選取的隨機(jī)值，為了避免在整體大致有序的情況下產(chǎn)生分組不平衡現(xiàn)象，使算法退化
 int RAND = (rand() % (r - l) + l);
 swap(arr[l], arr[RAND]);
 T v = arr[l];
 //小于v的分組的初始索引
 int lt = l;
 //大于v的分組的初始索引
 int gt = r + 1;
 //等于v的分組的初始索引，并且，此索引是數(shù)組遍歷值的索引
 int i = l + 1;
 while (i<gt)
 {
  //如果遍歷的數(shù)據(jù)小于v
  if (arr[i]<v)
  {
  //將該數(shù)組與第一個等于v的數(shù)據(jù)交換
  swap(arr[lt + 1], arr[i]);
  //維護(hù)小于v的索引和待遍歷的數(shù)據(jù)的索引
  lt++;
  i++;
  }
  //如果數(shù)據(jù)大于v
  else if (arr[i]>v)
  {
  //交換該數(shù)與大于v的第一個數(shù),但是在這里不需要維護(hù)i的索引
  swap(arr[i], arr[gt - 1]);
  gt--;
  }
  else//arr[i]==v
  {
  i++;//直接維護(hù)i的索引
  }
 }
 //最后將數(shù)組第一個數(shù)v和小于v的最后一個數(shù)互換
 swap(arr[l],arr[lt]);

 __QuickSort3way(arr,l,lt);
 __QuickSort3way(arr,gt,r);
 }
}

template <typename T>
void QuickSort3way(T *arr,int n)
{
 __QuickSort3way(arr, 0, n - 1);
}

#endif // !QUICKSORT3_H