QuickSort 快排知识要点及一些改进

概念

什么是快排？

快速排序由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)。