【第22次讨論主題：排序】
1）快排的原理是什麼？快速寫一段核心代碼實作。
快速排序原理:采用的是分治法,同冒泡排序一樣，快速排序也屬于交換排序，通過元素之間的比較 和交換位置來達到排序的目的。
不同的是，冒泡排序在每一輪中隻把1個元素冒泡到數列的一端， 而快速排序則在每一輪挑選一個基準元素，并讓其他比它大的元素移 動到數列一邊，
比它小的元素移動到數列的另一邊，進而把數列拆解 成兩個部分。快速排序算法總體的平均時間複雜度 是O(nlogn)。
基準元素的選擇，以及元素的交換， 都是快速排序的核心問題。
基準元素的選擇：最簡單的方式是選擇數列的第1個元素，或者就是随機選取一個
元素的交換：1. 雙邊循環法。2. 單邊循環法
public static void quickSort(int[] arr, int startIndex,int endIndex){
// 遞歸結束條件：startIndex大于或等于endIndex時
if (startIndex >= endIndex) {
return;
}
//擷取基準元素的下标位置
int pivotIndex = partition(arr, startIndex, endIndex);
// 根據基準元素，分成兩部分進行遞歸排序
//左邊的
quickSort(arr, startIndex, pivotIndex - 1);
//右邊
quickSort(arr, pivotIndex + 1, endIndex);
}
// 單邊循環
private static int partition(int[] arr, int startIndex, int endIndex) {
// 取第1個位置（也可以選擇随機位置）的元素作為基準元素
int pivot = arr[startIndex];
int mark = startIndex;
for(int i=startIndex+1; i<=endIndex; i++){
//獲得小于基準位置元素的元素
if(arr[i]<pivot){
//1.mark 向右移動,使得左側空間變大
mark ++;
//2.交換元素
int p = arr[mark];
arr[mark] = arr[i];
arr[i]=p;
}
}
//最後将 mark 位置的元素和pivot基準元素做交換
arr[startIndex] = arr[mark];
arr[mark] = pivot;
return mark;
} 2) DualPivotQuicksort的sort代碼實作int排序的原理和關鍵步驟。
1. sort(int[] a, int left, int right,int[] work, int workBase, int workLen);中
// 如果排序長度小于286,這直接進入雙軸快排
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
}
//如果排序長度大于67個，進行雙軸快排，否則使用歸并排序。
if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true);
return;
}
2.//sort（sort(int[] a, int left, int right, boolean leftmost)）方法中
//長度小于此值 47 使用插入排序
if (length < INSERTION_SORT_THRESHOLD) {
...
}else{
...大于此值使用快速排序
}
參考連結：
作業：圖解快速排序原理以及java實作
https://blog.csdn.net/u010430495/article/details/88388057
https://blog.csdn.net/fjtooo/article/details/90244584
Dual-Pivot QuickSort
https://www.jianshu.com/p/2c6f79e8ce6e 快速排序算法
https://blog.csdn.net/Backee/article/details/90048052 單軸快排（SinglePivotQuickSort）和雙軸快排（DualPivotQuickSort）及其JAVA實作
https://blog.csdn.net/holmofy/article/details/70245895 常見排序算法及JAVA實作
==========優秀同學的回答：
姚子健
12日15日 23.59.59截止
1.1快排核心原理
首先快排的核心思想是算法常用四大思想貪心、分治、回溯、動态規劃中的分治
分治是解決複雜問題拆分并簡單化的一種思維
貪心就是求解過程多個步驟選擇最優解
配合回溯可以減少周遊，也就是緩存思想
動态規劃就是複雜問題簡單化公式化遞歸思想。
我算法也不是特别好一直在學習，算法思想隻能描述到這。
其次具體操作就是選擇一個核心資料結點當作比較值Pivot
通過周遊數組中的資料和Pivot做比較
小于的放左邊大于的放右邊
同時該算法也演變出很多具體場景的優化算法
比如三路快排就是為了解決數組中重複元素比較多的情況下的無效比較。
但是三路快排在絕對無重複的情況下性能并不如普通快排
因為維護了多個無意義的指針以及無意義的比較。
這裡測試資料就不放出來了
因為計算機硬體和使用的語言不一樣，都會導緻結果的誤差，這個我非常肯定。
舉個例子歸并排序的合并有一個優化就是合并之前對中間資料的比較減少有序合并代碼如下
sort(arr, l, mid);
sort(arr, mid + 1, r);
if( arr[mid]>arr[mid+1] ){
merge(arr, l, mid, r); }
理論上可以起到優化，實際上性能可能會更差，我用的可能誰能保證你是一台什麼計算機。。
因為這裡多了一個if判斷，但是讀取arr[i]的資料嚴重依賴cpu的cache line
是以如果arr[mid]和arr[mid+1]都在cpu緩存那性能很高，否則的話不見得能快到哪裡，速度甚至更慢。
速度甚至更慢，這也是DualPivotQuicksort的核心優化點。
現代計算機算法不能用以前的傳統意義上的時間複雜度來衡量！
應該從交換次數，資料通路次數，比較次數，cpu緩存
1.2代碼如下：
首先這個代碼隻是基礎快排，并沒有再優化絕對有序的情況下算法退化問題
因為絕對有序的情況下會退化成O(n2)的時間複雜度
一般就是随機數和第一個元素替換,這樣可以避免退化
不過更好的優化是直接周遊一下是否有序或者逆序，然後再選擇合适的算法
這也是看DualPivotQuicksort學來的，歸并排序對于相對有序數組來說比快排性能要更好。
/**
- Todo if判斷之後随機擷取數組一個數和第一個元素交換，swap( arr, left , random() );
*/
public static void sort(int a[],int left,int right){
if (a==null||left>=right){
return;
}
int j =left;
int v = a[left];
for (int i=left+1;i<=right;i++){
if(a[i]<v){
j ++;
int temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
a[left] = a[j];
a[j] = v;
sort(a,left,j-1);
sort(a,j+1,right); DualPivotQuicksort主要實作原理是利用了各種算法的特性綜合實作
先說代碼實作步驟再說具體原理為代碼如下
可以分為兩個大步驟
2.1 歸并或者快排的選擇
1.if(arr<286)使用快速排序
2.判斷數組是否有序以及有序程度，如果發現數組并不是特别有序使用快排
3.以上判斷結束有序則直接傳回，否則使用歸并排序，
這裡歸并排序直接初始化了一個排序數組一樣大小工作空間數組，減少數組空間的開辟算一個優化點。
2.2 快排
這裡已經進入到快排的代碼塊主要步驟如下
1.if (length < INSERTION_SORT_THRESHOLD)如果下于47則使用插入排序
這個插入排序真心牛逼的不行，優化到了極緻，後面再說具體怎麼優化
因為得了解DualPivotQuicksort的排序做法才能懂。
2.超過47的情況下将資料除以近似7
int seventh = (length >> 3) + (length >> 6) + 1;
int e3 = (left + right) >>> 1; // The midpoint取中間值
int e2 = e3 - seventh;
int e1 = e2 - seventh;
int e4 = e3 + seventh;
int e5 = e4 + seventh;
接着給上面五個元素手動排序，注意是手動也是一個優化，避免重複循環，《逆序對》思想其實在這有展現。
3.比較上面五個元素，如果都重複說明數組重複機率很大，使用三路快排。
三路快排就是為了解決重複元素無效比較而出現。
4.否則使用雙軸快排，這個其實就是在單軸的普通快排上面多增加了一個比較軸
這有什麼好處了？
首先使得快排資料拆分更均勻，快排的不穩定也是由于拆分不均勻導緻
比如說絕對有序的數組使用快排就會導緻一邊倒，直接O(n2)
在步驟2中其實也涉及到拆分均勻的思路在裡面
其次使得數組可以拆分成更小的子產品，這有利于cpu緩存的利用提高性能。
衆所周知計算機多級緩存，cpu中運作最快但是空間最小。
合理拆分小數組可以在cpu中加載的比較資料更多，比較速度自然快
不得不佩服 Vladimir Yaroslavskiy的思路，打破了正常的算法性能認知。
5.最後統一的遞歸
sort(a, left, less - 1, leftmost);
sort(a, great + 1, right, false);
這裡就是步驟一中說到的優化
到這裡我們自然很明白左邊的資料肯定是小于右邊的資料
是以當leftmost為true使用傳統插入排序
false使用優化過後的雙資料插入
主要優化點還是false情況下的優化代碼具體如下，
//直接一個while完全不用管越界問題了
while (a1 < a[--k]) {
a[k + 2] = a[k]; 傳統的如下，每次循環都要判斷越界
if (j-- == left) {
break; 為什麼左邊的不使用這種方式
這根本不用想，不是不能實作，而是強行排序幾個小元素放前面性能下滑太厲害
還不如直接使用傳統方式
插入排序在數組較小的情況下理論上同樣的确不如快排，但是穩定啊
并且減少了遞歸的消耗，資料全在cpu中計算，畢竟幾十k的空間還是有的
進階排序算法的優化常用手段就是配合插入排序一塊玩
最後有幾個關鍵數字比如為什麼是47還有為什麼是286
其實DualPivotQuicksort這個代碼的執行邏輯我在上個星期就能說明白
一直在思考的也是這個問題，後面我得出結論
根據時間複雜度的計算魔法數的選擇範圍
接着作者對于代碼的優化，加上不同場景的資料測試選擇了這麼一個數字
群名片名字:張浩
原理：基于“分治”（divide-and-conquer）的思想，是以第一步就是“分”，把資料分成幾分（兩份），選取一個關鍵數a，把資料集合分成兩部分，array1中的所有數都小于a，array2的所有數都不小于a；然後用 遞歸排序，來對兩個子集合的資料進行排序。時間複雜度比較複雜，最好的情況是O(n)，最差的情況是O(n2)，是以平時說的O(nlogn)，為其平均時間複雜度。空間複雜度為O(log2n)。為什麼說這個排序算法是非常優秀的算法了，抛開最好和最差的兩種情況，即，在一般情況下，他的時間複雜度都是趨近于O(nlogn)，換一種說法就是，快排的運作時間不依賴于輸入序列的順序。在排序考慮算法的時候，我們要考慮的都是最普通的情況而不是特殊的情況，由于快排在很多普通的情況下，時間複雜度都是O(nlogn)，是以說快排很穩點，對記憶體的占用也非常小，相比于 其他算法，節省了記憶體空間。
我覺得核心的代碼，就是遞歸方法
//快速排序split實作方法
//劃分數組
public static int split(int a[], int low, int high)
{
int i = low; //i指向比較元素的期望位置
int x = a[low]; //将該組的第一個元素作為比較元素
//從第二個元素開始，若目前元素大于比較元素，将其跳過
for(int j = low+1; j <= high; j++)
//若找到了小于比較元素的元素，将其與前面較大的元素進行交換
if(a[j] <= x)
{
i++;
if(i != j)
swap(a, i, j);
}
swap(a, i, low); //将比較元素交換到正确的位置上
return i; //傳回比較元素的位置
}
DualPivotQuicksort使用了兩個pivot加速。思想如下：
1) 選擇兩個點作為軸心,P1,P2。
2)P1必須比P2要小，現在将整個數組分為四部分：
（1）第一部分：比P1小的元素。
（2）第二部分：比P1大但是比P2小的元素。
（3）第三部分：比P2大的元素。
（4）第四部分：待比較的部分。
在開始比較前，除了軸點，其餘元素幾乎都在第四部分，直到比較完之後第四部分沒有元素。
3）.從第四部分選出一個元素a[K]，與兩個軸心比較，然後放到第一二三部分中的一個。
4）.移動L，K，G指向。
5）.重複 3）和4） 步，直到第四部分為空。
6）.将P1與第一部分的最後一個元素交換。将P2與第三部分的第一個元素交換。
7）.遞歸的将第一二三部分排序。
DualPivotQuicksort提出了一種“掃描元素個數”的思想，我們知道，以前的算法都是基于“元素比較次數”來評價一個算法好壞的，在這種新的算法裡面，我們把對于數組裡面一個元素的通路:array[i] 稱為一次掃描。但是對于同一個下标，并且對應的值也不變得話，即使通路多次我們也隻算一次。而且我們不管這個通路到底是讀還是寫。
其實這個所謂的掃描元素個數反應的是CPU與記憶體之間的資料流量的大小。
在這種新的算法下面經典快排和Dual-Pivot快排的掃描元素個數分别為:
1.5697nlnn VS 1.4035nlnn
也就是說經典快排确實進行了更多的元素掃描動作，是以也就比較慢。在這種新的算法下面，Dual-Pivot快排比經典快排t節省了12%的元素掃描，從實驗來看節省了10%的時間。
參考：
1.
http://open.163.com/newview/movie/free?pid=M6UTT5U0I&mid=M6V2T7IS4，這個是網易公開課，是外國大學教授講快排的原理和為什麼快排很優秀的原因，
也是我第一個回答主要參考的對象；
2.
https://blog.csdn.net/u010786672/article/details/425808993.
https://www.jianshu.com/p/2c6f79e8ce6e4.
https://blog.csdn.net/jek123456/article/details/797276865.
https://www.cnblogs.com/su劉鵬飛【第22次讨論主題：排序】
原理：
1．先從數列中取出一個數作為基準數。
2．分區過程，将比這個數大的數全放到它的右邊，小于或等于它的數全放到它的左邊（這種處理方式稱為分治法）。
3．再對左右區間重複第二步，直到各區間隻有一個數。
資料的移動是基準元素中比較重要的點，有兩種方式實作，挖坑填數法和指針交換法。
核心代碼：
public class DiyQuickSort {
public static void sort(int a[], int low, int length) {
int i, j, index;
if (low > length) {
return;
}
i = low;
j = length;
index = a[i];
while (i < j) {
while (i < j && a[j] >= index) {
j--;
}
if (j > i) {
a[i] = a[j];
i = i + 1;
}
while (i < j && a[i] < index) {
i = i + 1;
}
if (j > i) {
a[j] = a[i];
j--;
}
}
a[i] = index;
sort(a, low, i - 1);
sort(a, i + 1, length);
} JDK裡面直到JDK6用的都是這種經典快排的算法。但是到了JDK7的時候JDK内置的排序算法已經由經典快排變成了Dual-Pivot排序算法。在經典快排裡面有一個pivot的概念，它是用來分隔大數和小數的 -- 這個pivot把一個數組分成兩份。那麼所謂的Dual-Pivot其實就是用兩個Pivot, 把整個數組分成三份。
原理：首先檢查數組的長度，比一個門檻值小的時候直接使用雙軸快排。其它情況下，先檢查數組中資料的順序連續性。把數組中連續升序或者連續降序的資訊記錄下來，順便把連續降序的部分倒置。這樣資料就被切割成一段段連續升序的數列。
代碼中的關鍵步驟：
sort排序主要目的最短的時間完成排序，是以會通過不同長度的int，來使用相對效率最高的排序方法，步驟如下：
第一段：
if (right - left < QUICKSORT_THRESHOLD) {
sort(a, left, right, true);
return;
} 第二段：
先判斷排序的長度，如果長度小于（QUICKSORT_THRESHOLD = 286 ）此值使用快速排序，大于此值使用歸并排序。
if (length < INSERTION_SORT_THRESHOLD) {
…
判斷排序的長度，如果長度小于（INSERTION_SORT_THRESHOLD = 47 ）此值使用插入排序，大于此值使用快速排序。
第三段：
if (++count == MAX_RUN_COUNT) {
sort(a, left, right, true);
return;
判斷數組中有序數列的個數超過了（MAX_RUN_COUNT=67）使用快速排序，否則使用歸并排序。
第四段：
for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
if (--m == 0) {
sort(a, left, right, true);
數列中有至少（MAX_RUN_LENGTH=33）的資料相等的時候，直接使用快速排序。
常量中除了QUICKSORT_THRESHOLD其餘都是用來選擇排序算法的，選擇排序算法主要考慮元素個數。
- 當元素個數大于元素種數，使用歸并排序。
- 當元素個數較多且基本有序（遞增片段較少），使用歸并排序。
- 當元素個數較多且較為無序，使用快速排序。
- 當元素個數較少，使用插入排序。
雙軸快速排序：
通過1/7的近似值，擷取靠近中間的5段數列排序。
使用5個元素中的2，4兩個位置，他們兩個大緻處在四分位的位置上, 稱之為pivot1和pivot2。
pivot1和pivot2都從數組中選出, pivot1在pivot2的右側, 且pivot1必須小于pivot2, 如果不是, 則交換pivot1和pivot2的值;
接下來令數組中的每一個元素和基準進行比較, 比pivot1小的放在pivot1左邊, 比pivot2大的放在pivot2右邊, 介于兩者之間的放在中間.
這樣, 最終我們會的得到三個數組, 比pivot1小元素構成的數組, 介于pivot1和P2之間的元素構成的數組, 以及比pivot2大的元素構成的數組.
最後, 遞歸地對這三個數組進行排序, 最終得到排序完成的結果。
![C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列 二、優先級規律[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)