java版十大排序經典算法:完整代碼(2)
快速排序
簡單解釋:
快速排序就是每次找一個基點(第一個元素),然後兩個哨兵,一個從最前面往後走,一個從最後面往前面走,如果後面那個哨兵找到瞭一個比基點大的數停下來,前面那個哨兵找到比基點大的數停下來,然後交換兩個哨兵找到的數,如果找不到最後兩個哨兵就會碰到一起就結束,最後交換基點和哨兵相遇的地方的元素,然後就將一個序列分為比基點小的一部分和比基點大的一部分,然後遞歸左半部分和右半部分,最後的結果就是有序的瞭。
完整代碼:
package com.keafmd.Sequence; /** * Keafmd * * @ClassName: QuickSort * @Description: 快速排序 * @author: 牛哄哄的柯南 * @date: 2021-06-24 10:32 */ public class QuickSort { //快速排序 public static void quickSort(int[] arr) { quickSort(arr, true); } public static void quickSort(int[] arr, boolean ascending) { if (ascending) { quickSort(arr, 0, arr.length - 1, true); } else { quickSort(arr, 0, arr.length - 1, false); } } public static void quickSort(int[] arr, int begin, int end, boolean ascending) { if (ascending) quickSort(arr, begin, end); else quickSortDescending(arr, begin, end); } //快排序升序 -- 默認 public static void quickSort(int[] arr, int begin, int end) { if (begin > end) { //結束條件 return; } int base = arr[begin]; int i = begin, j = end; while (i < j) { // 兩個哨兵(i左邊,j右邊)沒有相遇 while (arr[j] >= base && i < j) { //哨兵j沒找到比base小的 j--; } while (arr[i] <= base && i < j) { //哨兵i沒找到比base大的 i++; } if (i < j) { //如果滿足條件則交換 int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } //最後將基準為與i和j相等位置的數字交換 arr[begin] = arr[i]; arr[i] = base; quickSort(arr, begin, i - 1); //遞歸調用左半數組 quickSort(arr, i + 1, end); //遞歸調用右半數組 } //快排序降序 public static void quickSortDescending(int[] arr, int begin, int end) { if (begin > end) { //結束條件 return; } int base = arr[begin]; int i = begin, j = end; while (i < j) { // 兩個哨兵(i左邊,j右邊)沒有相遇 while (arr[j] <= base && i < j) { //哨兵j沒找到比base大的 j--; } while (arr[i] >= base && i < j) { //哨兵i沒找到比base小的 i++; } if (i < j) { //如果滿足條件則交換 int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } //最後將基準為與i和j相等位置的數字交換 arr[begin] = arr[i]; arr[i] = base; quickSortDescending(arr, begin, i - 1); //遞歸調用左半數組 quickSortDescending(arr, i + 1, end); //遞歸調用右半數組 } }
直接選擇排序
簡單解釋:
數組分為已排序部分(前面)和待排序序列(後面)
第一次肯定所有的數都是待排序的
從待排序的序列中找到最大或最小的那個元素,放到前面的已排序部分,然後一直找,不斷縮小待排序的范圍,直到所有的數都是已排序的瞭
完整代碼:
package com.keafmd.Sequence; /** * Keafmd * * @ClassName: SelectSort * @Description: 選擇排序 * @author: 牛哄哄的柯南 * @date: 2021-06-24 10:33 */ public class SelectSort { //直接選擇排序 public static void selectSort(int[] arr, boolean ascending) { for (int i = 0; i < arr.length; i++) { int m = i; //最小值或最小值的下標 for (int j = i + 1; j < arr.length; j++) { if (ascending ? arr[j] < arr[m] : arr[j] > arr[m]) { m = j; //找到待排序的數中最小或最大的那個數,記錄下標 } } //交換位置 int temp = arr[i]; arr[i] = arr[m]; arr[m] = temp; } } public static void selectSort(int[] arr) { selectSort(arr, true); } }
堆排序
先理解下大頂堆和小頂堆,看圖
大頂堆,雙親結點的值比每一個孩子結點的值都要大。根結點值最大
小頂堆,雙親結點的值比每一個孩子結點的值都要小。根結點值最小
簡單解釋:
構建好大頂堆或小頂堆結構,這樣最上面的就是最大值或最小值,那麼我們取出堆頂元素,然後重新構建結構,一直取,一直重新構建,那麼最後達到排序的效果瞭。
完整代碼:
package com.keafmd.Sequence; /** * Keafmd * * @ClassName: HeapSort * @Description: 堆排序 * @author: 牛哄哄的柯南 * @date: 2021-06-24 10:34 */ public class HeapSort { //堆排序 public static void heapSort(int[] arr) { //對傳入的數組進行建立堆,這裡默認建立大頂堆,進行升序排列 heapSort(arr, true); } public static void heapSort(int[] arr, boolean maxheap) { //1.構建大頂堆 for (int i = arr.length / 2 - 1; i >= 0; i--) { //從第一個非葉子結點從下至上,從右至左調整結構 sift(arr, i, arr.length , maxheap); } //2.調整堆結構+交換堆頂元素與末尾元素 for (int j = arr.length - 1; j > 0; j--) { //現在的數組第一個就是根結點,最小值所在,進行交換,把它放到最右邊 int temp = arr[j]; arr[j] = arr[0]; arr[0] = temp; //重新建立堆 sift(arr, 0, j , maxheap); //重新對堆進行調整 } } //建立堆的方法 /** * 私有方法,隻允許被堆排序調用 * * @param arr 要排序數組 * @param parent 當前的雙親節點 * @param len 數組長度 * @param maxheap 是否建立大頂堆 */ private static void sift(int[] arr, int parent, int len, boolean maxheap) { int value = arr[parent]; //先取出當前元素i for (int child = 2 * parent + 1; child < len; child = child * 2 + 1) { //從parent結點的左子結點開始,也就是2*parent+1處開始 if (child+1 < len && (maxheap ? arr[child] < arr[child + 1] : arr[child] > arr[child + 1])) { //如果左子結點小於右子結點,child指向右子結點 child++; //右孩子如果比左孩子大,我們就將現在的孩子換到右孩子 } //判斷是否符合大頂堆的特性, 如果右孩子大於雙親,自然左孩子也大於雙親,符合 //如果子節點大於父節點,將子節點值賦給父節點(不用進行交換) if (maxheap ? value < arr[child] : value > arr[child]) { arr[parent]=arr[child]; parent = child; } else {//如果不是,說明已經符合我們的要求瞭。 break; } } arr[parent] =value; //將value值放到最終的位置 } }
總結
本篇文章就到這裡瞭,希望能給你帶來幫助,也希望您能夠多多關註WalkonNet的更多內容!