快速排序
基本思想
通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另一部分的所有資料要小，然後再按此方法對着兩部分資料分别快排。整個排序過程可以遞歸進行，以此達到資料變為有效序列。
假設要排序的數組為A[0],A[1].....A[N-1]，首先任意選取一個資料（通常選用數組的第一個數）作為關鍵資料，然後将所有比他小的數都放到它左邊，所有比它大的數都放到它右邊，這個過程就是一趟快速排序。快速排序不是一種穩定的排序算法，也就是說，多個相同的值的相對位置也許會在算法結束後産生變動。
一趟快速排序算法為：
1.設定兩個變量i、j，排序開始時：i=0，j=arr.lenth-1
2.以第一個元素作為關鍵資料，指派給key，即k=A[i]=A[0]
3.從j開始向前搜尋，j--，直到找到第一個小于key的值A[j]，将A[j]和A[i]交換。
4.從i開始向後搜尋，i++，直到找到第一個大于key的A[i]，将A[i]和A[j]交換。
5.重複步驟3、4直到i=j
關于快速排序的優化：
1.随機選取基準，因為在待排序列是部分有序時，固定選取基準使快排效率低下，要緩解這種情況，就引入了随機選取基點。使用随機數生成函數生成一個随機數rand，随機數的範圍為[left,right]，并用此随機數為下标對應的元素a[rand]作為基點，并與第一個數交換。
優點：這是一種相對安全的政策，由于基點的位置是随機的，那麼産生的分割也不會總是會出現劣質的分割。在整個數組數字完全相等時，仍然是最壞情況，時間複雜度是O(n²)。為什麼是O(n²)？
如果是一個無序數組，[5,4,3,1,2]
第一次排序後：[2,1,3,4,5]
第二次排序：對[2,1]和[4,5]排序，[1,2,3,4,5]排序完成
如果有序呢？
設數組為1，2，3，4，5
第一次排序分為1和[2,3,4,5]
第二次排序後分為了[1,2]和[3,4,5]
第三次分為了[1,2,3]和[4,5]
第四次分為了[1,2,3,4]和[5]
排了n-1次，每次比較n次，是以是n²
2.三數中值分割法
一組序列的中值（中位數）是基點最好的選擇（因為可以将序列平均分為兩個子序列，但是計算一組數組的中位數比較耗時，會減慢快排的效率。但可以通過計算數組的第一個、中間位置、最後一個元素的中值來代替。使用三數分割法消除了預排序輸入的壞情形。
3.在排序序列長度分割到一定大小後，使用插入排序。
優點：對于很小和部分有序的數組，快排效率不如插入排序。（但是經過我測試，在資料量小的時候隻使用快排比使用快排+插入速度更快，在資料量很大時不管是<7還是<15的時候改成插入排序後，程式都運作不出來了）
4.在應對大量重複元素時，我們可以将數組切分為三部分，分别對應小于、等于、大于。
普通快排：
/**
* 普通快排
*/
public class QuickSort2 {
public static void main(String[] args) {
int[] array = {6,1,100,32,22,2,6,321,25,99,54,33,11,54,23,1,5};
quickSort(array,0,array.length-1);
System.out.println(Arrays.toString(array));
}
//每次以第一個元素季即arr[l]為基準，比基準值小的在右，大的在左，
//傳回基準值最終在數組中的位置
private static void quickSort(int[] arr, int l, int r) {
if(l>=r)
return;
int v=arr[l];
int j=l;
//int temp=arr[l];
for(int i=l+1;i<=r;i++) {
//每次循環将小于v的往前換
if(arr[i]<v) {
int temp =arr[j+1];
arr[j+1]=arr[i];
arr[i]=temp;
j++; //arr[j+1]始終是大于v的,arr[j]是最後一個<=v的
}
}
//再将基準值移動到中間
swap(arr,l,j);
//最終j所指的位置就是中間值
quickSort(arr, l, j-1);
quickSort(arr, j+1, r);
}
private static void swap(int[] arr, int i, int j) {
if(i!=j) {
int temp =arr[j];
arr[j]=arr[i];
arr[i]=temp;
}
}
}
雙路挖坑快排代碼一：
public static void quick_sort(int s[],int l,int r){
if(l<r){
int i=adjustArray(s, l, r);
quick_sort(s, l, i-1);
quick_sort(s,i+1,r);
}
}
public static int adjustArray(int s[],int l,int r){
int i=l,j=r;
//s[l]即s[i]就是第一個坑
int x = s[l];
while (i<j){
//從右向左找小于x的數來填充s[l] 循環跳出即為找到
while (i<j && s[j]>x)
j--;
if(i<j){
s[i] = s[j];
i++;
}
//從左向右找大于x的數來填充s[j]
while (i<j && s[i]<x)
i++;
if(i<j){
s[j] = s[i];
j--;
}
}
//退出時i=j,将x填到這個坑中
s[i] = x;
//傳回調整後基準數的位置
return i;
}
上面代碼不夠簡潔，對其進行組合整理後：
public static void quick_sort2(int[] s,int l,int r){
if(l<r){
//左邊的起始位置，右邊的起始位置，第一個數
int i=l,j=r,x=s[l];
while (i<j){
while (i<j && s[j]>x)
j--;
if(i<j){
s[i++] = s[j];
}
while (i<j && s[i]<x)
i++;
if(i<j){
s[j--] = s[i];
}
}
s[i] = x;
quick_sort2(s,l,i-1);
quick_sort2(s,i+1,r);
}
}
雙路快排，經過測試比上面的挖坑快排速度更快：
/**
* 雙路快排寫法2 較挖坑快排速度提升百分之三十左右
*/
public class QuickSort3 {
public static void main(String[] args) {
int[] array = ArrayUtil.bigArray();
long time1 = System.currentTimeMillis();
QuickSort(array,0,array.length-1);
long time2 = System.currentTimeMillis();
System.out.println(time2 - time1);
}
private static void QuickSort(int[] arr, int l, int r) {
if(l>=r)
return;
swap(arr,l,(int)Math.random()*(r-l+1)+l);
//滿足arr[l+1,i)<=v,arr(j,r]>=v
int v=arr[l];
int i=l+1,j=r;
while(true) {
//從左到右掃描，掃描出第一個比base大的元素，然後i停在那裡
while(arr[i]<v&&i<r)//arr[i]不能=v，會導緻v聚集在一邊
i++;
//從右到左掃描，掃描出第一個比base小的元素，然後j停在那裡
while(arr[j]>v&&j>l)
j--;
if(i>=j)
break;
swap(arr, i, j);
i++;
j--;
}
//将基準值交換到合适位置
//因為j能周遊到0，而i隻能從第1個往後找，如果第0個是最小的數，把會最小的數換到中間
swap(arr, l, j);
QuickSort(arr, l, j-1);
QuickSort(arr, j+1, r);
}
private static void swap(int[] arr, int i, int j) {
if(i!=j) {
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
三路快排：
private static void quickSort3Ways(int[] arr,int left,int right){
if (left >= right){
return;
}
//基數
int v = arr[left];
//左邊最接近v且等于v
int lt = left;
//右邊最接近v且等于v
int rt = right;
//從第一個數開始比較
int i=left+1;
while (i<=rt){
if(arr[i] < v){
//把小的數往左放 如果第arr[1]<arr[0] 交換i和0上的數
swap(arr,lt,i);
i++;
lt++;
}else if (arr[i]>v){
//大數放右邊
swap(arr,rt,i);
rt--;
}else{
i++;
}
}
//為什麼這裡是lt-1與rt+1 因為lt與rt索引指向的都是等于中間重複值的索引，中間的重複值已經是中值了
quickSort3Ways(arr,left,lt-1);
quickSort3Ways(arr,rt+1,right);
}
為什麼雙路快排比挖坑快排更快？
測試數組：
72，6，57，88，60，42，83，73，48，85
雙路快排：
第一趟将48和88交換，數組變為：72，6，57，48，60，42，83，73，88，85
第二趟i++到83才找到>72的數，j--到在42才找到小于72的數，這裡選取i和j都行，與72交換。
這裡就·暫且選取j吧，交換後變為：42，6，57，48，60，72，83，73，88，85
這樣比72小的都到了左邊，比72大的都到了右邊
挖坑法：
第一趟排序：temp=72相當于在72挖了個坑，從後向前找j--，找到48小于72，将48放到72 arr[0]=arr[8]
48，6，57，88，60，42，83，73，48，85
然後從前向後找i++，找>48的數，找到88，将88放入48，arr[8]=arr[3]
48，6，57，88，60，42，83，73，88，85
第二趟排序：j--找到42，42放到88 arr[3]=arr[5]
48，6，57，42，60，42，83，73，88，85
break
arr[5]=72
最後排序結果：
48，6，57，42，60，72，83，73，88，85
從結果可以看出，42的位置較上面發生了變化。增加了排序的不穩定性。而且這種排序相當于使用數組中的元素作為了臨時值去臨時儲存數組中别的資料，這種方法每次通路，交換，挖坑都要經過數組，在數組很大的情況下所耗費的資源比用臨時值儲存下資料，然後交換，耗費更多的時間與資源。
經過測試一千萬條資料的排序：
挖坑快排：1321，1260，1299 大約穩定在1.3秒左右
雙路快排：1067，1061，1032 大約穩定在1.0秒左右
一億條資料：
挖坑快排：13004，12893，12996大約13秒左右
雙路快排：10532，10807，10684大約10.5秒左右
三路快排：11038，10098，10571大約10秒吧，較雙路快排慢了一點點。
一億條資料當存在大量重複資料時：
挖坑：9405，10106大約9.7秒
雙路：6464，6456大約6.5秒
三路：4173，4195大約4秒
三路(選取left為基數）：6729，6936大約7秒，可以看出存在大量重複資料時，還是随機選取基數速度更快
時空複雜度
快速排序的平均時間複雜度也是：O(nlogn)
最差是O(n²)即退換為冒泡排序時。最差的情況就是每一次取到的元素就是數組中最小/最大的，這種情況其實就是冒泡排序了(每一次都排好一個元素的順序)
最優的情況下空間複雜度為：O(logn) ；每一次都平分數組的情況
最差的情況下空間複雜度為：O( n ) ；退化為冒泡排序的情況
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)