快速排序（取中位数法）

#include<iostream>#include<algorithm>#include<iterator>using namespace std;// 求首元素、中间元素和尾元素的中位数，将中位数与首元素交换位置inline void medianAsPivot(int arr[], const int& left, const int& right){const int middle = left+(right-left)>>1;const int l = arr[left];const int m = arr[middle];const int r = arr[right];if(l<=m&&m<=r || r<=m&&m<=l) swap(arr[left], arr[middle]);if(l<=r&&r<=m || m<=r&&r<=l) swap(arr[left], arr[right]); }// 求分区位置i，该位置左边的所有元素小于该元素，右边的所有元素不小于该元素// 同时，，求得的这个位置的元素值为第n-i大元素int partition(int arr[], const int& left, const int& right){if(left < right){medianAsPivot(arr, left, right);int i = left;int j = right;int key = arr[i]; // 首元素作为pivotwhile(i < j){while(i<j && arr[j]>=key) j–;if(i < j) arr[i++] = arr[j];while(i<j && arr[i]<key) i++;if(i < j) arr[j–] = arr[i];}arr[i] = key;return i;}return left;}// 快速排序递归实现void quickSort(int arr[], const int& left, const int& right){if(left < right){int p = partition(arr, left, right);quickSort(arr, left, p-1);quickSort(arr, p+1, right);}}int main(){int arr[] = {6, 8, 9, 2, 1, 4, 3, 2, 4, 7, 0, 5, 6};int size = sizeof(arr)/sizeof(int);copy(arr, arr+size, ostream_iterator<int>(cout, " "));cout<<endl;quickSort(arr, 0, size-1);copy(arr, arr+size, ostream_iterator<int>(cout, " "));cout<<endl;random_shuffle(arr, arr+size);copy(arr, arr+size, ostream_iterator<int>(cout, " "));cout<<endl;quickSort(arr, 0, size-1);copy(arr, arr+size, ostream_iterator<int>(cout, " "));cout<<endl;return 0;}

请让我们从容面对这离别之后的离别。