提供了以下排序：

冒泡排序

選擇排序

插入排序

希爾排序

快速排序

歸并排序

桶排序

堆排序

?
?

package com.xingej.algorithm.sort;import java.util.ArrayList; import java.util.Collections;/*** 排序工具類* * @author erjun 2017年12月13日 上午8:38:22*/public class SortUtils {// 私有構造器，禁止外界創建對象private SortUtils() {}// --------1、冒泡排序------/*** * 冒泡排序核心：1、從數組的最后一個元素，開始比較；2、兩兩比較，滿足條件的話，就需要進行位置的互換* * 實際生活中：小學時，需要根據身高進行座位排序，就可以使用冒泡排序進行。* */public static void bubbleSort(int[] arr) {int temp;// 4 3 2 1，按冒泡排序的話，需要進行3輪比較可以了for (int i = 0; i < arr.length - 1; i++) {// 每一輪比較，找出本輪的最小值for (int j = arr.length - 1; j > i; j--) {// 后面的/下面的水泡 小于 上面的水泡，就移位if (arr[j] < arr[j - 1]) {// java 是引用傳遞temp = arr[j];arr[j] = arr[j - 1];arr[j - 1] = temp;}}}}// --------2、選擇排序------/*** * 選擇排序的核心:* * 掃描所有的元素，得到最小的元素，并將最小的元素與左邊第一個元素進行交換。再次掃描除* * 第一位置的所有元素，得到最小的元素，與左邊第二個元素進行交換。依次類推* * 選擇排序是建立在冒泡排序的基礎之上的，* * 冒泡排序的缺點，每一輪交換的次數太多了，為了解決這個問題，出現選擇排序* * 解決思路，很明顯，既然冒泡排序每一輪的交換次數太多，那就，每一輪，最多交換依次，就是說，每一輪只將最小值* * 找出來，進行交換，* * 按照這個思路，去寫"選擇排序"* */public static void selectSort(int[] arr) {int minIndex = 0; // 每次兩兩比較時，如a>b，那么minIndex就是b的下標int value;for (int i = 0; i < arr.length - 1; i++) {minIndex = i;value = arr[minIndex]; // 每一輪未排序元素的第一個值// 這個for，每一次，都會找出未排序元素的最小下標for (int j = i + 1; j < arr.length; j++) {if (arr[minIndex] > arr[j]) {minIndex = j;// 將最小下標賦值給minIndex}}// 將最小值與第一個元素，進行交換arr[i] = arr[minIndex];arr[minIndex] = value;}}// --------3、插入排序------/*** 插入排序，的思想跟冒泡排序和選擇排序不同* * 使用場景很像打牌時，每抓到一個張牌，按照大小插入到"已經排序好"的牌里* * 實際應用場景：有排序好的元素，還有一些未排序的元素，這個時候可以考慮插入排序* * 其實，將待排序的元素，插入到已經排序好的元素時，* * 可以使用別的排序方法，來進行，不必循序查詢比較排序，可以使用快速排序* * @param arr*/public static void insertSort(int[] arr) {// right表示，未排序的元素for (int right = 1; right < arr.length; right++) {int temp = arr[right]; // 做備份int left = right - 1;// left 表示： 左邊已經排序好的元素// 比方說，左邊已經排序好的元素有 1 2 4 6// 待排序元素為3，// 將3依次跟6,4,2,1進行比較，直到找到合適的位置，// 也就是，找到合適的數組下標leftwhile (left >= 0 && arr[left] > temp) {arr[left + 1] = arr[left];left--;}// 為什么left+1呢？// 因為，上面的while循環中，left 減 1 之后， 不滿足循環條件的，// 因此，需要將temp值放到left+1的位置上去arr[left + 1] = temp;}}// --------4、希爾排序------public static void shellSort(int[] arr) {int left; // 左邊下標，表示，已經排序好的元素int right; // 右邊下標，表示，待排序元素/就是沒有排序的元素int temp; // 臨時存儲int h = 1; // 初始間隔為1；// 計算最大間隔while (h < arr.length / 3) {h = 3 * h + 1;}while (h > 0) {// 表示循環待排序的元素for (right = h; right < arr.length; right++) {temp = arr[right]; // 先將待排序的元素，進行緩存一下left = right; //// 為什么是left>h-1,// 目前我認為是，保證arr[left-h] 得有值，不能為空，或者說，報空指針異常吧while (left > h - 1 && arr[left - h] >= temp) {arr[left] = arr[left - h];left = left - h;}// 這里，千萬不要寫成下面的形式, 不能再left-h，因為，上面的while()循環，已經減去了// arr[left - h] = temp;arr[left] = temp;}// 重新調整排序間隔h = (h - 1) / 3;}}// --------5、快速排序------public static void quickSort(int arr[]) {recQuickSort(arr, 0, arr.length - 1);}// 使用遞歸和劃分技術進行快速排序private static void recQuickSort(int arr[], int left, int right) {int size = right - left + 1;if (size < 10) {insertSort(arr, left, right);} else {int median = medianof3(arr, left, right);int partition = partitionIt(arr, left, right, median);recQuickSort(arr, left, partition - 1);recQuickSort(arr, partition + 1, right);}}// 劃分方法，返回分割點的索引private static int partitionIt(int arr[], int left, int right, int pivot) {int leftPtr = left;int rightPtr = right - 1;while (true) {// 從左往右找大于特定值的while (arr[++leftPtr] < pivot); // 循環結束，就代表，找到一個大于特定值的數據項// 從右向左找小于特定值while (arr[--rightPtr] > pivot);if (leftPtr >= rightPtr) {break; // 結束時，leftPtr = rightPtr} else {swap(arr, leftPtr, rightPtr); // 交換}}swap(arr, leftPtr, right - 1);return leftPtr;}// 找出中間值// 索引為left，right，以及中間值的 進行排序，private static int medianof3(int arr[], int left, int right) {int centerIndex = (left + right) / 2;if (arr[left] > arr[centerIndex]) {swap(arr, left, centerIndex);}if (arr[left] > arr[right]) {swap(arr, left, right);}if (arr[centerIndex] > arr[right]) {swap(arr, centerIndex, right);}swap(arr, centerIndex, right - 1);return arr[right - 1];}private static void insertSort(int arr[], int left, int right) {int in, out;int temp; // 臨時緩存，待存儲的元素for (out = left + 1; out <= right; out++) {temp = arr[out];in = out;while (in > left && arr[in - 1] >= temp) {arr[in] = arr[in - 1];in--;}arr[in] = temp;}}private static void swap(int arr[], int left, int right) {int temp = arr[left];arr[left] = arr[right];arr[right] = temp;}// --------6、歸并排序------// 歸并兩個已經有序的數組// 首先將數組，拆分成兩部分，左邊做成有序的，同樣，右邊也做成有序的。// 將這兩個有序的數組，組合生成第3個有序的數組，// 時間復雜度O(N*logN)// 缺點：消耗內存；public static void mergeSort(int arr[]) {// 生成臨時的緩存數組，用于臨時排序int[] workSpace = new int[arr.length];recMergeSort(arr, workSpace, 0, arr.length - 1);}// lowerBound，upperBound 全是數組下標private static void recMergeSort(int arr[], int workSpace[], int lowerBound, int upperBound) {if (lowerBound == upperBound) {return;} else {int mid = (lowerBound + upperBound) / 2;// 遞歸前半部分recMergeSort(arr, workSpace, lowerBound, mid);// 遞歸后半部分recMergeSort(arr, workSpace, mid + 1, upperBound);// 進行合并merge(arr, workSpace, lowerBound, mid + 1, upperBound);}}/*** * @param arr* 被排序的數組* @param workSpace* 臨時緩存，進行排序的* @param lowPtr* 前半部分，最小下標* @param highPtr* 后半部分，最小下標* @param upperBound* 后半部分，最大下標*/private static void merge(int arr[], int workSpace[], int lowPtr, int highPtr, int upperBound) {int i = 0;int lowerBound = lowPtr;// 前半部分的最小下標，進行緩存int mid = highPtr - 1;int n = upperBound - lowerBound + 1;while (lowPtr <= mid && highPtr <= upperBound) {if (arr[lowPtr] < arr[highPtr]) {workSpace[i++] = arr[lowPtr++];} else {workSpace[i++] = arr[highPtr++];}}// 前半部分或者后半部分，可能還存在未排序的元素，需要寫到workSpace里while (lowPtr <= mid) {workSpace[i++] = arr[lowPtr++];}while (highPtr <= upperBound) {workSpace[i++] = arr[highPtr++];}// 將排序好的元素數組workSpace，重新賦值到arr數組里for (i = 0; i < n; i++) {arr[lowerBound + i] = workSpace[i];}}// --------7、桶排序------/*** 使用場景：* * 1、桶排序，可使用于最大最小值相差較大的數據情況，如{2,100,200,198,3,87}* * 2、被排序的數據元素，最好分配均勻，否則可能會導致數據都集中到一個桶中，如{102,108,111,204,3000}* * 基本步驟：* * 1.找出待排序數組中的最大值max、最小值min* * 2.我們使用 動態數組ArrayList 作為桶，桶里放的元素也用 ArrayList存儲。桶的數量為(max-min)/arr.length+1* * 3.遍歷數組 arr，計算每個元素 arr[i] 放的桶* * 4.每個桶各自排序* * 5.遍歷桶數組，把排序好的元素放進輸出數組* */public static void bucketSort(int arr[]) {int max = Integer.MIN_VALUE; // 先賦值成最小值int min = Integer.MAX_VALUE;// 一次循環，將該數組的最大值，最小值求出來for (int i = 0; i < arr.length; i++) {max = Math.max(max, arr[i]);min = Math.min(min, arr[i]);}// 求桶數int bucketNum = (max - min) / (arr.length) + 1;// 初始化每個桶ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>();for (int i = 0; i < bucketNum; i++) {bucketArr.add(new ArrayList<>());}// 遍歷數組，將每個元素放入桶中for (int i = 0; i < arr.length; i++) {int bucketIndex = (arr[i] - min) / (arr.length);bucketArr.get(bucketIndex).add(arr[i]);}// 對每個桶元素，進行排序for (int i = 0; i < bucketArr.size(); i++) {Collections.sort(bucketArr.get(i));}// 將已經排序好的元素，重新賦值到arr數組里int j = 0;// 遍歷每個桶，將每個桶的元素，賦值到arr數組里for (int i = 0; i < bucketArr.size(); i++) {ArrayList<Integer> arrayList = bucketArr.get(i);for (Integer key : arrayList) {arr[j++] = key;}}}// --------8、堆排序------// 堆特點：// 1、它是完全的二叉樹，除了樹的最后一層節點不需要是滿的，其他的每一層從左到右都完全是滿的// 2、它常常是用一個數組來實現堆的// 3、堆中的每一個節點都滿足的條件是，父節點的關鍵字要大于所有的子節點public static void heapSort(int arr[]) {int size = arr.length;Heap heap = new Heap(size);for (int i = 0; i < size; i++) {Node node = new Node(arr[i]);heap.insertAt(i, node);heap.incrementSize();// 數量遞增}// 從最后一個元素的父節點開始向下調整，一直到根// 調整完后，就變成標準的堆了for (int j = size / 2 - 1; j >= 0; j--) {heap.trickleDown(j);}// 通過循環刪除最大項，再把刪除的數據，數組中的指定的位置，如從后往前方；// 結果就是從小到大排序for (int j = size - 1; j >= 0; j--) {Node biggestNode = heap.remove();// 取出最大的數據項heap.insertAt(j, biggestNode);}System.out.println("----打印排序后的堆----");heap.displayArray();}// 堆排序，// 堆是二叉樹，因此，需要創建這個節點，來存儲數據// 堆的特點：父節點的值要大于子節點，左右子節點大小無關系，不要求左子節點小于右子節點static class Node {private int iData;public Node(int key) {iData = key;}public int getKey() {return iData;}public void setKey(int id) {iData = id;}}// 創建堆static class Heap {private Node[] heapArray;private int maxSize;private int currentSize;public Heap(int mx) {maxSize = mx;currentSize = 0;heapArray = new Node[maxSize];}public boolean isEmpty() {return currentSize == 0;}// 插入指定的位置public void insertAt(int index, Node node) {heapArray[index] = node;}public void incrementSize() {currentSize++;}public Node remove() {Node root = heapArray[0];heapArray[0] = heapArray[--currentSize];// 把最后一個元素，賦值到根元素上trickleDown(0);// 開始向下調整return root;}// 向下調整public void trickleDown(int index) {int largerChild;Node top = heapArray[index];while (index < currentSize / 2) {int leftChild = 2 * index + 1;int rightChild = leftChild + 1;if (rightChild < currentSize && heapArray[leftChild].getKey() < heapArray[rightChild].getKey()) {largerChild = rightChild;} else {largerChild = leftChild;}if (top.getKey() >= heapArray[largerChild].getKey()) {break;}heapArray[index] = heapArray[largerChild];index = largerChild;}heapArray[index] = top;}// 樹狀的方式，顯示堆public void displayHeap() {int nBlanks = 32;int itemsPerRow = 1;// 層數判斷int column = 0;int j = 0;String dots = "-------------------------";System.out.println(dots + dots);while (currentSize > 0) {if (column == 0) {for (int k = 0; k < nBlanks; k++) {System.out.print(' ');}System.out.print(heapArray[j].getKey());if (++j == currentSize) {break;// 所有的數據項，全部顯示完畢了}if (++column == itemsPerRow) {nBlanks /= 2;itemsPerRow *= 2;column = 0;System.out.println();} else {for (int k = 0; k < nBlanks * 2 - 2; k++) {System.out.print(' ');}}}}System.out.println("\n" + dots + dots);}// 以數組的方式，來顯示堆public void displayArray() {for (int j = 0; j < maxSize; j++) {System.out.print(heapArray[j].getKey() + " ");}System.out.println();}} }

?
?
?
?
?
測試用例：

package com.xingej.algorithm.sort;import org.junit.Before; import org.junit.Test;public class SortTest {private int max = 20;private int[] arr = new int[max];// 初始化數組@Beforepublic void initArray() {for (int i = 0; i < max; i++) {arr[i] = (int) (Math.random() * 100 + 1);}System.out.println("------排序前-----");show(arr);}// -----打印輸出/*** 打印輸出數組* * @param arr*/private void show(int[] arr) {for (int i = 0; i < max; i++) {System.out.print(arr[i] + " ");}System.out.println();}// -----冒泡排序@Testpublic void testByBubbleSort() {SortUtils.bubbleSort(arr);System.out.println("------排序后-----");show(arr);}// -----選擇排序@Testpublic void testBySelectionSort() {SortUtils.selectSort(arr);System.out.println("------排序后-----");show(arr);}// -----插入排序@Testpublic void testByInsertSort() {SortUtils.insertSort(arr);System.out.println("------排序后-----");show(arr);}// -----希爾排序@Testpublic void testByShellSort() {SortUtils.shellSort(arr);System.out.println("------排序后-----");show(arr);}// -----快速排序@Testpublic void testByQuickSort() {SortUtils.quickSort(arr);System.out.println("------排序后-----");show(arr);}// -----歸并排序@Testpublic void testByMergeSort() {SortUtils.mergeSort(arr);System.out.println("------排序后-----");show(arr);}// -----桶排序@Testpublic void testByBucketSort() {SortUtils.bucketSort(arr);System.out.println("------排序后-----");show(arr);}// -----堆排序,時間復雜度是O(logN)@Testpublic void testByHeapSort() {SortUtils.heapSort(arr);}}

代碼已經上傳到了git上
https://github.com/xej520/xingej-algorithm

?
?

本文轉自故新51CTO博客，原文鏈接：?http://blog.51cto.com/xingej/2056881，如需轉載請自行聯系原作者

總結

以上是生活随笔為你收集整理的JAVA 排序工具类的全部內容，希望文章能夠幫你解決所遇到的問題。

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