|
排序是演算法的必修課 也是基礎的第一課 排序的花樣非常多，一般在演算法或者程式設計中直接用系統內置函式，不自己寫，但是作為練習和演算法思想還是得學一下 |
冒泡排序
冒泡排序（Bubble Sort）是基于交換的排序，每次遍歷需要排序的元素，依次比較相鄰的兩個元素的大小，如果前一個元素大于后一個元素則兩者交換，保證最后一個數字一定是最大的（假設按照從小到大排序），即最后一個元素已經排好序，下一輪只需要保證前面 n-1 個元素的順序即可，
之所以稱為冒泡，是因為最大/最小的數，每一次都往后面冒，就像是水里面的氣泡一樣，
排序（假設從小到大）的步驟如下：
- 從頭開始，比較相鄰的兩個數，如果第一個數比第二個數大，那么就交換它們位置，
- 從開始到最后一對比較完成，一輪結束后，最后一個元素的位置已經確定，
- 除了最后一個元素以外，前面的所有未排好序的元素重復前面兩個步驟，
- 重復前面 1 ～ 3 步驟，直到所有元素都已經排好序，
例如，我們需要對陣列 [98，90，34，56，21] 進行從小到大排序，每一次都需要將陣列最大的移動到陣列尾部，
交換具體邏輯如下圖所示：
接下來兩輪排序確定好了第二個和第三個的位置，其實這個陣列已經完成排序了，一共 5 個數，冒泡 4 次即可，
紫色表示已經排好的元素，橙紅色表示正在比較/交換的元素，可以看出前面兩次排序之后，已經確定好了最大兩個數的位置，
冒泡排序Java代碼
查看代碼
public class BubbleSort {
public static void bubbleSort(int[] nums) {
int size=nums.length;
for(int i=0;i<size-1;i++) {
System.out.println("第"+(i+1)+"輪交換開始");
for(int j=0;j<size-1-i;j++) {
if(nums[j]>nums[j+1]) {
int temp=nums[j+1];
nums[j+1]=nums[j];
nums[j]=temp;
}
printf(nums);
}
}
}
public static void printf(int[] nums) {
for (int num : nums) {
System.out.print(num + " ");
}
System.out.println("");
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[]nums = new int[]{98,90,34,56,21};
printf(nums);
bubbleSort(nums);
}
}冒泡排序Java代碼運行結果
選擇排序
前面說的冒泡排序是每一輪比較確定最后一個元素，中間程序不斷地交換，而選擇排序就是每次選擇剩下的元素中最小的那個元素，與當前索引位置的元素交換，直到所有的索引位置都選擇完成，
排序的步驟如下：
- 從第一個元素開始，遍歷其后面的元素，找出其后面比它更小的且最小的元素，若有，則兩者交換，保證第一個元素最小，
- 對第二個元素一樣，遍歷其后面的元素，找出其后面比它更小的且最小的元素，若存在，則兩者交換，保證第二個元素在未排序的數中（除了第一個元素）最小，
- 依次類推，直到最后一個元素，那么陣列就已經排好序了，
比如，現在我們需要對 [98，90，34，56，21] 進行排序，動態排序程序如下：
前面兩輪選擇排序已經分別將 21 和 34 選擇出來，放到最前面的位置，
剩下的排序是確定 56 和 90 的位置，最后一個 98 自然就是最大的數，不需要再排序，
選擇排序Java代碼
查看代碼
public class SelectionSort {
public static void printf(int[] nums) {
for (int num : nums) {
System.out.print(num + " ");
}
System.out.println("");
}
public static void selectionSort(int []nums) {
int times=0;
int size=nums.length;
int minIndex,temp;
for(int i=0;i<size-1;i++) {
System.out.print("第" + (i + 1) + "輪選擇開始：");
minIndex=i;
for(int j=i+1;j<size;j++) {
times++;
if(nums[j]<nums[minIndex]) {
minIndex=j;
}
}
System.out.println("交換 "+nums[i]+"和"+nums[minIndex]);
temp=nums[i];
nums[i]=nums[minIndex];
nums[minIndex]=temp;
printf(nums);
}
System.out.println("比較次數："+times);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[]nums = new int[]{98,90,34,56,21};
printf(nums);
selectionSort(new int[]{98,90,34,56,21});
}
}選擇排序Java代碼運行結果
插入排序
選擇排序是每次選擇出最小的放到已經排好的陣列后面，而插入排序是依次選擇一個元素，插入到前面已經排好序的陣列中間，確保它處于正確的位置，當然，這是需要已經排好的順序陣列不斷移動，步驟描述如下：
- 從第一個元素開始，可以認為第一個元素已經排好順序，
- 取出后面一個元素
n，在前面已經排好順序的陣列里從尾部往頭部遍歷，假設正在遍歷的元素為nums[i]，如果num[i]>n，那么將nums[i]移動到后面一個位置，直到找到已經排序的元素小于或者等于新元素的位置，將n放到新騰空出來的位置上，如果沒有找到，那么nums[i]就是最小的元素，放在第一個位置， - 重復上面的步驟 2，直到所有元素都插入到正確的位置，
以陣列 [98，90，34，56，21] 為例，動態排序程序如下：
具體的排序程序如下：
第一次假設第一個元素已經排好，第二個元素 90 往前面查找插入位置，正好查找到 98 的位置插入，第二輪是 34 選擇插入位置，選擇了第一個元素 90 的位置插入，其后面的元素后移，
第三輪排序則是 56 選擇適合自己的位置插入，第四輪是最后一個元素 21 往前查找適合的位置插入：
插入排序Java代碼
查看代碼
public class InsertionSort {
public static void printf(int[] nums) {
for (int num : nums) {
System.out.print(num + " ");
}
System.out.println("");
}
public static void insertionSort(int[] nums) {
if(nums==null) {
return;
}
int size=nums.length;
int index,temp;
for(int i=1;i<size;i++) {
// 當前選擇插入的元素前面一個索引值
index=i-1;
// 當前需要插入的元素
temp=nums[i];
while(index>=0&&nums[index]>temp) {
nums[index+1]=nums[index];
index--;
}
// 插入空出來的位置
nums[index+1]=temp;
System.out.print("第" + (i) + "輪插入結果：");
printf(nums);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[]nums = new int[]{98,90,34,56,21};
printf(nums);
insertionSort(nums);
}
}
插入排序Java代碼運行結果
希爾排序
希爾排序（Shell's Sort）又稱“縮小增量排序”（Diminishing Increment Sort），是插入排序的一種更高效的改進版本，同時該演算法是首次沖破 O(n^2) 的演算法之一，
插入排序的痛點在于不管是否是大部分有序，都會對元素進行比較，如果最小數在陣列末尾，想要把它移動到陣列的頭部是比較費勁的，希爾排序是在陣列中采用跳躍式分組，按照某個增量 gap 進行分組，分為若干組，每一組分別進行插入排序，再逐步將增量 gap 縮小，再每一組進行插入排序，回圈這個程序，直到增量為 1，
希爾排序基本步驟如下：
- 選擇一個增量
gap，一般開始是陣列的一半，將陣列元素按照間隔為gap分為若干個小組， - 對每一個小組進行插入排序，
- 將
gap縮小為一半，重新分組，重復步驟 2（直到gap為 1 的時候基本有序，稍微調整一下即可），
以陣列 [98，90，34，56，21，11，43，61] 為例子
同樣以陣列 [98，90，34，56，21，11，43，61] 為例子，元素個數為 8，首次 gap 為 4，元素分為 4 組，同顏色視為一組，對相同顏色進行插入排序，這樣保證了大致位置上大的元素在后面，小的元素在前面，
第二輪希爾排序，gap = 4/2 = 2，則元素可以分為兩組，同顏色視為一組，仍是對同組的進行插入排序：
最后一輪，gap= 2/2 =1，則所有元素視為一組，相當于對所有元素進行插入排序，這時候元素已經基本有序，只需要做小范圍的調整即可，
希爾排序是非穩定排序演算法，每一組的排序，都確保了這一組的資料基本有序，整體上也是基本有序，
希爾排序Java代碼
查看代碼
public class ShellSort {
public static void printf(int[] nums) {
for (int num : nums) {
System.out.print(num + " ");
}
System.out.println("");
}
public static void shellSort(int[] nums) {
int times=1;
for(int gap=nums.length/2;gap>0;gap/=2) {
System.out.print("第" + (times++) + "輪希爾排序, gap= " + gap + " ,結果：");
for(int i = gap;i<nums.length;i++) {
int j=i;
int temp=nums[j];
if(nums[j]<nums[j-gap]) {
while(j-gap>=0&&temp<nums[j-gap]) {
nums[j]=nums[j-gap];
j-=gap;
}
nums[j]=temp;
}
}
printf(nums);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] nums = new int[]{98, 90, 34, 56, 21, 11, 43, 61};
printf(nums);
shellSort(nums);
}
}希爾排序Java代碼運行結果
快速排序
快速排序比較有趣，選擇陣列的一個數作為基準數，一趟排序，將陣列分割成為兩部分，一部分均小于/等于基準數，另外一部分大于/等于基準數，然后分別對基準數的左右兩部分繼續排序，直到陣列有序，這體現了分而治之的思想，其中還應用到挖坑填數的策略，
演算法的步驟如下：
- 從陣列中挑一個元素作為基準數，一般情況下我們選擇第一個
nums[i]，保存為standardNum，可以理解為nums[i]坑位的數被拎出來了，留下空的坑位， - 取陣列的左邊界索引指標
i，右邊界索引指標j，j從右邊往左邊，尋找到比standardNum小的數，停下來，寫到nums[i]的坑位，nums[j]的坑位空出來， 索引指標i從左邊往右邊找，尋找比standardNum大的數，停下來，寫到nums[j]的坑位，這個時候，num[i]的坑位空出來（前提是i和j不相撞）， - 上面的
i和j回圈步驟 2，直到兩個索引指標i和j相撞，將基準值standardNum寫到坑位nums[i]中，這時候，standardNum左邊的數都小于等于它本身，右邊的數都大于等于它本身， - 分別對
standardNum左邊的子陣列和右邊的子陣列，回圈執行前面的 1，2，3，直到不可再分，并且有序，
以陣列 [61，90，34，56，21，11，43，68] 為例，動態排序程序如下：
第一輪排序是所有元素，以第一個數 61 為基準值，排序完成則左邊的數都小于等于 61，右邊的數都大于等于 61，
分別對 61 左邊的數 [ 43，11，34，56，21 ] 和右邊的數 [ 90，68 ] 分別進行快速排序，這里體現了分治的思想，首先我們來看左邊 [ 43，11，34，56，21 ] 的排序，
左邊又確定了以 43 為分割的陣列 [ 21，11，34 ] 以及 [ 64 ]，由于遞回的原因，再次先對左邊 [ 21，11，34 ] 進行排序：
左邊 [ 21，11，34 ] 排序后，以 21 為分割線，左右各自只有一個數，自然已經停止，上面 43 的右邊也只有一個元素，所以也已經是有序的，
至此，61 以及左邊都是有序的，再對 61 右邊的 [ 90，68 ] 進行快速排序：
快速排序也就完成了
快速排序Java代碼
查看代碼
public class QuickSort {
public static void printf(int[] nums) {
for (int num : nums) {
System.out.print(num + " ");
}
System.out.println("");
}
public static void quickSort(int[] nums) {
quickSort(nums,0,nums.length-1);
}
public static void quickSort(int nums[],int left,int right) {
System.out.println("[left,right]:["+left+","+right+"]");
if(left<right) {
int i=left,j=right,standardNum=nums[left];
while(i<j) {
while(i<j&&nums[j]>=standardNum) {
j--;
}
System.out.print("standardNum:"+standardNum+",第1個小于等于standardNum的數："+nums[j]);
if(i<j) {
nums[i]=nums[j];
i++;
}
while(i<j&&nums[i]<standardNum) {
i++;
}
System.out.println(",第1個大于等于standardNum的數："+nums[i]);
if(i<j) {
nums[j]=nums[i];
j--;
}
}
nums[i]=standardNum;
printf(nums);
quickSort(nums,left,i-1);
printf(nums);
quickSort(nums,i+1,right);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] nums = new int[]{61, 90, 34, 56, 21, 11, 43, 68};
printf(nums);
quickSort(nums);
}
}快速排序Java代碼運行結果
實驗總結
前面學習了五種排序演算法，它們的復雜度以及特點在這里總結一下：
- 冒泡排序：基本最慢，時間復雜度最好為 O(n)，最壞為 O(n2)，平均時間復雜度為 O(n2)，空間復雜度為 O(1)，穩定排序演算法，
- 選擇排序：時間復雜度很穩定，最好最壞或者平均都是 O(n2)，空間復雜度為 O(1)，可以做到穩定排序，
- 插入排序：時間復雜度最好為 O(n)，最壞為 O(n2)，平均時間復雜度為 O(n2)，空間復雜度為 O(1)，穩定排序演算法，
- 希爾排序：希爾增量下最壞的情況時間復雜度是 O(n2)，最好的時間復雜度是 O(n) （也就是陣列已經有序），平均時間復雜度是 O(n3/2)，屬于不穩定排序，
- 快速排序：時間復雜度最差的情況是 O(n2)，平均時間復雜度為 O(nlogn)，空間復雜度，雖然快排本身沒有申請額外的空間，但是遞回需要使用堆疊空間，遞回數的深度是 log2n，空間復雜度也就是 O( log2n)，屬于不穩定排序，
每一種排序，都有其優缺點，我們應該根據場景選擇合適的排序演算法，
關于時間復雜度，我們一般使用大 O 表示法，它是一種體現演算法時間復雜度的計法，通俗來講，就是隨著問題規模的增長，演算法執行的指令數也在增長，時間復雜度越高，則執行時間增長越快，常見的演算法時間復雜度由好到壞依次為： Ο(1) ＜ Ο(log2n) ＜ Ο(n) ＜ Ο(nlog2n) ＜ Ο(n^2) ＜ Ο(n^3) ＜ … ＜ Ο(2^n) ＜ Ο(n!) ，一個優秀的演算法，自然少不了對低時間復雜度的追求，
但是我們也不能自然也不能忽略空間復雜度，也就是隨著問題規模的增長，計算程序中所需要的存盤空間增長的速度（增長率），其計算方式與時間復雜度類似，時間復雜度和空間復雜度是息息相關的兩個概念，隨著計算機空間越拉越大，不少的演算法傾向于以空間換時間，這也是取舍的策略，
在黑夜里夢想著光，心中覆寫悲傷，在悲傷里忍受孤獨，空守一絲溫暖， 我的淚水是無底深海，對你的愛已無言，相信無盡的力量，那是真愛永在， 我的信仰是無底深海，澎湃著心中火焰，燃燒無盡的力量，那是忠誠永在轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/412978.html
標籤：其他
上一篇：線性表的基本操作