概念
什么是快排？
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 ----百度百科
快排是一种比较算法，能够对任何类型的数据进行排序，只要类型存在“小于”的关系定义。快排采用分而治之的策略，每一次排序，都选择一个数作为支点，然后将大于支点数的放在支点数后，小于支点数的置于支点数前。对支点数前后两部分数据重复执行之前过程，直至整个数组有序。支点数的选择有多种策略，可以总是选择最后一个数，或第一个数，或任意选择数组中的某一个数，或选择数组的中位数。
总是选择最后一个数作为支点数的代码: (in C++)
// Always pick the last one as the pivot
int partition(vector<int>& vec, int low, int high){
int pivot = vec[high]; // pivot element
int i = low - 1; // smaller element index
for(int j = low; j < high; j++){
// if current element is less than or equal to the pivot
if(vec[j] <= pivot){
i++;
if(i != j) swap(vec[i],vec[j]);
}
}
swap(vec[i+1],vec[high]);
return i+1;
}
// Using Recursion
void quickSort(vector<int>& vec, int low, int high){
if(low < high){
int pi = partition(vec,low,high);
// Separately sort elements before
// partition and after partition
quickSort(vec, low, pi - 1);
quickSort(vec, pi + 1, high);
}
}
// Iteratively with Stack
void quickSort(vector<int>& vec, int low, int high){
stack<int> s;
s.push(low);
s.push(high);
while(!s.empty()){
high = s.top();
s.pop();
low = s.top();
s.pop();
int pi = partition(vec,low,high);
// Separately sort elements before
// partition and after partition
if(pi - 1 > low){
s.push(low);
s.push(pi-1);
}
if(pi + 1 < high){
s.push(pi+1);
s.push(high);
}
}
}
分析：
时间复杂度:
T(n) = T(k) + T(n-k-1) + Θ(n)
n为数组大小，k为小于pivot的数字个数。
- worst case: 此种情况发生在总是选择最小或最大的数作为pivot。如总是选择最后一个数作为pivot的情形下，当数组本身已经是sorted情况不过是倒序时，时间复杂度是O(n*n)。
- best case: 当总是选择middle元素作为支点数的情形，时间复杂度是O(n*Logn)。
