快速排序

快速排序是在一般情况下时间复杂度为O(nlogn)的排序。

基本思想

通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

算法图解

算法分析

时间复杂度
  1. 当情况为最优时(即基准每一次都在数组中央),则

    比较次数(每一次都比较n次)为:

    T(n) <= 2*T(n/2)+n

    T(n) <= 2(2(T(n/4) + n / 2) + n = 4T(n/4) + 2n

    ……

    T(n) <= nT(1) + nlog2n = O(nlogn)

  2. 但情况最糟糕时

    比较次数 = (n - 1) + (n - 2 ) + … + 2 + 1 = n(n-1) / 2 ;

    O(n^2)

参考代码

void QuickSort(int a[] , int left , int right){
int i = left , j = right , k = a[left];
//利用循环,使基准左边数字均小于基准,右边均大于基准
while(i < j){
while(i < j && a[j] < k) {--j;} //从右向左找到第一个比基准大的数
if(i < j) {a[i++] = a[j] ;}
while(i < j && a[i] > k) {++i;} //从左向右找到第一个比基准大】小的数
if(i < j) {a[j--] = a[i] ;}
}
a[i] = k ;
// 递归调用
QuickSort(a, left, i - 1); // 排序k左边
QuickSort(a, i + 1, right); // 排序k右边
}

谢谢访问