Common Sort - 排序 - Java
生活随笔
收集整理的這篇文章主要介紹了
Common Sort - 排序 - Java
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
文章目錄
- 排序
- 概念
- 穩定性（重要）
- 應用 - 舉例
- 1.、各大商城的價格從低到高等
- 2、中國大學排名
- 常見的排序算法（8 種）- 總覽
- 直接插入排序
- 模擬實現 - 插入排序
- 穩定性分析
- 結論
- 希爾排序
- 思考
- 原理
- 科學家的分組思維
- 模擬實現 - 希爾排序
- 總結
- 選擇排序
- 直接選擇排序 - 原理
- 優化
- 代碼如下
- 附圖
- 雙向選擇排序 （了解）
- 代碼如下
- 堆排序
- 代碼
- 冒泡排序
- 代碼如下 - 未優化
- 代碼優化思維
- 代碼如下 - 優化
- 未優化 和 優化代碼 運行速度比較
- 快速排序 - 重點
- 原理
- 總結
- 程序框架
- 完善 partition 部分
- 代碼細節部分
- 總程序 - 未優化
- 快速排序 的 時間 與 空間復雜度分析
- 堆排序 與 快排 的區別
- 細節拓展
- if語句中 比較大小的代碼中 等號是不能省略的
- 目前版本的 快排代碼 不支持 大量數據進行排序 - 會導致棧溢出。
- 基準值的選擇 - 優化前的知識補充
- 快速排序（幾數取中法 優化）
- 優化總結
- 拓展 快速排序 - 非遞歸實現
- 非遞歸實現快速排序的思維
- 代碼如下
- 歸并排序 - 重點
- 知識鋪墊 ： 二路合并
- 二路合并的代碼如下
- 歸并排序 - 原理
- 難點1 - 如何將一個數組拆分成一個個單獨數組【每個數組里只包含一個元素】。
- 難點2 - 合并
- 歸并排序的程序框架
- 合并程序的完善
- 附圖
- 歸并排序 - 總程序
- 歸并排序 - 時間與空間復雜度分析、穩定性
- 歸并排序 - 非遞歸實現
- 代碼如下
- 海量數據的排序問題
- 小總結
- 排序總結
- 不常見的排序 - 不基于比較的排序（了解）
- 基數排序
- 代碼如下
- 捅排序
- 計數排序
- 代碼如下
- 附圖 - 是目前的計數排序穩定
排序
概念
排序，就是使一串記錄，按照其中的某個 或 某些關鍵字的大小，遞增 或 遞減 的 排列起來的操作。
平時的上下文中，如果提到排序，通常指的是 排升序（非降序）。
通常意義上的排序，都是指的原地排序（in place sort）
原地排序：就是指在排序過程中不申請多余的存儲空間，只利用原來存儲待排數據的存儲空間進行比較和交換的數據排序。
穩定性（重要）
兩個相等的數據，如果經過排序后，排序算法能保證其相對位置不發生變化，則我們稱該算法是具備穩定性的排序算法。
應用 - 舉例
1.、各大商城的價格從低到高等
2、中國大學排名
常見的排序算法（8 種）- 總覽
直接插入排序
插入排序：非常簡單！僅次于冒泡排序。
根據這個思維：第一個數據是有序的，也就是說：在我們遍歷的時候，是從下標1 開始的。
具體的操作見下圖：
模擬實現 - 插入排序
import java.util.Arrays;public class DirectInsertionSort {/** 時間復雜度： O(N^2)* 最好情況： O(N) 數組有序的情況* 空間復雜度：O(1) 只有 一個 tmp 變量是常駐的* 穩定性：穩定* */public static void insertionSort(int[] array){for(int i = 1;i < array.length;i++){int tmp = array[i];int j = i - 1;for( ; j >= 0;j-- ){// 前移if(tmp < array[j]){array[j + 1] = array[j];}else{break;}}// 插入【無論是找到了合適插入的位置，還是不存在比 tmp更小的值，j自減到 -1.執行的代碼都是一樣的】array[j+1] = tmp;}}public static void main(String[] args) {int[] array = {23,45,56,68,8,9};insertionSort(array);System.out.println(Arrays.toString(array));}}穩定性分析
結論
一個穩定的排序，可以實現為 不穩定的排序。
但是，一個本身就不穩定的排序是 無法變成 穩定的排序。
直接插入排序 是 有序的。
它的時間復雜度是 O(N^2)；最好情況:O(N【數組有序】
也就是說：對于直接插入排序，數據越有序越快！
由此，不難聯想到：直接插入排序 有時候 會用于 優化 排序。
【假設：假設我們有一百萬個數據需要排序，在排序的過程中，區間越來越小，數據越來越有序。直接插入排序的時間復雜度為 O(N),N 越來越小，那么，使用 直接插入排序是不是越來越快！也就是說：直接插入排序 有時候會 用于 排序優化】
直接插入排序經常使用在 數據量不多，且整體數據趨于有序的。
希爾排序
思考
假設，現有 1 00 00 個 數據，如果對著組數據進行排序，使用插入排序。
時間復雜度為 O(N^2)【最壞情況：逆序的情況】
故 1 00 00 * 1 00 00 == 1 億（量化）
它不是 1 萬個數據嘛。那么，我們可以不可以這么去想：將這 一萬個數據拆分成 100 組【每組100個數據】，對其中一組進行直接插入排序的時間復雜度為 100*100 ==1 00 00（量化），這樣的分組還有99個，也就是將這一百組使用直接插入排序的時間復雜度為 1 00 00 * 1 00 = 1 百萬（量化）。
有沒有發現，分組過后，時間復雜度效率 提高很多，由1億 變成了 1百萬。
也就是說：如果采用分組的思想，我們會發現 時間復雜度會有一個很大的改變。
而這種分組的思想 就是 希爾排序。
原理
希爾排序又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數 n，把待排序文件中所有數據分成 n 組，所有距離為 數據量 / n 的 分在同一組。并且對每一組內的數據進行排序。然后，重復上述 分組 和 排序工作。當分組的組數為 1 是，所有數據 在進行 一個排序。
1、希爾排序 是對直接插入排序的優化。
2、當 group > 1 時都是預排序，目的是讓數組更接近于有序。當 group == 1時，數組已經接近有序了，這樣就會更快。對于整體而言，可以達到優化的效果。
那么，問題來了！我們怎去確定分多少組，而且越分越少。
【取自清華大學出版的一本書《數據結構》】
科學家的分組思維
現在這組數據，我們相當于只排序了一組數據，就走人了。數組整體還不是有序的。那么，我們該怎么解決這個問題？往下看！
模擬實現 - 希爾排序
import java.util.Arrays;public class ShellSort {/** 時間復雜度和增量有關系，所以無法得出準確的時間復雜度* 但只需要記住：在一定的范圍里，希爾排序的時間復雜度為 O(N^1.3 ~ N^1.5)* 空間復雜度為 O(1)* 穩定性：不穩定* 判斷穩定性的技巧：如果在比較的過程中 發生了 跳躍式交換。那么，就是不穩定的排序。* */public static void shell(int[] array,int group){for (int i = group; i < array.length; i += 1) {int tmp = array[i];int j = i-group;for (; j >= 0; j-=group) {if(tmp < array[j]){array[j+group] = array[j];}else{break;}}array[j+group] = tmp;}}public static void shellSort(int[] array){int group = array.length;// 預排序while(group > 1){// 第一次分組委 數組的長度，即 頭尾判斷。// 其后，每次分組個數，縮小一倍。shell(array,group);group /= 2;}// 最后調整shell(array,1);}public static void main(String[] args) {int[] array ={12,5,9,34,6,8,33,56,89,0,7,4,22,55,77};shellSort(array);System.out.println(Arrays.toString(array));} }總結
其實 希爾排序就是一個直接插入排序。
選擇排序
直接選擇排序 - 原理
優化
定義 一個 變量， 用來記錄 此時的 i 后面最小值的下標。等 j 遍歷完了，最小值的下標也就拿到了。此時，再進行交換。
這樣就不必讓上面那樣，遇到比 i下標元素 小的，就交換。
代碼如下
import java.util.Arrays;public class SelectSort {/** 穩定性： 不穩定 見附圖* 時間復雜度：O(N^2) 》》 外層循環 n -1，內層循環 n -1* 空間復雜度：O(1)* */public static void selectSort(int[] array){for (int i = 0; i < array.length-1; i++) {int index = i;for (int j = i + 1; j < array.length; j++) {if(array[index] > array[j]){index = j;}}int tmp = array[i];array[i] = array[index];array[index] = tmp;}}public static void main(String[] args) {int[] array = {12,6,10,3,5};selectSort(array);System.out.println(Arrays.toString(array));} }附圖
雙向選擇排序 （了解）
每一次從無序區間選出最小 + 最大的元素，存放在無序區間的最前和最后，直到全部待排序的數據元素排完 。
代碼如下
import java.util.Arrays;public class SelectSortOP {public static void selectSortOP(int[] array){int low = 0;int high = array.length - 1;// [low,high] 表示整個無序區間while(low < high){int min = low;int max = low;for (int i = low+1; i <= high; i++) {if(array[i] < array[min]){min = i;}if(array[i] > array[max]){max = i;}}swap(array,min,low);if(max == low){max = min;}swap(array,max,high);low++;high--;}}public static void swap(int[] array,int x,int y){int tmp = array[x];array[x] = array[y];array[y] = tmp;}public static void main(String[] args) {int[] array = {9, 5, 2, 7, 3, 6, 8 };selectSortOP(array);System.out.println(Arrays.toString(array));} }堆排序
基本原理也是選擇排序，只是不在使用遍歷的方式查找無序區間的最大的數，而是通過堆來選擇無序區間的最大的數。
注意： 排升序要建大堆；排降序要建小堆.
這個我就不講，因為我在堆/優先級中講的很清楚！
有興趣的，可以點擊 鏈接關鍵字 ，跳轉到該文章，該內容在 文章目錄最后面。
這里我們就直接上代碼。
代碼
import java.util.Arrays;public class HeapSort {public static void main(String[] args) {int[] array = {12,8,5,4,10,15};creationHeap(array);// 建堆的時間復雜度：O(N)System.out.println(Arrays.toString(array));heapSort(array);// 堆排序的時間復雜度：O(N * log2 N)// 空間復雜度：O(1)System.out.println(Arrays.toString(array));}// 創建一個大根堆public static void creationHeap(int[] array){for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {shiftDown(array,parent,array.length);}}public static void heapSort(int[] array){/** 時間復雜度：O(N * log2 N)* 空間復雜度：O(1)* 穩定性：不穩定* */int end = array.length - 1;while(end>0){int tmp = array[end];array[end] = array[0];array[0] = tmp;shiftDown(array,0,end);end--;}}// 向下調整public static void shiftDown(int[] array,int parent,int len){int child = parent * 2 + 1;// 做孩紙while(child < len){// 獲取左右子樹最大值的下標if(child+1 < len && (array[child] < array[child+1])){child++;}if(array[child] > array[parent]){int tmp = array[child];array[child] = array[parent];array[parent] = tmp;parent = child;child = parent * 2 + 1;}else{break;}}} }冒泡排序
代碼如下 - 未優化
import java.util.Arrays;/** 時間復雜度：O(N^2) 【無論是最好情況，還是最壞情況，時間復雜度都不變】* 空間復雜度：O(1)* 穩定性：穩定【未發生跳躍式交換】* */ public class BubbleSort {public static void bubbleSort(int[] array){// 比較的趟數 = 數組的長度 - 1 【 0 ~ 3 一共 4趟】for (int i = 0; i < array.length-1; i++) {// 比較完一趟后，可以比較的元素個數減一。【因為靠后的數據已經有序】// 內循環中，之所以要減一個 1，是因為防止 下面的if語句 發生 數組越界異常for(int j = 0;j< array.length-1-i;j++){if(array[j] > array[j+1]){int tmp = array[j];array[j] = array[j+1];array[j+1] = tmp;}}}}public static void main(String[] args) {int[] array = {12,6,10,3,5};bubbleSort(array);System.out.println(Arrays.toString(array));} }代碼優化思維
代碼如下 - 優化
import java.util.Arrays;public class BubbleSort {/** 時間復雜度：O(N^2)* 最好情況【數組有序】可以達到 O(N)* 空間復雜度：O(1)* 穩定性：穩定【未發生跳躍式交換】* */public static void bubbleSort(int[] array){for (int i = 0; i < array.length-1; i++) {boolean flag = true;for(int j = 0;j< array.length-1-i;j++){if(array[j] > array[j+1]){int tmp = array[j];array[j] = array[j+1];array[j+1] = tmp;flag = false;// 表示這一趟比較，數組是無序的}}// flag == trueif(flag){break;}}}public static void main(String[] args) {// 前半段無序，后半段有序int[] array = {2,3,1,4,5};bubbleSort(array);System.out.println(Arrays.toString(array));} }未優化 和 優化代碼 運行速度比較
public class BubbleSort {// 優化public static void bubbleSort2(int[] array){for (int i = 0; i < array.length-1; i++) {boolean flag = true;for(int j = 0;j< array.length-1-i;j++){if(array[j] > array[j+1]){int tmp = array[j];array[j] = array[j+1];array[j+1] = tmp;flag = false;}}// flag == trueif(flag){break;}}}// 未優化public static void bubbleSort1(int[] array){for (int i = 0; i < array.length-1; i++) {for(int j = 0;j< array.length-1-i;j++){if(array[j] > array[j+1]){int tmp = array[j];array[j] = array[j+1];array[j+1] = tmp;}}}}public static void main(String[] args) {int[] array = new int[10000];for (int i = 0; i < array.length; i++) {array[i] = i;}long start = System.currentTimeMillis();bubbleSort2(array);// 優化long end = System.currentTimeMillis();System.out.println(end - start);// 輸出排序所需時間start = System.currentTimeMillis();bubbleSort1(array);// 未優化end = System.currentTimeMillis();System.out.println(end - start);//輸出排序所需時間} }快速排序 - 重點
原理
1、從待排序區間選擇一個數，作為基準值（pivot）
2、Partition（分割）：遍歷整個待排序區間，將比基準值小的（可以包含相等的）放到基準值的左邊，將比基準值大的（可以包含相等的）放到基準值的右邊。
3、采用分治思想，對左右兩個小區間按照同樣的方式處理，直到小區間的長度 == 1.代表已經有序，或者小區間的長度 == 0，代表沒有數據。
總結
快速排序，其實說白了 和二叉樹]很像，先根，再左，后右。利用遞歸去實現！
程序框架
public class QuickSort {public static void quickSort(int[] array){quick(array,0, array.length);}public static void quick(int[] array,int start,int end){if(start >= end){return;}int pivot = partiton(array,start,end);quick(array,start,pivot-1);// 遞歸左邊quick(array,pivot+1,end);// 遞歸右邊}// 分割 - 找基準private static int partiton(int[] array,int start,int end){} }完善 partition 部分
// 分割 - 找基準private static int partiton(int[] array,int start,int end){int tmp = array[start];while(start < end){while(start < end && array[end] >= tmp){end--;}// 此時 end 下標 元素的值 是 小于 tmp的。array[start] = array[end];while(start<end && array[start] <= tmp){start++;}//此時 start 下標元素的值 是 大于 tmp的。array[end] = array[start];}// start 和 end 相遇了，將 tmp 賦予 它們相遇下標指向的空間array[start] = tmp;return start;}代碼細節部分
總程序 - 未優化
import java.util.Arrays;public class QuickSort {/** 時間復雜度：O(N^2) 【數據有序或者逆序的情況】* 最好情況【每次可以均勻的分割待排序序列】：O(N * log2 N)* 空間復雜度：O(N)[單分支的一棵樹]* 最好：log2 N* 穩定性：不穩定* */public static void quickSort(int[] array){quick(array,0, array.length-1);}public static void quick(int[] array,int start,int end){if(start >= end){return;}int pivot = partiton(array,start,end);quick(array,start,pivot-1);// 遞歸左邊quick(array,pivot+1,end);// 遞歸右邊}// 分割 - 找基準private static int partiton(int[] array,int start,int end){int tmp = array[start];while(start < end){while(start < end && array[end] >= tmp){end--;}// 此時 end 下標 元素的值 是 小于 tmp的。array[start] = array[end];while(start<end && array[start] <= tmp){start++;}array[end] = array[start];}array[start] = tmp;return start;}public static void main(String[] args) {int[] array = {6,1,2,7,9,3,4,5,10,8};quickSort(array);System.out.println(Arrays.toString(array));} }快速排序 的 時間 與 空間復雜度分析
堆排序 與 快排 的區別
細心的朋友會發現 堆排序 和 快排 的 時間復雜度在最好情況下 都是N* log2 N。
那么，兩者又有什么區別？
堆排序，無論最好還是最壞情況，時間復雜度都是N* log2 N。空間復雜度 O(1)
那么，又為什么快排 比 堆排序 要快？
其實再細一點說 ：在兩個排序的時間復雜度都為 N* log2 N時，其實連著前面還有 一個 k【K * N* log2 N 】，只不過快排前面的K要小一點。所以快排要快一點。
在對空間復雜度沒有要求的情況： 快排
對空間復雜度有要求的情況，或者說對數據的序列也要要求： 堆排
細節拓展
if語句中 比較大小的代碼中 等號是不能省略的
當 下面框選的代碼 沒有等號時，會造成死循環。
我就改了一下，末尾元素的值。
那么，問題來了：為什么沒有等號就死循環了？
所以，在 寫快排的時候，比較大小的代碼，記住一定要加上等號！！！！！
目前版本的 快排代碼 不支持 大量數據進行排序 - 會導致棧溢出。
這是因為 我們遞歸的太深了，1百萬數據，4百萬字節。
1TB等于1024GB;1GB等于1024MB;1MB等于1024KB;1KB等于1024Byte(字節);1Byte等于8bit(位);
有的朋友會說：這才多大啊？棧怎么會被擠爆？
這是因為在遞歸的時候，開辟的棧幀【函數的信息，參數等等等…都有】，所以，每次開辟的棧幀不止 4byte。故棧被擠爆了。
所以，我們要優化快排的 代碼。【優化：數據有序的情況】
基準值的選擇 - 優化前的知識補充
1、選擇邊上（左或者右） 【重點，上面使用的就是這種方法】
2、隨機選擇（針對 有序數據）【了解】
3、幾數取中（常見的就是三數取中）：array[left]，array[mid] ，array[right]中 大小為 中間值的為基準值【優化的關鍵】
快速排序（幾數取中法 優化）
import java.util.Arrays;public class QuickSort {/** 時間復雜度：O(N^2) 【數據有序或者逆序的情況】* 最好情況【每次可以均勻的分割待排序序列】：O(N * log2 N)* 空間復雜度：O(N)[單分支情況]* 最好：log2 N* 穩定性：不穩定* */public static void quickSort(int[] array){quick(array,0, array.length-1);}public static void quick(int[] array,int start,int end){if(start >= end){return;}// 在找基準之前，先確定 start 和 end 的 中間值。[三數取中法]int midValIndex = findMidValIndex(array,start,end);//將它 與 start 交換。這樣后面的程序，就不用改動了。swap(array,start,midValIndex);int pivot = partiton(array,start,end);quick(array,start,pivot-1);// 遞歸左邊quick(array,pivot+1,end);// 遞歸右邊}// 確定基準值下標private static int findMidValIndex(int[] array,int start,int end){// 確定 start 和 end 的中間下標int mid = start + ((end - start)>>>1);// == （start + end）/ 2// 確定 mid、start、end 三個下標，誰指向的元素是三個元素中的中間值if(array[end] > array[start]){if(array[start] > array[mid]){return start;}else if(array[mid] > array[end]){return end;}else{return mid;}}else{// array[start] >= array[end]if(array[end] > array[mid]){return end;}else if(array[mid] > array[start]){return start;}else {return mid;}}}// 交換兩個下標元素private static void swap(int[] array,int x,int y){int tmp = array[x];array[x] = array[y];array[y] = tmp;}// 分割 - 找基準private static int partiton(int[] array,int start,int end){int tmp = array[start];while(start < end){while(start < end && array[end] >= tmp){end--;}// 此時 end 下標 元素的值 是 小于 tmp的。array[start] = array[end];while(start<end && array[start] <= tmp){start++;}array[end] = array[start];}array[start] = tmp;return start;}// 有序public static void test1(int capacity){int[] array = new int[capacity];for (int i = 0; i < capacity; i++) {array[i] = i;}long start = System.currentTimeMillis();quickSort(array);long end = System.currentTimeMillis();System.out.println(end - start);}public static void main(String[] args) {test1(100_0000);int[] array = {6,1,2,7,9,3,4,5,10,6};quickSort(array);System.out.println(Arrays.toString(array));} }優化總結
1、選擇基準值很重要，通常使用幾數取中法
2、partition 過程中把和基準值相等的數也選擇出來
3、待排序區間小于一個閾(yù)值【臨界值】
隨著不斷的劃分基準，數組逐漸趨于有序，而區間隨著遞歸也在減小。所以，利用 直接插入排序的特性【越有序越快】，來進一步優化 快排。
拓展 快速排序 - 非遞歸實現
非遞歸實現快速排序的思維
代碼如下
import java.util.Arrays; import java.util.Stack;public class QuickSortNonRecursion {public static void quickSort(int[] array){Stack<Integer> stack = new Stack<>();int left = 0;int right = array.length-1;int pivot = partiton(array,left,right);if(pivot > left+1){stack.push(left);stack.push(pivot-1);}if(pivot < right -1){stack.push(pivot+1);stack.push(right);}while(!stack.isEmpty()){right = stack.pop();left = stack.pop();pivot = partiton(array,left,right);if(pivot>left+1){stack.push(left);stack.push(pivot-1);}if (pivot<right-1){stack.push(pivot+1);stack.push(right);}}}public static int partiton(int[] array,int start,int end){int tmp = array[start];while(start<end){while(start<end && array[end] >=tmp){end--;}array[start] = array[end];while (start<end && array[start] <= tmp){start++;}array[end] = array[start];}array[start] = tmp;return start;}public static void main(String[] args) {int[] array = {12,5,8,1,10,15};quickSort(array);System.out.println(Arrays.toString(array));} }歸并排序 - 重點
知識鋪墊 ： 二路合并
將兩個有序表合并成一個有序表，稱為二路歸并。【簡單說就是 將兩個有序數組合并為一個有序數組，稱為二路合并】
二路合并的代碼如下
import java.util.Arrays;public class MergeSort {/* * array1 已有序 * array2 已有序 * */public static int[] mergeArrays(int[] array1,int[] array2){if(array1 == null || array2 == null){return array1 == null ? array2: array1;}int[] arr = new int[array1.length + array2.length];int i = 0;// arr 的 遍歷變量int s1 = 0;//array1 的 遍歷變量int s2 = 0;//array2 的 遍歷變量while(s1 < array1.length && s2 < array2.length){if(array1[s1] > array2[s2]){arr[i++] = array2[s2++]; // s2++; // i++;}else{arr[i++] = array1[s1++]; // s1++; // i++;}}// 循環結束，有一個數組的元素已經全部存入// 接下來就是將另一個數組的元素放入 arr 中while (s1 < array1.length){arr[i++] = array1[s1++]; // i++; // s1++;}while (s2 < array2.length){arr[i++] = array2[s2++]; // i++; // s2++;}return arr;}public static void main(String[] args) {int[] array1 = {1,6,7,10};int[] array2 = {2,3,4,9};int[] mergeArray = mergeArrays(array1,array2);System.out.println(Arrays.toString(mergeArray));} }歸并排序 - 原理
歸并排序（MERGE - SORT）是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
難點1 - 如何將一個數組拆分成一個個單獨數組【每個數組里只包含一個元素】。
難點2 - 合并
歸并排序的程序框架
public class MergeSort {// 歸并排序的調用“接口”public static int[] mergeSort(int[] array){if(array == null){return array;}mergeSortFunc(array,0,array.length-1);return array;}// 歸并排序實現private static void mergeSortFunc(int[] array,int low,int high){if(low >= high){return;}// 遞歸分解 // int mid = (high + low) >>> 1int mid = low + ((high - low) >>> 1);mergeSortFunc(array,low,mid);// 左邊mergeSortFunc(array,mid+1,high);// 右邊// 合并merge(array,low,mid,high);}private static void merge(int[] array,int low,int mid,int high){} }合并程序的完善
其實這個并不難，跟我前面做的知識鋪墊的思路是一樣的。
需要注意的是：
1、我們的參數中 只有一個數組
2、數組 arr ，只是一個臨時數組，用來存儲 合并之后的結果。
3、在將 arr 數組 存儲的結果，轉移到 原本數組的時候，注意賦值的位置！
附圖
歸并排序 - 總程序
import java.util.Arrays;public class MergeSort {/** 時間復雜度：N * log2 N* 空間復雜丟：O(N)* 穩定性：穩定* */public static int[] mergeSort(int[] array){if(array == null){return array;}mergeSortFunc(array,0,array.length-1);return array;}private static void mergeSortFunc(int[] array,int low,int high){if(low >= high){return;} // int mid = (high + low) >>> 1int mid = low + ((high - low) >>> 1);mergeSortFunc(array,low,mid);// 左邊mergeSortFunc(array,mid+1,high);// 右邊merge(array,low,mid,high);}private static void merge(int[] array,int low,int mid,int high){int[] arr = new int[high - low +1];int start1 = low;int end1 = mid;int start2 = mid+1;int end2 = high;int i = 0;while (start1 <= end1 && start2 <= end2){if(array[start1] > array[start2]){arr[i++] = array[start2++];}else{arr[i++] = array[start1++];}}while(start1 <= end1){arr[i++] = array[start1++];}while(start2 <= end2){arr[i++] = array[start2++];}for (int j = 0; j < arr.length; j++) {array[low++] = arr[j];}}public static void main(String[] args) {int[] array = {1,6,7,10,2,3,4,9};mergeSort(array);System.out.println(Arrays.toString(array));} }歸并排序 - 時間與空間復雜度分析、穩定性
歸并排序 - 非遞歸實現
代碼如下
import java.util.Arrays;public class MergeSortNonRecursion {public static void mergeSort(int[] array){//歸并排序非遞歸實現int groupNum = 1;// 每組的數據個數while(groupNum < array.length){// 無論數組含有幾個元素， 數組每次都需要從下標 0位置，開始遍歷。for(int i = 0;i<array.length;i+= groupNum * 2){int low = i;int mid = low + groupNum -1;// 防止越界【每組的元素個數，超過了數組的長度】if(mid >= array.length){mid = array.length-1;}int high = mid + groupNum;// 防止越界【超過了數組的長度】if(high >= array.length){high = array.length-1;}merge(array,low,mid,high);}groupNum *= 2;//每組的元素個數擴大到原先的兩倍。}}public static void merge(int[] array,int low,int mid,int high){// high 與 mid 相遇，說明 此時數組分組只有一組，也就說沒有另一組的數組與其合并// 即數組已經有序了，程序不用再往下走。if(high == mid){return;}int[] arr = new int[high -low + 1];int start1 = low;int end1 = mid;int start2 = mid+1;int end2 = high;int i = 0;while(start1 <= end1 && start2 <= end2){if(array[start1]>array[start2]){arr[i++] = array[start2++];}else{arr[i++] = array[start1++];}}while (start1 <= end1){arr[i++] = array[start1++];}while(start2 <= end2){arr[i++] = array[start2++];}for (int j = 0; j < arr.length; j++) {array[low++] = arr[j];}}public static void main(String[] args) {int[] array = {12,5,8,7,3,4,1,10};mergeSort(array);System.out.println(Arrays.toString(array));} }海量數據的排序問題
外部排序：排序過程需要在磁盤等外部存儲進行的排序
【內部排序：排序過程需要在 內存上進行排序】
前提：內存只有 1G，需要排序的數據有 100G
因為內存中無法把所有數據全部放下，所以需要外部排序，而歸并排序是最常用的外部排序。
1、先把文件切分成 200 份，每個512M
2、分別對 512M 的數據量 進行排序，因為 內存已經被分割了，512M < 1G 內存放得下。所以任何排序方式都可以，
3、進行 200 路歸并，同時對 200 份有序文件做歸并過程，最終結果就有序了
小總結
目前，我們講了八種排序：直接插入排序、希爾排序、直接選擇排序，雙向選擇排序、冒泡排序，堆排序、快速排序，歸并排序。
其中穩定的排序：插入排序，冒泡排序，歸并排序，一共三種。
?
另外，堆排序、歸并排序、快速排序的時間復雜度都是 N * log2 N。
如果，你想速度快，就用快排。
如果，你想穩定，就用歸并。
如果，你想空間復雜度低，就用堆排。
排序總結
| 冒泡排序 | O(N) | O(N^2) | O(N^2) | O(1) | 穩定 |
| 插入排序 | O(N) | O(N^2) | O(N^2) | O(1) | 穩定 |
| 選擇排序 | O(N^2) | O(N^2) | O(N^2) | O(1) | 不穩定 |
| 希爾排序 | O(N) | O(N^1.3) | O(N^2) | O(1) | 不穩定 |
| 堆排序 | O(N * log2 N) | O(N * log2 N) | O(N * log2 N) | O(1) | 不穩定 |
| 快速排序 | O(N * log2 N) | O(N * log2 N) | O(N ^ 2) | O(N) | 不穩定 |
| 歸并排序 | O(N * log2 N) | O(N * log2 N) | O(N * log2 N) | O(N) | 穩定 |
不常見的排序 - 不基于比較的排序（了解）
基數排序
它的思路：假設待排序的數據類型是 整形/十進制數，每個數據 分別按照 個，百，千，萬的大小，放入拿出對應編號空間，其最終的結果就是有序的。
放入拿出的次數 取決于 這組數據中 最大值的位數。
代碼如下
import java.util.Arrays;public class RadixSort { // 基數排序功能 實際功能實現方法private static void radixSortFunc(int[] array,int maxDigit){int mode = 10 ; // 十進制int divide = 1;// 將 數值上的每個數“分割”，方便獲取數據的一個位上的值// 每個數據從個位到最大值的最高位，按照其位上的大小 放出 拿出for (int i = 0; i < maxDigit; i++,mode *= 10,divide *=10) {// 考慮 負數的 情況，0~9 對應負數，10 ~ 19 對應正數// 行 對應的是編號， 列 對應的存儲的數據int[][] counter = new int[mode*2][0];for (int j = 0; j < array.length; j++) {int number = ((array[j] % mode)/divide) + mode; /*獲取 數據對應 空間的編號 */counter[number] = arrayAppend(counter[number],array[j]);}int pos = 0;for (int[] number:counter) {for (int val:number) {array[pos++] = val;}}}}// 添加 元素private static int[] arrayAppend(int[] arr,int value){arr = Arrays.copyOf(arr,arr.length+1);arr[arr.length-1] = value;return arr;}// 基數排序 功能調用方法“窗口”public static void radixSort(int[] array){int maxNumLength = getNumLength(array);radixSortFunc(array,maxNumLength);}// 獲取最大值的位數 - 功能“窗口”private static int getNumLength(int[] array){int maxVal = getMaxValue(array);return getMaxDigit(maxVal);}//獲取最大值private static int getMaxValue(int[] array){int maxValue= array[0];for (int value: array) {if(value > maxValue){maxValue = value;}}return maxValue;}// 獲取最大值的位數 - 執行private static int getMaxDigit(int num){if(num == 0){return 0;}int len = 0;while(num > 0){len++;num /= 10;}return len;}// 程序入口public static void main(String[] args) {int[] array = {124,366,170,52,200,78,468};radixSort(array);System.out.println(Arrays.toString(array));} }捅排序
計數排序
在使用 計數排序時，需注意以下幾點：
1、確定基數排序的大小
2、這個計數排序 適用的范圍【假設數據中最小值 10000，最大 12000，那么，我們的計數數組容量只需要2001（0 下標也算入） 就夠了。不需要創建 12000容量，避免空間浪費】
計數數組 計數也簡單，用元素值減去 10000（最小值） 就行了
3、必須找到數據中的最大值 和 最小值，鎖定計數數組的長度：max - min + 1
4、 拿出數據的時候，記得將減去的 最小值 加上，再進行對原始數組的覆寫。
代碼如下
import java.util.Arrays; /* * 時間復雜度：O(N) * 空間復雜度: O(M) : M 表示 當前數據的范圍 * 【空間 換 時間】 * 穩定性： 當前代碼是不穩定，本質是穩定的。 * 在借助一個 數組來存儲 每個元素排序后，最后出現的位置， * 拿出來的時候，就能確定位置。致使該排序 穩定。 - 見附圖 * */ public class CountingSort {public static void countingSort(int[] array){int maxVal = array[0];int minVal = array[0];for (int i = 0; i < array.length; i++) {if (array[i] > maxVal){maxVal = array[i];}if(array[i] < minVal){minVal =array[i];}}// 當循環結束，獲得了 數據的最大值 和 最小值// 可以確定計數數組的容量int[] count = new int[maxVal -minVal +1];for (int i = 0; i < array.length; i++) {// 提高空間利用率count[ array[i] - minVal ]++;}// 此時，計數數組 已經把array數組當中，每個元素的出現次數統計好了// 接下來，只需要遍歷計數數組，把 數據 覆寫 到 array當中。int indexArray = 0; // 用于遍歷 array數組，標記 覆寫的位置。for (int i = 0; i < count.length; i++) {while(count[i]>0){// 這里一定要加上減去minVal，因為 下標 i 不一定 在 array 數組中出現過。array[indexArray++] = i + minVal;// 拿出來的時候，記得將減去的值加上// indexArray++;count[i]--;}}}public static void main(String[] args) {int[] array = {5,0,2,3,4,5,2};countingSort(array);System.out.println(Arrays.toString(array));} }附圖 - 是目前的計數排序穩定
總結
以上是生活随笔為你收集整理的Common Sort - 排序 - Java的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python3随笔-copy与索引
- 下一篇： sympy随笔－python符号计算