常見的五種排序演算法
- 2019 年 12 月 26 日
- 筆記
冒泡排序
冒泡排序簡介
冒泡排序只會操作相鄰的兩個數據。每次冒泡操作都會對相鄰的兩個元素進行比較，看是否滿足大小關係要求。
如果不滿足就讓它倆互換。一次冒泡會讓至少一個元素移動到它應該在的位置，重複 n 次，就完成了 n 個數據的排序工作。大的數往下沉，小的數往下冒。 穩定、原地排序，最好時間複雜度為O(n)，最壞與平均時間複雜度為O(n2)。
原地排序簡介
原地排序指的是空間複雜度為O(1)的排序演算法。
穩定排序簡介
穩定性指的是：如果待排序列中存在值相等的元素，經過排序之後，相等元素的先後順序沒有改變 比如我們有一組數據 2，9，3，4，8，3，按照大小排序之後就是 2，3，3，4，8，9。 這組數據里有兩個 3。經過某種排序演算法排序之後，如果兩個 3 的前後順序沒有改變，那我們就把這種排序演算法叫作穩定的排序演算法；如果前後順序發生變化，那對應的排序演算法就叫作不穩定的排序演算法。
冒泡程式碼程式碼實現
public class BubbleSort { public static void main(String[] args) { // TODO Auto-generated method stub int[] data=new int[]{2,3,5,4,7,6,9,10,12,11,23,22,18,8}; bubbleSort(data); for(int i=0;i<data.length;i++){ System.out.print(data[i]+" "); } } public static void bubbleSort(int[] data){ if(data.length<=1) return; for(int i=0;i<data.length;i++){ //提前退出冒泡循環的標誌位 boolean flag = false; for(int j=0;j<data.length-1-i;++j){ if(data[j]>data[j+1]){ int temp = data[j]; data[j] = data[j+1]; data[j+1] = temp; flag = true;//有數據交換 } } if(!flag) break;//沒有數據交換，退出 } } }插入排序
插入排序簡介
我們將數組中的數據分為兩個區間，已排序區間和未排序區間。初始已排序區間只有一個元素，就是數組的第一個元素。插入演算法的核心思想是取未排序區間中的元素，在已排序區間中找到合適的插入位置將其插入，並保證已排序區間數據一直有序。重複這個過程，直到未排序區間中元素為空，演算法結束。 穩定、原地排序，最好時間複雜度為O(n)，最壞與平均時間複雜度為O(n2)。
程式碼實現
public class InsertSort { public static void main(String[] args) { // TODO Auto-generated method stub int[] data=new int[]{4,3,2,1,5}; insertSort(data); for(int i=0;i<data.length;i++){ System.out.print(data[i]+" "); } } public static void insertSort(int[] data){ if(data.length<=1) return; for(int i=1;i<data.length;++i){ int value = data[i]; int j=i-1; for(;j>=0;--j){ if(data[j]>value){ data[j+1] = data[j]; }else { break; } } data[j+1]=value; } } }選擇排序
選擇排序簡介
選擇排序演算法的實現思路有點類似插入排序，也分已排序區間和未排序區間。但是選擇排序每次會從未排序區間中找到最小的元素，將其放到已排序區間的末尾。 不穩定、原地排序，最好時間複雜度為O(n2)，最壞與平均時間複雜度為O(n2)。 選擇排序是一種不穩定的排序演算法。選擇排序每次都要找剩餘未排序元素中的最小值，並和前面的元素交換位置，這樣破壞了穩定性。
程式碼實現
public class SelectSort { public static void main(String[] args) { // TODO Auto-generated method stub int[] data=new int[]{2,3,5,4,7,6,9,10,12,11,23,22,18,8}; selectSort(data); for(int i=0;i<data.length;i++){ System.out.print(data[i]+" "); } } public static void selectSort(int[] data){ if(data.length<=1) return; for(int i=0;i<data.length-1;++i){ int minIndex=i; for(int j=i+1;j<data.length;++j){ if(data[j]<data[minIndex]){ minIndex = j; } } int temp = data[i]; data[i] = data[minIndex]; data[minIndex] = temp; } } }歸併排序
歸併排序簡介
如果要排序一個數組，我們先把數組從中間分成前後兩部分，然後對前後兩部分分別排序，再將排好序的兩部分合併在一起，這樣整個數組就都有序了。 歸併排序用的是一種分治思想，它不是原地排序，即空間複雜度不是O(1)，空間複雜度為O(n),不管最好還是最壞或平均，它的時間複雜度都為O(nlogn)，是一個穩定的演算法。
程式碼實現
/** * 歸併排序 * 將需要排序的數組從中間分成兩部分，將這兩部分分別排序，再將排序好的兩部分合併在一起 * 時間複雜度O(nlogn) * 空間複雜度(n) * */ public class MergeSort { public static void main(String[] args) { int[] a= new int[]{1,2,4,3,45,34,23,6,7}; mergeSort(a, 9); for(int i=0;i<a.length;i++){ System.out.print(a[i]+" "); } } private static void mergeSort(int[] a,int n){ mergeIntaily(a, 0, n-1); } private static void mergeIntaily(int[] a,int p,int r){ if(p>=r) return; int q = p+(r-p)/2; mergeIntaily(a, p, q); mergeIntaily(a, q+1, r); merge(a, p, q, r); } private static void merge(int[] a,int p,int q,int r){ int i=p; int j = q+1; int k=0; //申請一個數組，大小與a[p..r]相同 int[] tmp = new int[r-p+1]; //用兩個游標，一個i指向a[p..q]中的第一個元素,一個j指向a[q+1..r]的第一個元素, //如果a[i]<=a[j],就將a[i]的值放進tmp數組中,i後移,否則將a[j]元素放進tmp數組中,j後移 while(i<=q&&j<=r){ if(a[i]<=a[j]){ tmp[k++] = a[i++]; }else { tmp[k++] = a[j++]; } } //判斷那部分數組剩餘 int start = i; int end = q; if(j<=r){ start = j; end = r; } //將剩餘數組放進tmp中 while(start<=end){ tmp[k++] = a[start++]; } //在將tmp數組中的元素放回原數組中 for(i=0;i<=r-p;i++){ a[p+i] = tmp[i]; } } }merge(A[p…r], A[p…q], A[q+1…r]) 這個函數的作用就是，將已經有序的 A[p…q] 和 A[q+1…r] 合併成一個有序的數組，並且放入 A[p…r]。 申請一個臨時數組 tmp，大小與 A[p…r] 相同。我們用兩個游標 i 和 j，分別指向 A[p…q] 和 A[q+1…r] 的第一個元素。比較這兩個元素 A[i] 和 A[j]，如果 A[i]<=A[j]，我們就把 A[i] 放入到臨時數組 tmp，並且 i 後移一位，否則將 A[j] 放入到數組 tmp，j 後移一位。 繼續上述比較過程，直到其中一個子數組中的所有數據都放入臨時數組中，再把另一個數組中的數據依次加入到臨時數組的末尾，這個時候，臨時數組中存儲的就是兩個子數組合併之後的結果了。最後再把臨時數組 tmp 中的數據拷貝到原數組 A[p…r] 中。
快速排序
快速排序簡介
要排序的數組下標從p到r的一組數據，選取從p到r之間的任意一個數據作為pivot(分區點),也是分治思想。 快速排序是原地排序，不穩定，最壞時間複雜度為O(n2)，最好和平均時間複雜度都為O(nlogn)，空間複雜度為O(1)。
程式碼實現
public class QuickSort { public static void main(String[] args) { // TODO Auto-generated method stub int[] a= new int[]{1,2,4,3,45,34,23,6,7}; quickSort(a, 9); for(int i=0;i<a.length;i++){ System.out.print(a[i]+" "); } } private static void quickSort(int[] a,int n){ quickSortIntaily(a, 0, n-1); } private static void quickSortIntaily(int[] a,int p,int r){ if(p>=r) return; //遞歸終止條件 int q= partition(a, p, r); quickSortIntaily(a, p, q-1); quickSortIntaily(a, q+1, r); } //分區函數,隨機選擇一個元素作為pivot，一般選取從p到r的最後一個元素，然後對a[p..r]分區，返回pivot下標 private static int partition(int[] a,int p,int r){ int pivot = a[r]; int i=p; for(int j=p;j<r;++j){ if(a[j]<pivot){ int tmp = a[i]; a[i] = a[j]; a[j] = tmp; ++i; } } int tmp = a[i]; a[i] = a[r]; a[r] = tmp; return i; } }遍歷 p 到 r 之間的數據，將小於 pivot 的放到左邊，將大於 pivot 的放到右邊，將 pivot 放到中間。經過這一步驟之後，數組 p 到 r 之間的數據就被分成了三個部分，前面 p 到 q-1 之間都是小於 pivot 的，中間是 pivot，後面的 q+1 到 r 之間是大於 pivot 的。
歸併與快排區別
- 歸併排序的處理過程是由下到上的，先處理子問題，然後再合併。而快排處理過程是由上到下的，先分區，然後再處理子問題。歸併排序雖然是穩定的、時間複雜度為 O(nlogn) 的排序演算法，但是它是非原地排序演算法；
- 歸併排序和快速排序是兩種稍微複雜的排序演算法，都是使用分治的思想，程式碼都通過遞歸來實現，過程相似；
