排序算法-快速排序

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

起源

东尼·霍尔(C.R.A.Hoare)于1962年提出。

思想

分治法

时间复杂度

平摊O(N*logN),最坏O(n²)

最坏情况何时发生?

数组已是排好序的(无论是正序,还是倒序,或者相等)。

步骤

  • 先从数列中取出一个数作为基准数。
  • 分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
  • 再对左右区间重复第二步,直到各区间只有一个数。  

动图演示

代码实现

int Paritition(int num[], int l, int r) {
  int pivot = num[l];
  while (l < r) {
    while (l < r && num[r] >= pivot) {
      --r;
    }
    num[l] = num[r];
    while (l < r && num[l] <= pivot) {
      ++l;
    }
    num[r] = num[l];
  }
  num[l] = pivot;

  return l;
}

void QuikSort(int num[], int l, int r) {
  if (l < r) {
    int pivot = Paritition(num, l, r);
    QuikSort(num, l, pivot - 1);
    QuikSort(num, pivot + 1, r);
  }
}

void main(){
  int num[5] = {1,5,4,2,3};
  QuikSort(num,0,4);
}