Sort Algorithm（ASC）
[TOC] //怎么生成目錄炒刁，糾結(jié)ing
插入排序
每一趟排序都將待排元素插入到已有序的序列中女蜈，但不能保證該元素的插入位置是全局有序的。
Insertion Sort
直接插入排序
- 最好情況：$O(n)$
- 最壞情況：$O(n^2)$
- 平均情況：$O(n^2)$
- 輔助空間：O(1)
- 穩(wěn)定性：穩(wěn)定
- 每一趟排序只能保證當(dāng)前有序饰潜，并不能保證全局有序
核心思想
數(shù)組中的每一個(gè)待排元素與已部分有序的元素依次比較举畸，如果待排元素小于當(dāng)前已有序的元素别威，則交換兩者位置躯舔，并繼續(xù)向前比較。-
程序示例
public static void insertionSort(int[] arr){ for (int i=1;i<arr.length;i++){ for (int j=i-1;j>=0;j--){ if (arr[j]>arr[j+1]){ swap(arr,j,j+1); } } } } public static void swap(int[] arr,int i,int j){ int tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp; } -
程序分析
直接插入排序采用兩層循環(huán)：- 外層循環(huán)用來跟蹤每一個(gè)待排元素省古，從1到 n-1粥庄，剛開始arr[0]是默認(rèn)有序的。
- 內(nèi)層循環(huán)負(fù)責(zé)當(dāng)前待排元素與已部分有序的元素進(jìn)行逐一比較衫樊，確定當(dāng)前待排元素的最終插入位置飒赃。
優(yōu)化分析*
在內(nèi)層循環(huán)中，每當(dāng)逆序（已有序元素大于待排元素時(shí)）的情況出現(xiàn)時(shí)科侈，就執(zhí)行一次 swap 操作载佳，交換兩元素的位置，這樣會導(dǎo)致交換次數(shù)較多臀栈∧杌郏可以考慮通過比較確定最后的插入位置，然后將交換操作推遲到最后進(jìn)行权薯。這樣只需要進(jìn)行一次交換操作姑躲，但已有序元素的移動次數(shù)是不會改變的睡扬。
Shell Sort
希爾排序（縮小增量排序）
- 步長+直接插入排序
- 最好情況：$O(n)$
- 最壞情況：$O(n^2)$
- 平均情況：$O(n^{1.3})$
- 輔助空間：O(1)
- 穩(wěn)定性：不穩(wěn)定
- 每一趟排序只能保證當(dāng)前有序，并不能保證全局有序
核心思想
希爾排序黍析，又稱縮小增量排序卖怜，使用步長來確定每一次的待排子序列，然后使用直接插入排序?qū)Ξ?dāng)前待排子序列進(jìn)行排序阐枣。在完成步長為 h 的排序后马靠，通過證明可以保證，對于每一個(gè) i 與 i+h 元素都是有序的蔼两。然后縮小步長甩鳄，再次使用直接插入排序。直到最后步長為1额划，最后一次序列已經(jīng)基本有序妙啃，最后采用一次直接插入排序后就可以得到最終的有序數(shù)組。-
程序示例
public static void shellSort(int[] arr){ //第一層循環(huán)控制步長 for (int gap=arr.length/2;gap>0;gap=gap/2){ //第二層循環(huán)控制滿足步長的所有子序列 for (int i=gap;i<arr.length;i++){ //第三層循環(huán)控制當(dāng)前滿足步長的子序列的排序,采用直接插入排序的方式進(jìn)行排序 for (int j=i;j<arr.length;j+=gap){ if (arr[j]<arr[j-gap]){ swap(arr,j,j-gap); } } } } } public static void swap(int[] arr,int i,int j){ int tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp; } -
程序分析
希爾排序采用三層循環(huán)：- 第一層循環(huán)負(fù)責(zé)確定每一趟的步長俊戳，并按一定的規(guī)則（這里采用/2折半的規(guī)則）揖赴，循環(huán)減小步長到1。
- 第二層循環(huán)針對當(dāng)前步長品抽，依次確定滿足該步長的待排子序列储笑。
- 第三層循環(huán)針對當(dāng)前確定的待排子序列甜熔，采用直接插入排序的方法進(jìn)行排序圆恤。
選擇排序
基本思想：比較+交換
Selection Sort
簡單選擇排序
- 最好情況：$O(n^2)$
- 最壞情況：$O(n^2)$
- 平均情況：$O(n^2)$
- 輔助空間：O(1)
- 穩(wěn)定性：不穩(wěn)定
- 每一趟排序保證全局有序
核心思想
簡單選擇排序，是選擇排序中的一種腔稀，遵循其基本思想：比較+交換盆昙。即通過依次比較確定當(dāng)前趟最小元素，并根據(jù)情況與當(dāng)前待排元素交換焊虏。具體做法是在每趟排序中淡喜，通過將當(dāng)前待排元素與與剩余所有元素比較，找到最小的元素并與當(dāng)前元素交換（如果當(dāng)前待排元素就是最小诵闭，則不用交換）炼团。-
程序示例
public static void selectionSort(int[] arr){ for (int i=0;i<arr.length;i++){ //這里采用 min 來標(biāo)記最小元素的下標(biāo),方便 swap 的時(shí)候通過下標(biāo)進(jìn)行交換 int min=i; //第二層循環(huán)負(fù)責(zé)將當(dāng)前元素與剩余所有元素比較,找到這些元素中的最小值,如果該最小值不是當(dāng)前元素,則在退出循環(huán)后將當(dāng)前元素與該最小元素交換 //因?yàn)槊恳淮螌ふ耶?dāng)前趟最小元素都是與所有待排元素比較,因此,簡單選擇排序是全局有序的 for (int j=i+1;j<arr.length;j++){ if (arr[j]<arr[min]){ min=j; } } if (min!=i){ swap(arr,i,min); } } } public static void swap(int[] arr,int i,int j){ int tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp; } -
程序分析
簡單選擇排序，采用兩層循環(huán)：- 外層循環(huán)用于控制當(dāng)前待排元素及其待排位置疏尿。
- 內(nèi)存循環(huán)用于基于當(dāng)前待排位置和待排元素瘟芝，循環(huán)依次與序列中剩余其它元素比較，如果存在元素小于當(dāng)前待排元素褥琐，則采用一個(gè)臨時(shí)變量始終標(biāo)記符合該條件的元素锌俱。在退出內(nèi)層循環(huán)后，判斷經(jīng)過一趟完整比較后敌呈，最小元素是否為當(dāng)前待排元素贸宏，如果是造寝，說明當(dāng)前待排元素是當(dāng)前趟的最小值，當(dāng)前位置即全局有序位置吭练，不交換诫龙；如果不是，則采用 swap 交換鲫咽。
Heap Sort
堆排序
- 最好情況：$O(nlog_2n)$
- 最壞情況：$O(nlog_2n)$
- 平均情況：$O(nlog_2n)$
- 輔助空間：O(1)
- 穩(wěn)定性：不穩(wěn)定
- 每一趟排序保證全局有序
核心思想
堆排序赐稽，先根據(jù)父節(jié)點(diǎn)與子節(jié)點(diǎn)下標(biāo)關(guān)系（i，2i+1浑侥，2i+2）將待排序列構(gòu)造為大頂堆（實(shí)際上還是在數(shù)組中存儲）姊舵。然后執(zhí)行循環(huán)操作：每次將頂點(diǎn)元素與最后一個(gè)元素swap，交換后寓落，當(dāng)前最大元素已經(jīng)位于數(shù)組的末尾括丁，因?yàn)樵瓉淼哪┪苍氐搅隧旤c(diǎn)位置，有可能破壞堆的性質(zhì)伶选，則通過堆調(diào)整來修正堆性質(zhì)史飞。循環(huán)執(zhí)行這一組操作，直到堆中只有一個(gè)元素的時(shí)候仰税，該待排序列已然有序构资。-
程序示例
public static void heapSort(int[] arr){ buildHeap(arr); int length=arr.length; while (length>0){ swap(arr,0,length-1); length--; adjustToHeap(arr,length,0); } } public static void buildHeap(int[] arr){ for (int i=0;i<arr.length/2;i++){ adjustToHeap(arr,arr.length,i); } } public static void adjustToHeap(int[] arr,int length,int index){ int indexOfMax=index; while (true){ int leftIndex=getLeftChild(index); int rightIndex=getRightChild(index); if (leftIndex<length&&arr[leftIndex]>arr[indexOfMax]){ indexOfMax=leftIndex; } if (rightIndex<length&&arr[rightIndex]>arr[indexOfMax]){ indexOfMax=rightIndex; } if (indexOfMax!=index){ swap(arr,index,indexOfMax); index=indexOfMax; continue; } else { break; } } } public static int getLeftChild(int i){ return 2*i+1; } public static int getRightChild(int i){ return 2*i+2; } public static void swap(int[] arr,int i,int j){ int tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp; } -
程序分析
在采用堆排序前，需要對待排序列構(gòu)造大頂堆陨簇。具體構(gòu)造方式吐绵，稍后詳述。- 在生成大頂堆后河绽，滿足大頂堆的性質(zhì)己单，第一個(gè)元素 arr[0]是當(dāng)前0~arr.length-1中的最大值。接下來對該大頂堆進(jìn)行 N-1 次的交換和調(diào)整耙饰。
- 具體做法是纹笼，在每次交換和調(diào)整中，將堆頂?shù)淖畲笾蹬c堆尾元素互換苟跪，這樣廷痘，該最大值就位于正確順序位置上。因?yàn)榛Q后有可能破壞大頂堆順序件已，因此必須在互換后調(diào)用 adjustToHeap 進(jìn)行堆性質(zhì)修正笋额。
交換排序
Bubble Sort
冒泡排序
- 最好情況：$O(n^2)$
- 最壞情況：$O(n^2)$
- 平均情況：$O(n^2)$
- 輔助空間：O(1)
- 穩(wěn)定性：穩(wěn)定
- 每一趟排序保證全局有序
核心思想
冒泡排序，在每一趟排序中拨齐，都依次比較左右兩個(gè)元素鳞陨，如果不符合大小關(guān)系，則交換位置，并繼續(xù)比較下一個(gè)坐標(biāo)位置厦滤。在一趟比較結(jié)束后援岩，當(dāng)前趟最大的元素會沉底。-
程序示例
public static void bubbleSort(int[] arr){ //對于 N 個(gè)元素的序列,需要 N-1 趟排序 for (int i=1;i<arr.length;i++){ //在每一趟排序后,下標(biāo)為 arr.length-i的元素已經(jīng)位于全局有序位置,因此下一趟比較的最后待排位置為 arr.length-i-1 //每一趟比較中,當(dāng)前下標(biāo)的左右兩個(gè)元素如果順序不當(dāng),則互相交換,較大的向后調(diào)整,如果滿足大小要求,則不交換掏导。這樣依次對剩余元素進(jìn)行比較,直到 arr.length-i for (int j=0;j<arr.length-i;j++){ if (arr[j]>arr[j+1]){ swap(arr,j,j+1); } } } } public static void swap(int[] arr,int i,int j){ int tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp; } -
程序分析
冒泡排序采用兩層循環(huán)享怀，對于 N 個(gè)元素的冒泡排序，需要進(jìn)行 N-1 趟排序趟咆，第 i 趟排序需要比較 N-i 次添瓷。- 第一層循環(huán)控制冒泡排序的趟數(shù)，從1到 N-1趟冒泡排序值纱。
- 第二層循環(huán)控制每一趟的冒泡排序鳞贷，因?yàn)榻?jīng)過第 i-1 趟的排序，第 N-i+1 個(gè)位置已經(jīng)有序虐唠，所以在第 i 趟的冒泡排序中搀愧，只需要從第一個(gè)元素一直比較到第 N-i 個(gè)元素。
優(yōu)化分析
針對最好情況為$O(n)$的情形疆偿，可以在外層循環(huán)中設(shè)置一個(gè)變量用來檢查上一趟是否存在交換操作咱筛，在內(nèi)層循環(huán)中，發(fā)生 swap 操作則置該變量為 true杆故，否則默認(rèn)為 false迅箩。在退出內(nèi)層循環(huán)后，外層邏輯會判斷如果變量為 true 說明上一趟待排序列不滿足順序條件处铛，繼續(xù)本趟排序饲趋；如果為 false 說明在上一趟中待排序列所有元素已經(jīng)有序。因此在本趟排序可以直接 break罢缸，已經(jīng)提前完成了序列排序篙贸。
Quick Sort
快速排序
- 最好情況：$O(nlog_2n)$
- 最壞情況：$O(n^2)$
- 平均情況：$O(nlog_2n)$
- 輔助空間：$O(nlog_2n)$
- 穩(wěn)定性：不穩(wěn)定
- 每一趟排序保證軸 key 全局有序
核心思想
循環(huán)比較交換+分而治之的思想。在每一趟的排序操作中枫疆，當(dāng) i不等于j 的時(shí)候，將大于 key 的元素都交換在 key 的右邊敷鸦，小于 key 的元素都交換在 key 的左邊息楔。當(dāng) i等于j 的時(shí)候，就是 key 的最終有序位置扒披。但是經(jīng)過一趟排序操作值依，僅保證了當(dāng)前 key 位于正確有序的位置 i，但對于start~i-1和 i+1~end 是無序的碟案，因此需要在這兩段上遞歸調(diào)用剛剛的排序操作愿险。-
程序示例
public static void quickSort(int[] arr,int start,int end){ if (start<end){ int i=start; int j=end; int key=arr[start]; while (i!=j){ //從后向前循環(huán)找到第一個(gè)小于 key 的元素 while (i<j&&arr[j]>=key){ j--; } //將該元素替換到 key 的左邊 if (i<j){ arr[i]=arr[j]; i++; } //從前向后循環(huán)找第一個(gè)大于 key 的元素 while (i<j&&arr[i]<key){ i++; } //將該元素替換到 key 的右邊 if (i<j){ arr[j]=arr[i]; j--; } } //當(dāng) i=j 的時(shí)候,說明在這一趟交換過后,所有大于 key 的元素都位于 key 的右邊,所有小于 key 的元素都位于 key 的左邊 //而此時(shí) i==j 即表示 key 應(yīng)該插入的位置,即原先的 arr[start]元素的最終位置 arr[i]=key; quickSort(arr,start,i-1); quickSort(arr,i+1,end); } } -
程序分析
快速排序在每一趟排序中，先選定一個(gè)軸，通過交換來確定軸的最終位置辆亏，在一趟排序后风秤，大于或小于該軸的元素會位于該軸的兩側(cè)。- 外層循環(huán)用來控制這趟排序是否結(jié)束扮叨，當(dāng) i 等于 j 的時(shí)候缤弦，說明待排序列的比較已經(jīng)結(jié)束，該位置即為軸 key 的最終有序位置彻磁。
- 在第一個(gè)內(nèi)層循環(huán)中碍沐，先從后向前循環(huán)查找第一個(gè)小于 key 的元素，如果存在則退出循環(huán)并將該元素交換至 key 的 i 位置衷蜓，然后再進(jìn)入第二個(gè)內(nèi)層循環(huán)累提。如果沒有存在一個(gè)小于 key 的元素，說明在從后向前的查找中磁浇，key 后面的元素都大于 key刻恭，因此，說明 key 就是在正確的有序位置扯夭。
- 在第二個(gè)內(nèi)層循環(huán)中鳍贾，從前向后循環(huán)查找第一個(gè)大于 key 的元素，如果存在則退出循環(huán)并交換至當(dāng)前 j 位置交洗，然后退出該循環(huán)骑科，判斷 i 是否等于 j，不等于則說明該趟還沒比較結(jié)束构拳，繼續(xù)從第一個(gè)內(nèi)層循環(huán)開始咆爽，繼續(xù)排序操作。直至 i 等于 j置森。
優(yōu)化分析
快速排序?qū)τ谠綗o序的序列效果越好斗埂，但對于基本有序序列，在選定 key 后凫海，有可能剩余的 N-1個(gè)元素均大于或小于 key呛凶，導(dǎo)致分而治之的效果不明顯，沒有明顯的均分待排序列行贪，使得效率接近于插入排序$O(n^2)$的效果漾稀。改善這樣的情況，可以嘗試采用隨機(jī) key 的方式建瘫，每一趟排序崭捍，均在當(dāng)前 start~end 中隨機(jī)選取 key 作為軸，而不是始終設(shè)定為 arr[start]為軸啰脚，盡可能通過隨機(jī)化減少有序影響殷蛇，實(shí)現(xiàn)或接近分治效果。
