Quicksort
Quickselect
quickselect is a selection algorithm to find the kth smallest element in an unordered list.
It requires only constant memory overhead if tail call optimization is available, or if eliminating the tail recursion with a loop
Partition Method I
int partition(vector<int> &a, int low, int high){ int pivot=a[low]; while (low<high){ while (low<high && a[high]>=pivot) --high; if (low<high) a[low++]=a[high]; while (low<high && a[low]<=pivot) ++low; if (low<high) a[high--]=a[low]; } a[low] = pivot; return low; } void quicksort(vector<int> &a, int low, int high){ if (low>=high) return; int pivotIndex=partition(a,low,high); quicksort(a,low,pivotIndex-1); quicksort(a,pivotIndex+1,high); } int quickselect(vector<int> &a, int low, int high, int k){ if (low==high) return a[low]; int pivotIndex=partition(a,low,high); int len=pivotIndex-low+1; if (k==len) return a[pivotIndex]; else if (k<len) return quickselect(a,low,pivotIndex-1,k); else return quickselect(a,pivotIndex+1,high,k-len); } int main() { vector<int> a={1,5,8,3,2}; int n=a.size(); quicksort(a,0,n-1); for (auto x:a) cout<<x<<‘ ‘; cout << endl; for (int k=1;k<=n;++k) cout<<quickselect(a,0,n-1,k)<<‘ ‘; return 0; }
Partition Method II
#include <iostream> int partition(vector<int> &a, int low, int high){ int pivot=a[high]; int k=low; for (int i=low;i<high;++i){ if (a[i]<=pivot) swap(a[i],a[k++]); } swap(a[high],a[k]); return k; } void quicksort(vector<int> &a, int low, int high){ if (low>=high) return; int pivotIndex=partition(a,low,high); quicksort(a,low,pivotIndex-1); quicksort(a,pivotIndex+1,high); } int quickselect(vector<int> &a, int low, int high, int k){ if (low==high) return a[low]; int pivotIndex=partition(a,low,high); int len=pivotIndex-low+1; if (k==len) return a[pivotIndex]; else if (k<len) return quickselect(a,low,pivotIndex-1,k); else return quickselect(a,pivotIndex+1,high,k-len); } int main() { vector<int> a={1,5,8,3,2}; int n=a.size(); quicksort(a,0,n-1); for (auto x:a) cout<<x<<‘ ‘; cout << endl; for (int k=1;k<=n;++k) cout<<quickselect(a,0,n-1,k)<<‘ ‘; return 0; }
Time Complexity
Sensitive to the pivot that is chosen.
If the pivot is mid of the array (best case), T(n) = O(n) + 2T(n/2) => O(nlogn) for quicksort, T(n) = O(n) + T(n/2) => O(n) for quickselect.
On average, quicksort O(nlogn), quickselect O(n)
In the worst case, both O(n^2)
原文：https://www.cnblogs.com/hankunyan/p/11741675.html