[算法]快速排序

基本思路

• 分治，将数组分为两半，以k为界限，小于k的在左边，大于k的在右边。

实现

有数组A

• 选A[i]的数值为k
• A[j]与k对比

  • 如果A[j]>=k,j--;

    
    
  • 如果A[j]<k,A[i]与A[j]交换位置,此时k变为了A[j],发生了1次交换
    
• 发生奇数次交换时，A[i]与k作比较(此时的k是A[j])

  • 如果A[i]<=k,i++

    
    

  • 如果A[i]>k，A[i]与A[j]交换位置，此时k变为了A[i]，发生了2次交换
    

    
• 此时变为了偶数次交换 图片.png

• 交换的最终目的，是使得大于k的数在k的右边，小于k的数字k的左边。

  
  
  

  此时整个数组扫了一遍，时间复杂度为O(n)

代码实现

void swap(int &a[i],int &a[j]){
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}


void QuickSort(a[],int s,int e){
    //如果只有一个元素了，就不排序了 
    if(s >= e)
        return;
    int k = a[s];
    int i = s,j =e;
    while(i!=j){
        while(j>i && a[j]>=k)
            j--;
        swap(a[i],a[j]);
        while(j>i && a[i]<=k)
            i++;
        swap(a[i],a[j]);
    } // 处理结束之后，a[i] = k (循环里两次交换) 
    QuickSort(a,s,i-1);
    QuickSort(a,i+1,e);
    
}

复杂度分析

• 一般情况下
  • 每次将数据分为两部分的复杂度为n
  • 对两部分进行排序的复杂度为logn
  • 所以一般情况下复杂度为nlogn
  • 但是无法保证每一次的k都能将数组分为两半
• 那么最坏的情况下，复杂度将为n^2(数组本身就是有序的)
• 一般来说复杂度都为nlogn，如果担心出现数组本身有序的情况，可以先将数组打乱再排序，当然打乱程序的复杂度需要是O(n)或者O(nlogn)。