版權信息 原文鏈接： [Java常用排序算法/程序員必須掌握的8大排序算法](http://blog.csdn.net/qy1387/article/details/7752973) --- 本文由網絡資料整理而來，如有問題，歡迎指正！ 分類： 1）插入排序（直接插入排序、希爾排序） 2）交換排序（冒泡排序、快速排序） 3）選擇排序（直接選擇排序、堆排序） 4）歸并排序 5）分配排序（基數排序） 所需輔助空間最多：歸并排序 所需輔助空間最少：堆排序 平均速度最快：快速排序 不穩定：快速排序，希爾排序，堆排序。 **** ~~~java // 排序原始數據 private static final int[] NUMBERS = {49, 38, 65, 97, 76, 13, 27, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51}; ~~~ **?1\. 直接插入排序** 基本思想：在要排序的一組數中，假設前面(n-1)[n>=2] 個數已經是排 好順序的，現在要把第n個數插到前面的有序數中，使得這n個數 也是排好順序的。如此反復循環，直到全部排好順序。  ~~~java ?public static void insertSort(int[] array) { ? ? ?for (int i = 1; i < array.length; i++) { ? ? ? ? ?int temp = array[i]; ? ? ? ? ?int j = i - 1; ? ? ? ? ?for (; j >= 0 && array[j] > temp; j--) { ? ? ? ? ? ? ?//將大于temp的值整體后移一個單位 ? ? ? ? ? ? ?array[j + 1] = array[j]; ? ? ? ? ?} ? ? ? ? ?array[j + 1] = temp; ? ? ?} ? ? ?System.out.println(Arrays.toString(array) + " insertSort"); ?} ~~~ **2**.?**希爾排序** 希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。希爾排序是非穩定排序算法。 希爾排序是基于插入排序的以下兩點性質而提出改進方法的： 插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率； 但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位。 先取一個正整數d1 < n, 把所有相隔d1的記錄放一組，每個組內進行直接插入排序；然后d2 < d1，重復上述分組和排序操作；直至di = 1，即所有記錄放進一個組中排序為止。  ~~~java public static void shellSort(int[] array) { ? ? int i; ? ? int j; ? ? int temp; ? ? int gap = 1; ? ? int len = array.length; ? ? while (gap < len / 3) { gap = gap * 3 + 1; } ? ? for (; gap > 0; gap /= 3) { ? ? ? ? for (i = gap; i < len; i++) { ? ? ? ? ? ? temp = array[i]; ? ? ? ? ? ? for (j = i - gap; j >= 0 && array[j] > temp; j -= gap) { ? ? ? ? ? ? ? ? array[j + gap] = array[j]; ? ? ? ? ? ? } ? ? ? ? ? ? array[j + gap] = temp; ? ? ? ? } ? ? } ? ? System.out.println(Arrays.toString(array) + " shellSort"); } ~~~ ? **3**.?**簡單選擇排序** 基本思想：在要排序的一組數中，選出最小的一個數與第一個位置的數交換； 然后在剩下的數當中再找最小的與第二個位置的數交換，如此循環到倒數第二個數和最后一個數比較為止。  ~~~java public static void selectSort(int[] array) { ? ? int position = 0; ? ? for (int i = 0; i < array.length; i++) { ? ? ? ? int j = i + 1; ? ? ? ? position = i; ? ? ? ? int temp = array[i]; ? ? ? ? for (; j < array.length; j++) { ? ? ? ? ? ? if (array[j] < temp) { ? ? ? ? ? ? ? ? temp = array[j]; ? ? ? ? ? ? ? ? position = j; ? ? ? ? ? ? } ? ? ? ? } ? ? ? ? array[position] = array[i]; ? ? ? ? array[i] = temp; ? ? } ? ? System.out.println(Arrays.toString(array) + " selectSort"); } ~~~ ? **4**.?**堆排序** 基本思想：堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。 堆的定義如下：具有n個元素的序列（h1,h2,...,hn),當且僅當滿足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)時稱之為堆。在這里只討論滿足前者條件的堆。由堆的定義可以看出，堆頂元素（即第一個元素）必為最大項（大頂堆）。完全二叉樹可以很直觀地表示堆的結構。堆頂為根，其它為左子樹、右子樹。初始時把要排序的數的序列看作是一棵順序存儲的二叉樹，調整它們的存儲序，使之成為一個堆，這時堆的根節點的數最大。然后將根節點與堆的最后一個節點交換。然后對前面(n-1)個數重新調整使之成為堆。依此類推，直到只有兩個節點的堆，并對它們作交換，最后得到有n個節點的有序序列。從算法描述來看，堆排序需要兩個過程，一是建立堆，二是堆頂與堆的最后一個元素交換位置。所以堆排序有兩個函數組成。一是建堆的滲透函數，二是反復調用滲透函數實現排序的函數。 建堆：  交換，從堆中踢出最大數  剩余結點再建堆，再交換踢出最大數  依次類推：最后堆中剩余的最后兩個結點交換，踢出一個，排序完成。 ~~~java public static void heapSort(int[] array) { ? ? /* ? ? ?* ?第一步：將數組堆化 ? ? ?* ?beginIndex = 第一個非葉子節點。 ? ? ?* ?從第一個非葉子節點開始即可。無需從最后一個葉子節點開始。 ? ? ?* ?葉子節點可以看作已符合堆要求的節點，根節點就是它自己且自己以下值為最大。 ? ? ?*/ ? ? int len = array.length - 1; ? ? int beginIndex = (len - 1) >> 1; ? ? for (int i = beginIndex; i >= 0; i--) { ? ? ? ? maxHeapify(i, len, array); ? ? } ? ? /* ? ? ?* 第二步：對堆化數據排序 ? ? ?* 每次都是移出最頂層的根節點A[0]，與最尾部節點位置調換，同時遍歷長度 - 1。 ? ? ?* 然后從新整理被換到根節點的末尾元素，使其符合堆的特性。 ? ? ?* 直至未排序的堆長度為 0。 ? ? ?*/ ? ? for (int i = len; i > 0; i--) { ? ? ? ? swap(0, i, array); ? ? ? ? maxHeapify(0, i - 1, array); ? ? } ? ? System.out.println(Arrays.toString(array) + " heapSort"); } private static void swap(int i, int j, int[] arr) { ? ? int temp = arr[i]; ? ? arr[i] = arr[j]; ? ? arr[j] = temp; } /** ?* 調整索引為 index 處的數據，使其符合堆的特性。 ?* ?* @param index 需要堆化處理的數據的索引 ?* @param len ? 未排序的堆（數組）的長度 ?*/ private static void maxHeapify(int index, int len, int[] arr) { ? ? int li = (index << 1) + 1; // 左子節點索引 ? ? int ri = li + 1; ? ? ? ? ? // 右子節點索引 ? ? int cMax = li; ? ? ? ? ? ? // 子節點值最大索引，默認左子節點。 ? ? if (li > len) { ? ? ? ? return; ? ? ? // 左子節點索引超出計算范圍，直接返回。 ? ? } ? ? if (ri arr[li]) // 先判斷左右子節點，哪個較大。 ? ? { cMax = ri; } ? ? if (arr[cMax] > arr[index]) { ? ? ? ? swap(cMax, index, arr); ? ? ?// 如果父節點被子節點調換， ? ? ? ? maxHeapify(cMax, len, arr); ?// 則需要繼續判斷換下后的父節點是否符合堆的特性。 ? ? } } ~~~ ? **5**.?**冒泡排序** 基本思想：在要排序的一組數中，對當前還未排好序的范圍內的全部數，自上而下對相鄰的兩個數依次進行比較和調整，讓較大的數往下沉，較小的往上冒。即：每當兩相鄰的數比較后發現它們的排序與排序要求相反時，就將它們互換。  ~~~java public static void bubbleSort(int[] array) { ? ? int temp = 0; ? ? for (int i = 0; i < array.length - 1; i++) { ? ? ? ? for (int j = 0; j < array.length - 1 - i; j++) { ? ? ? ? ? ? if (array[j] > array[j + 1]) { ? ? ? ? ? ? ? ? temp = array[j]; ? ? ? ? ? ? ? ? array[j] = array[j + 1]; ? ? ? ? ? ? ? ? array[j + 1] = temp; ? ? ? ? ? ? } ? ? ? ? } ? ? } ? ? System.out.println(Arrays.toString(array) + " bubbleSort"); } ~~~ **6**.?**快速排序** 基本思想：選擇一個基準元素,通常選擇第一個元素或者最后一個元素,通過一趟掃描，將待排序列分成兩部分,一部分比基準元素小,一部分大于等于基準元素,此時基準元素在其排好序后的正確位置,然后再用同樣的方法遞歸地排序劃分的兩部分。  ~~~java public static void quickSort(int[] array) { ? ? _quickSort(array, 0, array.length - 1); ? ? System.out.println(Arrays.toString(array) + " quickSort"); } private static int getMiddle(int[] list, int low, int high) { ? ? int tmp = list[low]; ? ?//數組的第一個作為中軸 ? ? while (low < high) { while (tmp < list[high]) { high--; } ? ? ? ? list[low] = list[high]; ? //比中軸小的記錄移到低端 ? ? ? ? while (low < high && list[low] <= tmp) { ? ? ? ? ? ? low++; ? ? ? ? } ? ? ? ? list[high] = list[low]; ? //比中軸大的記錄移到高端 ? ? } ? ? list[low] = tmp; ? ? ? ? ? ? ?//中軸記錄到尾 ? ? return low; ? ? ? ? ? ? ? ? //返回中軸的位置 } private static void _quickSort(int[] list, int low, int high) { ? ? if (low < high) { ? ? ? ? int middle = getMiddle(list, low, high); ?//將list數組進行一分為二 ? ? ? ? _quickSort(list, low, middle - 1); ? ? ?//對低字表進行遞歸排序 ? ? ? ? _quickSort(list, middle + 1, high); ? ? //對高字表進行遞歸排序 ? ? } } ~~~ **7、歸并排序** 基本排序：歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。  ~~~java public static void mergingSort(int[] array) { ? ? sort(array, 0, array.length - 1); ? ? System.out.println(Arrays.toString(array) + " mergingSort"); } private static void sort(int[] data, int left, int right) { ? ? if (left < right) { ? ? ? ? //找出中間索引 ? ? ? ? int center = (left + right) / 2; ? ? ? ? //對左邊數組進行遞歸 ? ? ? ? sort(data, left, center); ? ? ? ? //對右邊數組進行遞歸 ? ? ? ? sort(data, center + 1, right); ? ? ? ? //合并 ? ? ? ? merge(data, left, center, right); ? ? } } private static void merge(int[] data, int left, int center, int right) { ? ? int[] tmpArr = new int[data.length]; ? ? int mid = center + 1; ? ? //third記錄中間數組的索引 ? ? int third = left; ? ? int tmp = left; ? ? while (left <= center && mid <= right) { ? ? ? ? //從兩個數組中取出最小的放入中間數組 ? ? ? ? if (data[left] <= data[mid]) { ? ? ? ? ? ? tmpArr[third++] = data[left++]; ? ? ? ? } else { ? ? ? ? ? ? tmpArr[third++] = data[mid++]; ? ? ? ? } ? ? } ? ? //剩余部分依次放入中間數組 ? ? while (mid <= right) { ? ? ? ? tmpArr[third++] = data[mid++]; ? ? } ? ? while (left <= center) { ? ? ? ? tmpArr[third++] = data[left++]; ? ? } ? ? //將中間數組中的內容復制回原數組 ? ? while (tmp <= right) { ? ? ? ? data[tmp] = tmpArr[tmp++]; ? ? } } ~~~ **8、基數排序** 基本思想：將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然后，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后,數列就變成一個有序序列。  ~~~java public static void radixSort(int[] array) { ? ? //首先確定排序的趟數; ? ? int max = array[0]; ? ? for (int i = 1; i < array.length; i++) { ? ? ? ? if (array[i] > max) { ? ? ? ? ? ? max = array[i]; ? ? ? ? } ? ? } ? ? int time = 0; ? ? //判斷位數; ? ? while (max > 0) { ? ? ? ? max /= 10; ? ? ? ? time++; ? ? } ? ? //建立10個隊列; ? ? ArrayList> queue = new ArrayList<>(); ? ? for (int i = 0; i < 10; i++) { ? ? ? ? ArrayList queue1 = new ArrayList<>(); ? ? ? ? queue.add(queue1); ? ? } ? ? //進行time次分配和收集; ? ? for (int i = 0; i < time; i++) { ? ? ? ? //分配數組元素; ? ? ? ? for (int anArray : array) { ? ? ? ? ? ? //得到數字的第time+1位數; ? ? ? ? ? ? int x = anArray % (int)Math.pow(10, i + 1) / (int)Math.pow(10, i); ? ? ? ? ? ? ArrayList queue2 = queue.get(x); ? ? ? ? ? ? queue2.add(anArray); ? ? ? ? ? ? queue.set(x, queue2); ? ? ? ? } ? ? ? ? int count = 0;//元素計數器; ? ? ? ? //收集隊列元素; ? ? ? ? for (int k = 0; k < 10; k++) { ? ? ? ? ? ? while (queue.get(k).size() > 0) { ? ? ? ? ? ? ? ? ArrayList queue3 = queue.get(k); ? ? ? ? ? ? ? ? array[count] = queue3.get(0); ? ? ? ? ? ? ? ? queue3.remove(0); ? ? ? ? ? ? ? ? count++; ? ? ? ? ? ? } ? ? ? ? } ? ? } ? ? System.out.println(Arrays.toString(array) + " radixSort"); } ~~~ **結果** ****