Quick Sort 的一个注记

irhwe

"通常快速排序为了效率,都是选取中间点作为枢纽元. 现有从1到15,15个元素.请问这15个元素如何排列,能让选取中点作为枢纽元的排序方案也只能有O(n^2)的效率?"
这个应该怎么做呢？

xds2000

#include <iostream>
using namespace std;

//quickSort algorithm
template < class T >
int partition(T a[], int p, int r){
T x = a[r];
int i = p-1;
  for(int j=p;j<r;j++){
    if(a[j] <= x){
     i++;
     swap(a,a[j]);
    }
  }
  swap(a[i+1], a[r]);
  return i+1;
}


template< class T >
void quickSort(T a[], int p, int r){
if(p < r){
  int q = partition(a, p , r);
  quickSort(a, p , q-1);
  quickSort(a, q+1 , r);
}
}

int main()
{
    int arr[]={23,31,4,9,12,7,59};
    int const n=sizeof(arr)/sizeof(arr[0]);
    for(int i=0;i<n;++i) cout<<"arr["<<i<<"]: "<< arr<<endl;
quickSort(arr,0,n);
cout<<"after sort: "<<endl;
for(int i=0;i<n;++i) cout<<"arr["<<i<<"]: "<< arr<<endl;

}

reiase

学习了