摘要:冒泡排序插入排序選擇排序堆排序父節點索引尾節點索引歸并排序快速排序附錄交換方法基于策略模式的主程序實現定義一個數組構造函數初始化數組遍歷數組中每一個元素展示
「博客搬家」 原地址: 簡書 原發表時間: 2017-08-17
網上有很多排序算法的總結,不過有很多缺點,比如有些根本就是錯的,無法通過測試用例,有些過于冗長。所以我總結了一套短小精悍的 Java 實現,經測試,該套實現可通過牛客網的關于此的所有測試用例。
1. 冒泡排序public class BubbleSort implements KySort { public void kySort(int[] a, int size) { for (int i = 0; i < size - 1; i++) { for (int j = 0; j < size - i - 1; j++) { if (a[j] > a[j + 1]) { swap(a, j, j + 1); } } } } }2. 插入排序
public class InsertSort implements KySort { public void kySort(int[] a, int size) { for (int i = 1; i < size; i++) { int temp = a[i]; int j = i; while (j > 0 && a[j - 1] > temp) { a[j] = a[j - 1]; j--; } a[j] = temp; } } }3. 選擇排序
public class SelectSort implements KySort { public void kySort(int[] a, int size) { for (int i = 0; i < size - 1; i++) { int min = i; for (int j = i + 1; j < size; j++) { if (a[j] < a[min]) { min = j; } } if (i != min) { swap(a, i, min); } } } }4. 堆排序
public class HeapSort implements KySort { public void kySort(int[] a, int n) { for (int i = n / 2; i >= 0; i--) { heapAdjust(a, i, n - 1); } for (int i = n - 1; i > 0; i--) { swap(a, 0, i); heapAdjust(a, 0, i - 1); } } /** * @param index 父節點索引 * @param n 尾節點索引 */ private void heapAdjust(int[] a, int index, int n) { int temp = a[index]; for (int child = index * 2 + 1; child <= n; child = index * 2 + 1) { if (child < n && a[child] < a[child + 1]) { child++; } if (temp > a[child]) break; a[index] = a[child]; index = child; } a[index] = temp; } }5. 歸并排序
public class MergeSort implements KySort { public void kySort(int[] a, int size) { sort(a, 0, size - 1, new int[a.length]); } private void sort(int[] a, int left, int right, int[] temp) { if (left >= right) return; int mid = (left + right) / 2; sort(a, left, mid, temp); sort(a, mid + 1, right, temp); merge(a, left, mid, right, temp); } private void merge(int[] a, int left, int mid, int right, int[] temp) { int k = left; int i = left; int j = mid + 1; 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++]; } while (left <= right) { a[left] = temp[left]; left++; } } }6. 快速排序
public class QuickSort implements KySort { @Override public void kySort(int[] a, int size) { quickSort(a, 0, size - 1); } private void quickSort(int[] a, int left, int right) { if (right - left < 2) { if (a[left] > a[right]) swap(a, left, right); return; } int p = middleBy3(a, left, right); quickSort(a, left, p - 1); quickSort(a, p + 1, right); } private int middleBy3(int[] a, int left, int right) { int p = (left + right) / 2; int end = right; if (a[left] > a[p]) swap(a, left, p); if (a[left] > a[right]) swap(a, left, right); if (a[p] > a[right]) swap(a, p, right); int temp = a[p]; swap(a, p, right); while (true) { while (a[++left] < temp) ; while (a[--right] > temp) ; if (left >= right) break; else swap(a, left, right); } swap(a, left, end); return left; } }7. 附錄 7.1 交換方法
public class Util { public static void swap(int[] a, int i, int j) { int k = a[i]; a[i] = a[j]; a[j] = k; } }7.2 基于策略模式的主程序實現
public class SortMain { private static KySort sorter; private int[] a;//定義一個數組 private SortMain(int... values) { //構造函數 a = values; } public static void main(String[] args) { setSorter(new QuickSort()); SortMain arr; arr = new SortMain(5, 4, 3, 2, 1, 0); arr.display(); arr.kySort(); arr.display(); System.out.println("--------"); arr = new SortMain(54, 35, 48, 36, 27, 12, 44, 44, 8, 14, 26, 17, 28); arr.display(); arr.kySort(); arr.display(); System.out.println("--------"); arr = new SortMain(32, 103, 24, 88, 95, 70, 97, 15, 102, 6, 79, 46, 51, 37, 93, 108, 9, 58, 53, 58, 79, 36, 58, 91, 78, 58, 61, 81); //初始化數組 arr.display(); arr.kySort(); arr.display(); } private static void setSorter(KySort sorter) { SortMain.sorter = sorter; } private void display() { for (int i : a) { //遍歷數組中每一個元素 System.out.print(i + " "); //展示 } System.out.println(); } private void kySort() { sorter.kySort(a, a.length); } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/68246.html
摘要:算法描述冒泡排序是一種簡單的排序算法。算法描述和實現一般來說,插入排序都采用在數組上實現。平均情況希爾排序年發明第一個突破的排序算法是簡單插入排序的改進版它與插入排序的不同之處在于,它會優先比較距離較遠的元素。 前言 讀者自行嘗試可以想看源碼戳這,博主在github建了個庫,讀者可以Clone下來本地嘗試。此博文配合源碼體驗更棒哦~~~ 個人博客:Damonare的個人博客 原文地址:...
摘要:此專欄文章是對力扣上算法題目各種方法的總結和歸納整理出最重要的思路和知識重點并以思維導圖形式呈現當然也會加上我對導圖的詳解目的是為了更方便快捷的記憶和回憶算法重點不用每次都重復看題解畢竟算法不是做了一遍就能完全記住的所 ...
摘要:數據結構與算法常用數據結構及其實現經過前面文章的鋪墊,我們鞏固了基礎數據結構的知識,接下來就可以進入算法的鞏固階段了。首先我們來看常見的排序算法。同樣的小規模數據轉換為插入排序會有效果提升。它只能對整數進行排序。 數據結構與算法——常用數據結構及其Java實現經過前面文章的鋪墊,我們鞏固了基礎數據結構的知識,接下來就可以進入算法的鞏固階段了。首先我們來看常見的排序算法。 冒泡排序 原理...
閱讀 2954·2021-11-17 09:33
閱讀 3118·2021-11-16 11:52
閱讀 482·2021-09-26 09:55
閱讀 2975·2019-08-30 15:52
閱讀 1313·2019-08-30 15:44
閱讀 1257·2019-08-30 13:59
閱讀 796·2019-08-30 13:08
閱讀 1157·2019-08-30 10:50