[數據結構]排序 --2

8、快速排序

8.1、Hoare版

8.2、挖坑法

8.3、前后指針法

9、快速排序優化

9.1、三數取中法

9.2、采用插入排序

10、快速排序非遞歸

11、歸并排序

12、歸并排序非遞歸

13、排序類算法總結

14、計數排序

15、其他排序

15.1、基數排序

15.2、桶排序

8、快速排序

快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法

基本思想：任取待排序元素序列中的某元素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止

8.1、Hoare版

1. 把第一個值作為基準值 pivot

2. right 從右邊走，遇到比 pivot 大的就停下；left 從左邊走，遇到比 pivot 小的就停下

3. 交換 left 和 right 的值

4.?left 和 right 繼續走，直到 left 和?right 相遇

5.?相遇的位置就是要找的位置，把基準值與該位置交換

    public static void quickSort(int[] array) {quick(array,0,array.length-1);}private static void quick(int[] array,int start,int end) {if(start >= end) {return;}int pivot = partitionHoare(array,start,end);quick(array,start,pivot-1);quick(array,pivot+1,end);}private static int partitionHoare(int[] array, int left, int right) {int tmp = array[left];int pivot = left;while (left < right) {// 單獨的循環 不能一直減到超過最左邊的邊界while (left < right && array[right] >= tmp) {right--;}while (left < right && array[left] <= tmp) {left++;}swap(array,left,right);}swap(array,pivot,left);return left;}

兩個問題：

1. 為什么 array[right] >= tmp 必須帶等于號

????????可能會出現 left 和 right 無限交換的死循環

2. 為什么從 right 先走而不是 left

????????如果 left 先走可能會出現相遇的是比基準大的數據，最后把大的數據放到了最前面

快速排序總結：

1. 快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序

2. 時間復雜度：O(N*logN)

????????最好的情況下：O(N*logN)

????????最壞情況下：O(N^2)? -- 逆序/有序

3. 空間復雜度：O(logN)? -- 遞歸了logN層

????????最好的情況下：O(logN)

????????最壞情況下：O(N)? ?-- 逆序/有序

4. 穩定性：不穩定

8.2、挖坑法

1. 把第一個值拿出來作為基準值 tmp，第一個值的位置就是第一個坑

2. right 從右邊走，遇到比 pivot 大的就停下，然后把這個值放到上一個坑里，right 就形成了新的坑

3. left 從左邊走，遇到比 tmp 小的就停下，然后把這個值放到坑里，left?就是新的坑

4.?循環2、3，直到 left 和?right 相遇

5.?相遇的位置就是要找的位置，把基準值放在這個位置

    public static void quickSort(int[] array) {quick(array,0,array.length-1);}private static void quick(int[] array,int start,int end) {if(start >= end) {return;}int pivot = partitionHole(array,start,end);quick(array,start,pivot-1);quick(array,pivot+1,end);}private static int partitionHole(int[] array, int left, int right) {int tmp = array[left];while (left < right) {// 單獨的循環 不能一直減到超過最左邊的邊界while (left < right && array[right] >= tmp) {right--;}array[left] = array[right];while (left < right && array[left] <= tmp) {left++;}array[right] = array[left];}array[left] = tmp;return left;}

8.3、前后指針法

1.?定義兩根指針cur和prev，初始位置如下圖

2. cur開始往后走，如果遇到比key小的值，則++prev，然后交換prev和cur指向的元素，再++cur，如果遇到比key大的值，則只++cur

3.?當cur訪問過最后一個元素后，將key的元素與prve訪問的元素交換位置。cur訪問完整個數組后的各元素位置如下圖

private static int partition(int[] array, int left, int right) {int prev = left ;int cur = left+1;while (cur <= right) {if(array[cur] < array[left] && array[++prev] != array[cur]) {swap(array,cur,prev);}cur++;}swap(array,prev,left);return prev;
}

總結：
1. Hoare
2. 挖坑法
3. 前后指針法
這3種方式 ?每次劃分之后的前后順序有可能是不一樣的

9、快速排序優化

優化的出發點：減少遞歸的次數

9.1、三數取中法

既然有序數組或者有序數組片段會使效率下降，我們就可以讓基準值每次都取大小靠中的數，然后在進行快速排序這樣就可以避免了。但不是完全避免，只是減少了最壞情況出現的概率，最壞情況還是O(n2)，但有效提升了運行效率，主要提升的部分是數組中有序的數組片段，減少了循環次數。

    // 求中位數的下標private static int middleNum(int[] array,int left,int right) {int mid = (left+right)/2;if(array[left] < array[right]) {if(array[mid] < array[left]) {return left;}else if(array[mid] > array[right]) {return right;}else {return mid;}}else {//array[left] > array[right]if(array[mid] < array[right]) {return right;}else if(array[mid] > array[left]) {return left;}else {return mid;}}}private static void quick(int[] array,int start,int end) {if(start >= end) {return;}//1 2 3 4 5 6 7int index = middleNum(array,start,end);swap(array,index,start);//4 2 3 1 5 6 7int pivot = partition(array,start,end);quick(array,start,pivot-1);quick(array,pivot+1,end);}

9.2、采用插入排序

往往一棵樹的最后兩層的結點占整棵樹的絕大多數，所以當遞歸到一定深度時，采用直接插入排序

    public static void insertSort(int[] array,int left,int right) {for (int i = left+1; i <= right; i++) {int tmp = array[i];int j = i-1;for (; j >= left ; j--) {if(array[j] > tmp) {array[j+1] = array[j];}else {break;}}array[j+1] = tmp;}}private static void quick(int[] array,int start,int end) {if(start >= end) {return;}if(end - start + 1 <= 15) {insertSort(array, start, end);return;}//1 2 3 4 5 6 7int index = middleNum(array,start,end);swap(array,index,start);//4 2 3 1 5 6 7int pivot = partition(array,start,end);quick(array,start,pivot-1);quick(array,pivot+1,end);}

10、快速排序非遞歸

1. 先調用partition方法找到基準
2. 基準左邊和右邊有沒有2個及以上個元素，有就把下標放到棧中

3. 判斷棧空不空，不空出棧2個，第一個是新的end，第二個是新的start

4. 棧不為空時，循環執行上述1.2.3

    public static void quickSortNor(int[] array) {int start = 0;int end = array.length-1;Stack<Integer> stack = new Stack<>();int pivot = partition(array,start,end);if(pivot > start+1) {stack.push(start);stack.push(pivot-1);}if(pivot+1 < end) {stack.push(pivot+1);stack.push(end);}while (!stack.isEmpty()) {end = stack.pop();start = stack.pop();pivot = partition(array,start,end);if(pivot > start+1) {stack.push(start);stack.push(pivot-1);}if(pivot+1 < end) {stack.push(pivot+1);stack.push(end);}}}

11、歸并排序

歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并

    public static void mergeSort(int[] array) {mergeSortFun(array,0,array.length-1);}private static void mergeSortFun(int[] array,int start,int end) {if(start >= end) {return;}int mid = (start+end)/2;mergeSortFun(array,start,mid);mergeSortFun(array,mid+1,end);//合并merge(array,start,mid,end);}private static void merge(int[] array, int left, int mid, int right) {// s1，e1，s2，e2 可以不定義，這樣寫為了好理解int s1 = left;int e1 = mid;int s2 = mid+1;int e2 = right;//定義一個新的數組int[] tmpArr = new int[right-left+1];int k = 0;//tmpArr數組的下標//同時滿足 證明兩個歸并段 都有數據while (s1 <= e1 && s2 <= e2) {if(array[s1] <= array[s2]) {tmpArr[k++] = array[s1++];}else {tmpArr[k++] = array[s2++];}}while (s1 <= e1) {tmpArr[k++] = array[s1++];}while (s2 <= e2) {tmpArr[k++] = array[s2++];}//把排好序的數據 拷貝回原來的數組array當中for (int i = 0; i < tmpArr.length; i++) {array[i+left] = tmpArr[i];}}

兩個有序數組合并為一個有序數組代碼：

public static int[] mergeArray(int[] arrayl,int[] array2) {// 注意判斷參數int[] tmp = new int[array1.length+array2.length];int k = 0;int s1 = 0;int el = array1.length-1;int s2 = 0;int e2 = array2.length-1;while (s1 <= el && s2 <= e2) {if(array1[s1] <= array2[s2]) {tmp[k++] = array1[s1++];}else {tmp[k++]=array2[s2++];}}while (s1 <= el) {tmp[k++] = array1[s1++];}while (s2 <= e2) {tmp[k++]= array2[s2++];}return tmp;
}

歸并排序總結
1. 歸并的缺點在于需要O(N)的空間復雜度，歸并排序更多的是解決在磁盤中的外排序問題。
2. 時間復雜度：O(N*logN)
3. 空間復雜度：O(N)

?????????遞歸調用棧空間：O(logN)

????????合并操作空間：O(N)
4. 穩定性：穩定

海量數據的排序

外部排序：排序過程需要在磁盤等外部存儲進行的排序
前提：內存只有 1G，需要排序的數據有 100G
因為內存中因為無法把所有數據全部放下，所以需要外部排序，而歸并排序是最常用的外部排序
1. 先把文件切分成 200 份，每個 512 M
2. 分別對 512 M 排序，因為內存已經可以放的下，所以任意排序方式都可以
3. 進行2路歸并，同時對 200 份有序文件做歸并過程，最終結果就有序了（在外部存儲進行）

12、歸并排序非遞歸

1. 找到 left、mid、right 的位置和關系，然后調用merge合并

2. 定義 gap 表示當前的分組是每組幾個數據

    public static void mergeSortNor(int[] array) {int gap = 1;//每組幾個數據while (gap < array.length) {for (int i = 0; i < array.length; i = i+gap*2) {int left = i;// mid、right 可能會越界int mid = left+gap-1;int right = mid+gap;if(mid >= array.length) {mid = array.length-1;}if(right >= array.length) {right = array.length-1;}merge(array,left,mid,right);}gap*=2;}

13、排序類算法總結

14、計數排序

思想：計數排序又稱為鴿巢原理，是對哈希直接定址法的變形應用。操作步驟：
1. 統計相同元素出現次數
2. 根據統計的結果將序列回收到原來的序列中

具體實現：

1.申請一個數組count，大小為待排序數組array的范圍 M

2.遍歷待排序數組array，把數字對應的count數組的下標內容進行++

3.遍歷計數數組count 寫回到待排序數組array，此時需要注意寫的次數和元素值要一樣

4. 最后數組array中存儲的就是有序的序列

    public static void countSort(int[] array) {//求數組的最大值 和 最小值  O(N)int minVal = array[0];int maxVal = array[0];for (int i = 1; i < array.length; i++) {if(array[i] < minVal) {minVal = array[i];}if(array[i] > maxVal) {maxVal = array[i];}}//確定計數數組的 長度int len = maxVal - minVal + 1;int[] count = new int[len];//遍歷array數組 把數據出現的次數存儲到計數數組當中   O(N)for (int i = 0; i < array.length; i++) {count[array[i]-minVal]++;}//計數數組已經存放了每個數據出現的次數//遍歷計數數組 把實際的數據寫回array數組  O(M) M表示數據范圍int index = 0;for (int i = 0; i < count.length; i++) {while (count[i] > 0) {//這里需要重寫寫回array 意味著得從array的0位置開始寫array[index] = i+minVal;index++;count[i]--;}}}

計數排序的特性總結
1.計數排序是非基于比較的排序

2.?計數排序在數據范圍集中時，效率很高，但是適用范圍及場景有限；計數排序的場景：指定范圍內的數據

3. 時間復雜度：O(MAX(N,M))? ?M表示數據范圍
4. 空間復雜度：O(M)
5. 穩定性：穩定；上述代碼是不穩定的寫法

15、其他排序

15.1、基數排序

基數排序（Radix Sort）是一種非比較型的排序算法，它通過逐位比較元素的每一位（從最低位到最高位）來實現排序。基數排序的核心思想是將整數按位數切割成不同的數字，然后按每個位數分別進行排序。基數排序的時間復雜度為 O(d*(n+r))，其中 n 為元素個數，d 是最大數字的位數，r 為基數（桶的個數）

時間復雜度分析：

分配依次將每個數放到對應的桶中 O(n)

收集依次將每個桶里的元素拿出來 O(r)? （桶里的元素是用鏈表連接的）

每輪：分配+收集 O(n+r)

如果最大的數字有d位，就需要排d輪

所以時間復雜度為：O(d*(n+r))