快速排序是使用的最廣得排序算法.優(yōu)點:簡單,適用于不同的輸入數(shù)據(jù),在一般應(yīng)用中比排序算法快.
是一種原地排序(只需要一個很小的輔助棧),排序時間與N 數(shù)組成NLgN成正比.而且內(nèi)循環(huán)比大多數(shù)算法都要少.
快速排序是一種分治的排序算法.把數(shù)組一分為二,然后分別對兩半進行排序.只有一分為二,時間復(fù)雜度才有可能 達到lgN→log2N.
具體算法過程:

• 1.查找一個拆分點K,使得把整個數(shù)組分成兩塊.左邊都小于K,右邊值都大于等于K
• 2.對左邊,右邊分別排序.

問題:
如何找中軸?
通常把第一個數(shù)作為中軸,目的是要把第一個數(shù)排序到中間位置,使得 左邊的數(shù)都小于它,右邊的數(shù)都大于它.

2018-04-07 20-01-49 的屏幕截圖.png

2018-04-07 20-02-25 的屏幕截圖.png

拆分中軸的算法如下:

public class QuikSort{
public void sort(int [] arr,int low,int high){
   if(arr==null||arr.length==0){
      return;
   }
   int mid=partion(arr,0,arr.length-1);
   sort(arr,0,mid-1);
   sort(arr,mid+1,high);
}
private int partition(int[] arr,int low,int high){
    while(low<high){
       while(low<high&&arr[high]>arr[low]){
              high--;
        }
        if(low<high){
           swap(arr,low,high);
           low++;
         }
       while(low<high&&arr[low]<arr[high]){
           low++;
       }
       if(low<high){
        swap(arr,low,high);
        high--;
       }
    }
}
private void swap(int [] a,int left,int right){
     a[left]^=a[right];
     a[right]^=a[left];
     a[left]^=a[right];
}
}

性能分析

命題K:
將長度為N的無重復(fù)數(shù)組排序,快速排序的平均需要 2NlnN次比較,(1/6的交換).在實際數(shù)組中元素重復(fù),精確的分析會十分復(fù)雜,但是在重復(fù)的元素,其平均比較次數(shù)不會大于CN.

盡管快速排序有眾多優(yōu)點,但是有些潛在的缺點:

• 1.切分不平衡是效率會極低

命題:
快速排序最多需要N2/2次比較,但是隨機打亂數(shù)組能預(yù)防這種情況.
經(jīng)過測試,
對于5000000個整數(shù)的排序 時間平均在 800~900毫秒之內(nèi)..速度驚人.
幾十萬級別排序在幾十毫秒級別

• 2.對于小數(shù)組,改用插入排序.

因為遞歸,小數(shù)組在快速排序中也會遞歸調(diào)用自己.對于設(shè)置這個常數(shù) 一般在5-15 之間.

• 3.對于元素重復(fù)率高的時候,三取樣切分/熵最優(yōu)的排序

例如一個全部是重復(fù)元素的子數(shù)組不需要排序,但我們的普通算法還是會將他繼續(xù)切分成更小的數(shù)組排序,這里面就有改進的空間.