概念

什么是快排？

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。 ----百度百科

快排是一種比較算法，能夠?qū)θ魏晤愋偷臄?shù)據(jù)進(jìn)行排序，只要類型存在“小于”的關(guān)系定義?？炫挪捎梅侄沃牟呗裕恳淮闻判?，都選擇一個(gè)數(shù)作為支點(diǎn)，然后將大于支點(diǎn)數(shù)的放在支點(diǎn)數(shù)后，小于支點(diǎn)數(shù)的置于支點(diǎn)數(shù)前。對(duì)支點(diǎn)數(shù)前后兩部分?jǐn)?shù)據(jù)重復(fù)執(zhí)行之前過(guò)程，直至整個(gè)數(shù)組有序。支點(diǎn)數(shù)的選擇有多種策略，可以總是選擇最后一個(gè)數(shù)，或第一個(gè)數(shù)，或任意選擇數(shù)組中的某一個(gè)數(shù)，或選擇數(shù)組的中位數(shù)。

總是選擇最后一個(gè)數(shù)作為支點(diǎn)數(shù)的代碼: (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);
    }
  }
}

分析：

時(shí)間復(fù)雜度:

T(n) = T(k) + T(n-k-1) + Θ(n)

n為數(shù)組大小，k為小于pivot的數(shù)字個(gè)數(shù)。

• worst case: 此種情況發(fā)生在總是選擇最小或最大的數(shù)作為pivot。如總是選擇最后一個(gè)數(shù)作為pivot的情形下，當(dāng)數(shù)組本身已經(jīng)是sorted情況不過(guò)是倒序時(shí)，時(shí)間復(fù)雜度是O(n*n)。
• best case: 當(dāng)總是選擇middle元素作為支點(diǎn)數(shù)的情形，時(shí)間復(fù)雜度是O(n*Logn)。