快排的最坏情况？想要避免除了一开始随机打乱还有什么好的办法？

三位取中？

每次在取pivot时， 产生随机数去取~

STL的sort函数了解一下？

优化partition算法

块排最重要的就是partition()操作，如果是普通的快速排序，暂且叫partition(),可以采用随机区标志位进行划分；双路快排就是出现=标志位很多时，进行的优化；三路快排就是解决=标志位很多的情况。 具体partition()函数如下： template<typename T> int __partion(T arr[],int l,int r) {     int index=rand()%(r-l+1)+l;     swap(arr[l],arr[index]);     T temp=arr[l];     int j=l;     for(int i=l+1;i<=r;i++)     {         if(arr[i]<temp)         {              swap(arr[j+1],arr[i]);              j++;         }     }     swap(arr[l],arr[j]);     return j; } template<typename T> int __partion2(T arr[],int l,int r) {     int index=rand()%(r-l+1)+l;     swap(arr[l],arr[index]);     T v=arr[l];     int i=l+1;     int j=r;     while(true)     {         while(i<=r&&arr[i]<=v)             i++;         while(j>l&&arr[j]>=v)             j--;         if(i<j)             swap(arr[i++],arr[j--]);         else             break;     }     swap(arr[l],arr[j]);     return j; } 三路快排就不写了，可以去看数据结构与算法。 其实排序算法中，到小范围的排序都可以采用插入排序，这也是一步优化。

BFPRT 算法了解，这样的选择划分值好像比较好。

在划分到N小于一定的数据值时  由于复杂度常数项的影响变得更加显著 可以使用其他算法替代

主元取中位数，三向切分，快速三向切分，小数组使用插入排序，这些都是优化

返回值的时候返回两个数。等于最后一个数开始的位置与等于最后的一个数的位置