Java輕松入門冒泡 選擇 插入 希爾 歸並排序算法
今天我們主要看一些簡單的排序
常見的時間復雜度
🎈 常數階Ο(1)
🎈 對數階Ο(log2n)
🎈 線性階Ο(n)
🎈 線性對數階Ο(nlog2n)
🎈 平方階Ο(n²)
🎈 立方階Ο(n³)
🎈 K次方階Ο(n^k)
🎈 指數階Ο(2^n)
常見的時間復雜度對應圖
Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n²)<Ο(n³)<…<Ο(2^n) <Ο(n!)<O(n^n)
冒泡排序(Quicksort)
算法描述:
①. 比較相鄰的元素。如果第一個比第二個大,就交換他們兩個。
②. 對每一對相鄰元素作同樣的工作,從開始第一對到結尾的最後一對。這步做完後,最後的元素會是最大的數。
③. 針對所有的元素重復以上的步驟,除瞭最後一個。
④. 持續每次對越來越少的元素重復上面的步驟①~③,直到沒有任何一對數字需要比較。
為瞭直觀感受,在網上找個動態的演示
代碼實現:
當數組中有n個元素時,隻需要進行n-1輪比較,則整個數組就是有序的 public static void bubbleSort(int[] arr) { // 進行i輪比較 for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { //後一位的值大於前一位的值進行值交換 if (arr[j] > arr[j + 1]) { swap(arr, j, j + 1); } } } } public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }
選擇排序(Quicksort)
算法描述:
選擇排序是一種簡單直觀的排序算法。它的工作原理是:第一次從待排序的數據元素中選出最小(或最大)的一個元素,存放在序列的起始位置,然後再從剩餘的未排序元素中尋找到最小(大)元素,繼續放在起始位置知道未排序元素個數為0。
代碼實現:
public static void selectionSort(int[] a) { //每當完成一輪,將會找到最小值,一個i代表一輪 for (int i = 0; i < a.length; i++) { int index = i; //每一輪從i+1開始找,查找是否有比當前值更小的值 for (int j = i + 1; j < a.length; j++) { if (a[index] > a[j]) { index = j; } }//如果index和i不相等說明,下標交換過,也就是說找到更小的數值瞭 if (index != i) { swap(a, index, i); } } } public static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; }
插入排序(insertSort)
算法描述:
插入排序也是一種常見的排序算法,插入排序的思想是:將初始數據分為有序部分和無序部分,每一步將一個無序部分的數據插入到前面已經排好序的有序部分中,直到插完所有元素為止。 插入排序的步驟如下:每次從無序部分中取出一個元素,與有序部分中的元素從後向前依次進行比較,並找到合適的位置,將該元素插到有序組當中。 將數組分為2端,有序數組和無序數組,依次將無序數組中的值插入到無序數組中。
如圖,插入4的過程如下 將數組分為2端,有序數組和無序數組,依次將無序數組中的值插入到無序數組中。
如下圖3 6 7為有序數組,4 2為無序數組。依次將4,2插入到無序數組中即可
如圖,插入4的過程如下
代碼實現:
public static void insertionSort(int[] a) { for (int i = 1; i < a.length; i++) { int temp = a[i]; int j; // 查到合適的插入位置,插入即可 for (j = i - 1; j >= 0 && a[j] > temp; j--) { a[j + 1] = a[j]; } a[j + 1] = temp; } }
希爾排序 (ShellSort)
算法描述:
希爾排序是基於插入排序改進後的算法。因為當數據移動次數太多時會導致效率低下。所以我們可以先讓數組整體有序(剛開始移動的幅度大一點,後面再小一點),這樣移動的次數就會降低,進而提高效率
代碼實現:
public static void shellSort(int[] a) { for (int step = a.length / 2; step > 0; step /= 2) { //接下來的過程類似於插入排序 for (int i = step; i < a.length; i++) { int temp = a[i]; int j; for (j = i - step; j >= 0 && a[j] > temp ; j -= step) { a[j + step] = a[j]; } a[j + step] = temp; } } }
歸並排序(MergetSort)
算法描述:
1.申請空間,使其大小為兩個已經排序序列之和,該空間用來存放合並後的序列;
2.設定兩個指針,最初位置分別為兩個已經排序序列的起始位置;
3.比較兩個指針所指向的元素,選擇相對小的元素放入到合並空間,並移動指針到下一位置;
4.重復步驟 3 直到某一指針達到序列尾;
將另一序列剩下的所有元素直接復制到合並序列尾。
方便理解,直接網上找圖
代碼實現:
public static void mergeSort(int[] a, int left, int right) { // 將數組分段成隻有一個元素 if (left == right) { return; } int mid = (left + right) / 2; mergeSort(a, left, mid);//遞歸 mergeSort(a, mid + 1, right); merge(a, left, mid, right); } public static void merge(int[] a, int left, int mid, int right) { int[] temp = new int[right - left + 1]; int i = left; int j = mid + 1; int k = 0; while (i <= mid && j <= right) { if (a[i] < a[j]) { temp[k++] = a[i++]; } else { temp[k++] = a[j++]; } } // 復制左邊數組剩餘的值 while (i <= mid) { temp[k++] = a[i++]; } // 復制右邊數組剩餘的值 while (j <= right) { temp[k++] = a[j++]; } int index = 0; //把temp全部復制給數組 while (left <= right) { a[left++] = temp[index++]; } }
快速排序(QuickSort)
算法描述:
- 快速排序的執行流程主要分為如下三步
- 從數列中取出一個數作為基準數
- 分區,將比它大的數全放到它的右邊,小於或等於它的數全放到它的左邊
- 再對左右區間重復第二步,直到各區間隻有一個數
代碼實現:
public static void quickSort(int[] a, int left, int right) { if (left >= right) { return; } int index = sort(a, left, right); //得到中間值index,然後一分為二,繼續分 quickSort(a, left, index - 1); quickSort(a, index + 1, right); } public static int sort(int[] a, int left, int right) { //以左邊的a[left]為基準數 int key = a[left]; while (left < right) { // 從right所指位置向前搜索找到第一個關鍵字小於key的記錄和key互相交換 while (left < right && a[right] >= key) { right--; } a[left] = a[right]; // 從left所指位置向後搜索,找到第一個關鍵字大於key的記錄和key互相交換 while (left < right && a[left] <= key) { left++; } a[right] = a[left]; } // 放key值,此時left和right相同 a[left] = key; return left; }
到此這篇關於Java輕松入門冒泡 選擇 插入 希爾 歸並排序算法的文章就介紹到這瞭,更多相關Java 排序算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!