甭管什么，筆者就喜歡湊個9。這次，關于排序的算法還是9種，小結一下。排序的算法，盡管有很多的方法例子，但這次是自己總結的，挺有意思算法希望大家喜歡。直接上代碼樓，以下算法，都經過筆者親測，并修改使之有效（粘貼可用）。

package com.css.java.learning.massbag; import java.util.Arrays; /**算法：* 排序相關小結* @author Red_ant* 20181119*/ public class OrderMethod {/*1、冒泡排序* 通過相鄰兩個元素比較的方式，依次選出合適的元素放到* 數組的第i位。*/public static int[] bubbleSort(int[] nums){int num = 0;for (int i = 0; i < nums.length -1; i++) {for (int j = 0; j < nums.length - 1 - i; j++) {//兩兩比較，符合條件的元素居于前面if(nums[j] > nums[j + 1]){num = nums[j];nums[j] = nums[j + 1];nums[j + 1] = num;}}}return nums;}/*2、選擇排序* 每一趟從待排序列，選擇最小的元素放到已排序好的序列末尾，剩下的為待排序序列，* 重復上述步驟，直至完成。*/public static int[] selectSort(int[] nums){int num = 0;for (int i = 0; i < nums.length -1; i++) {int index = i;for (int j = i + 1; j < nums.length; j++) {//選擇合適的元素，直接放到數組的第i位if(nums[index] > nums[j]){index = j;}if(index != i){num = nums[i];nums[i] = nums[index];nums[index] = num;}}}return nums;}/*3、選擇排序：堆排序* 堆排序是一種樹形結構選擇排序* 堆排序需要兩個過程，建立堆，堆頂與堆最后一個元素交換位置。所以堆排序有兩個函數組成：* 建堆的***函數，反復調用***函數實現排序的函數* 基本思路：* 將序列建成一個堆，根據升序降序選擇大頂堆或小頂堆* 將堆頂元素與末尾元素交換，將最大元素沉到數組末端* 重新調整結構，使其滿足堆定義，然后繼續交換堆頂元素與當前末尾元素，反復執行調整+交換步驟，直到整個序列有序。*/public static int[] HeapSorts(int[] nums){//建立大頂for (int i = nums.length/2 - 1; i >= 0; i--) {//從第一個非葉子節點從下至上，從右至左調整結構suitHeap(nums, i, nums.length);}//調整堆結構，交換堆頂元素與 末尾元素for (int j = nums.length - 1; j > 0; j--) {exchangeNum(nums, 0, j);//交換堆頂元素與末尾元素suitHeap(nums, 0, j);}return nums;}private static void exchangeNum(int[] nums, int i, int i2) {int index = nums[i];nums[i] = nums[i2];nums[i2] = index;}private static void suitHeap(int[] nums, int i, int length) {int index = nums[i];//取出當前元素for (int j = i*2 + 1; j < length; j = j*2+1) {//從i節點的左節點開始，即2i+1處if(j+1 < length && nums[j] < nums[j+1]){//如果，左子節點小于右子節點，j指向右子節點j++;}if(nums[j] > index){//如果子節點大于父節點，將子節點賦值給父節點nums[i] = nums[j];i = j;}else{break;}}nums[i] = index;//將index值放到最終位置}/*4、java Arrays排序* 該方法是Arrays類的靜態方法，在需要對數組進行排序時，非常好用*/public static int[] ArraySort(int[] nums){Arrays.sort(nums);return nums;}/*5、插入排序：直接插入排序* 將數組分為兩部分，將后部分元素逐一與前部分元素比較* 然后依據比較結果進行移動元素*/public static int[] insertSort(int[] nums){//從頭部第一個當做已經排序好的，把后面的一個一個的插入到已經排序好的列表中for (int i = 1; i < nums.length; i++) {int j;int index = nums[i];//index為待插入的元素for (j = i; j > 0 && index < nums[j - 1]; j--) {nums[j] = nums[j -1];}nums[j] = index;}return nums;}/*6、插入排序：希爾排序* 建堆，對頂與堆的最后一個元素進行排序* 希爾排序是插入排序的一種，先取一個小于n的整數作為第一個增量，把文件的全部記錄分組。* 所有距離為d1的倍數的記錄放在同一個組中，先在各組內進行直接插入排序。實際上是一種分組插入排序的方法。*/public static int[] shellSrot(int[] nums){int index = nums.length/2;while (index >= 1) {for (int i = index; i < nums.length; i++) {if(nums[i] < nums[i - index]){int j;int x = nums[i];//當前待插入的元素nums[i] = nums[i - index];for (j = i - index; j >= 0 && x < nums[j]; j = j-index) {nums[j + index] = nums[j];}nums[j + index] = x;//插入元素}}index = index/2;}return nums;}/*7、交換排序：快速排序* 基本思想：* A選擇一個基準元素，通常選擇第一個元素或最后一個元素* B通過一趟排序將待排序的記錄分割成獨立的兩部分：記錄均值比基準元素值小，元素值比基準元素值大* C此時基準元素在排序好的正確位置* D分別對這兩部分記錄，用同樣的方法繼續進行排序，直到整個序列有序。*/public static int[] quickSort(int[] nums, int...is){int low,hight;if(is.length == 0){low = 0;hight = nums.length - 1;}else{low = is[0];hight = is[1];}if(low < hight){//判斷，讓遞歸函數退出，否則無限循環int middle = getMiddle(nums, low, hight);quickSort(nums, 0, middle - 1);//基準元素小quickSort(nums, middle + 1, hight);//比基準元素大}return nums;}//獲取，均值private static int getMiddle(int[] nums, int low, int hight) {int index = nums[low];//選擇基準元素while (low < hight) {//從hight開始，找出比基準小的，與low換位置while (low < hight && nums[hight] >= index) {hight--;}nums[low] = nums[hight];//從low開始找比基準大，放到之前hight空出來的位置上while (low < hight && nums[low] <= index) {low++;}nums[hight] = nums[low];}//此時low = hight是基準元素的位置，也是空缺的位置nums[low] = index;return low;}/** 8、歸并排序* 基本思想：* 歸并排序是，將兩個或兩個以上有序表合并成一個新的有序表。* 即把待排序的序列分為若干個子序列，每個子序列是有序的，然后再把有序序列合并成整體有序序列*/public static int[] mergeSort(int[] nums){sortmerge(nums, 0, nums.length - 1);return nums;}private static void sortmerge(int[] nums, int i, int j) {if(i >= j){return;}//找出中間索引int middle = (i + j)/2;//對左邊數組進行遞歸sortmerge(nums, i, middle);//對右邊數組進行遞歸sortmerge(nums, middle + 1, j);//合并數組merge(nums, i, middle, j);}private static void merge(int[] nums, int i, int middle, int j) {//創建臨時中間量數組int[] tmpArr = new int[nums.length];//右數組第一個元素索引int mid = middle + 1;//記錄臨時數組索引int second = i;//緩存左側數組第一個元素的索引int tmp = i;while (i <= middle && mid <= j) {//從兩個數組中取出最小的放到臨時數組中if(nums[i] <= nums[mid]){tmpArr[second++] = nums[i++];}else{tmpArr[second++] = nums[mid++];}}//剩余部分依次放入臨時數組while (mid <= j) {tmpArr[second++] = nums[mid++];}while (i <= middle) {tmpArr[second++] = nums[i++];}//將臨時數組中內容，拷貝到原數組中while (tmp <= j) {nums[tmp] = tmpArr[tmp++];}}/*9、基數排序（桶）* 將數組中的所有元素按照元素中最長的位數進行統一格式，不足位數的前面補充0* 然后，一次比較每一位的數字，得到最終的比較結果* 基本思想：* A遍歷找出最大的數（確定最大的數是幾）* B開辟臨時數組，用于中間過程的計算* C用一個count數組統計原數組中某一位(從低位向高位統計)相同的數據出現的次數；* D用一個start數組計算原數組中某一位(從最低位向最高位計算)相同數據出現的位置；* E將桶中數據從小到大用臨時數組收集起來；* F重復(3)(4)(5)直到所有位都被統計并計算過，用臨時數組收集起來；* G將臨時數組拷回到原數組中；*/public static int[] radixSort(int[] nums) {int exp; // 指數。當對數組按各位進行排序時，exp=1；按十位進行排序時，exp=10；...int max = getMax(nums); // 數組a中的最大值// 從個位開始，對數組a按"指數"進行排序for (exp = 1; max/exp > 0; exp *= 10) {countSort(nums, exp);}return nums;}//獲取數組中最大的元素private static int getMax(int[] nums) {int i, max;max = nums[0];for (i = 1; i < nums.length; i++)if (nums[i] > max)max = nums[i];return max;}/** 對數組按照"某個位數"進行排序(桶排序)* 參數說明：* exp -- 指數。對數組a按照該指數進行排序。* (01) 當exp=1表示按照"個位"對數組a進行排序* (02) 當exp=10表示按照"十位"對數組a進行排序* (03) 當exp=100表示按照"百位"對數組a進行排序*/private static void countSort(int[] a, int exp) {int[] output = new int[a.length]; // 存儲"被排序數據"的臨時數組int[] buckets = new int[10];// 將數據出現的次數存儲在buckets[]中for (int i = 0; i < a.length; i++)buckets[(a[i] / exp) % 10]++;// 更改buckets[i]。目的是讓更改后的buckets[i]的值，是該數據在output[]中的位置。for (int i = 1; i < 10; i++)buckets[i] += buckets[i - 1];// 將數據存儲到臨時數組output[]中for (int i = a.length - 1; i >= 0; i--) {output[buckets[(a[i] / exp) % 10] - 1] = a[i];buckets[(a[i] / exp) % 10]--;}// 將排序好的數據賦值給a[]for (int i = 0; i < a.length; i++) {a[i] = output[i];}// 用完清空output = null;buckets = null;}public static void main(String[] args) {int[] nums = {1221,232,1242,24,12,4,1,43,14,4,21,4,14,4,1,41,2};//nums = bubbleSort(nums);冒泡//nums = selectSort(nums);選擇//nums = ArraySort(nums);數組//nums = insertSort(nums);插入//nums = shellSrot(nums);希爾//nums = HeapSorts(nums);選擇排序：堆排序//nums = quickSort(nums);快速//nums = mergeSort(nums);歸并nums = radixSort(nums);for (int k = 0; k < nums.length; k++) {System.err.println("排序之后的"+nums[k]);}} }

轉載于:https://blog.51cto.com/13479739/2319073

總結

以上是生活随笔為你收集整理的简单算法之9种排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。