作為一個數學系的coding菜鳥，還是得多多練習coding，花了一個多小時又手擼了一遍排序，這次把代碼補全關了，果然有點不習慣～

排序算法算是基礎中的基礎，必須得多練。稍微講一下要點吧。

冒泡排序：每一趟將相鄰元素比較，將大的元素往后挪。每一趟可以把最大的元素放到未排序數組的末尾。可以實現成穩定的排序。時間復雜度為N-1+N-2+N-3+...+1 = N(N-1)/2 = O(N^2)。空間復雜度為O(1)

選擇排序：每一趟從未排序的元素中選出最大的，與未排序數組的末尾交換。不穩定的排序。時間復雜度為O(N^2),空間復雜度為O(1)

插入排序：原始的插入排序是將新的元素插入到已經排序好的數組中去，找到排序好的數組中第一個大于當前元素的位置，然后依次交換過去。可以實現為穩定的排序，時間復雜度為O(N^2)，若數組已經有序，則為O(N)，與待排序數組的數據狀況有關。

二分插入排序：原理與插入排序一樣，只不過在查找排序好的數組中第一個大于當前元素的位置時用了二分查找，相比于順序查找效率較高。同樣為穩定的排序。

希爾排序：同樣也是插入排序。因為插入排序的時間復雜度與待排序數組的數據狀況有關，這個時間復雜度主要是在交換元素上。而希爾排序的核心思想就是慢慢使得整個待排序數組有序，這樣每一次插入排序的交換元素耗時就會變小。通過設置一個gap，對每個相鄰gap的元素進行直接插入排序。如果聽不懂，你就這么想，當gap為1的時候就是直接插入排序。gap為2就是對1，3，5，7，9。。。。。位置的元素進行直接插入排序。注意希爾排序是不穩定的，其時間復雜度為O(n^1.3)~O(n^2)

歸并排序：利用了分治的想法。關鍵在于如何Merge，具體不說了，網上有很多的圖解，寫的都很好。時間復雜度O(NlogN),空間復雜度O(N)，可以實現成穩定的排序。

快速排序：同樣利用了分治的思想，關鍵在于Partition函數。時間復雜度為O(NlogN),最壞情況下為O(N^2)在基本排好序的情況下就很差，如果每次分區越均勻則速度越快。所以通常采用隨機快排，隨機選取分割點。是不穩定的排序。

堆排序：不穩定，時間復雜度為O(NlogN)

桶排序計數排序：

桶排序基數排序：

工程中的綜合排序：

對數器：

下次再來填坑了～

import java.util.Arrays;public class Main {public static void main(String[] args) {int[] arr = { 1, 11, 5, 10, 9, 4, 6, 4, 2, 0 };// BubbleSort(arr);// InsertionSort(arr);// BinaryInsertionSort(arr);// ShellSort(arr);// SelectionSort(arr);// MergeSort(arr);// QuickSort(arr);// HeapSort(arr);// BucketSort(arr);RadixSort(arr);for (int i : arr) {System.out.print(i + " ");}System.out.println();int testTime = 500000;int maxSize = 100;int maxValue = 100;boolean succeed = true;for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);// BubbleSort(arr1);// InsertionSort(arr1);// BinaryInsertionSort(arr1);// ShellSort(arr1);// SelectionSort(arr1);// MergeSort(arr1);// QuickSort(arr1);// HeapSort(arr1);// BucketSort(arr1);RadixSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {succeed = false;break;}}System.out.println(succeed ? "Nice!" : "Fucking fucked!");}public static void BubbleSort(int[] arr) {if (arr == null || arr.length < 2) {return;}for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - 1 - i; j++) {if (arr[j + 1] < arr[j]) {swap(arr, j, j + 1);}}}}public static void InsertionSort(int[] arr) {if (arr == null || arr.length < 2) {return;}for (int i = 1; i < arr.length; i++) {for (int j = i - 1; j >= 0; j--) {if (arr[j + 1] < arr[j])swap(arr, j, j + 1);}}}public static void BinaryInsertionSort(int[] arr) {if (arr == null || arr.length < 2)return;for (int i = 1; i < arr.length; i++) {int index = BinarySearch(arr, 0, i - 1, arr[i]);for (int j = i - 1; j >= index; j--)swap(arr, j, j + 1);}}public static int BinarySearch(int[] arr, int l, int r, int target) {int mid = 0;while (l <= r) {mid = l + ((r - l) >> 1);if (arr[mid] <= target)l = mid + 1;elser = mid - 1;}return l;}public static void ShellSort(int[] arr) {if (arr == null || arr.length < 2)return;int gap = arr.length;while (gap > 1) {gap = gap / 3 + 1;for (int i = gap; i < arr.length; i += gap) {for (int j = i - gap; j >= 0; j--) {if (arr[j + gap] < arr[j])swap(arr, j, j + gap);}}}}public static void SelectionSort(int[] arr) {if (arr == null || arr.length < 2)return;for (int i = 0; i < arr.length - 1; i++) {int index = 0;for (int j = 1; j < arr.length - i; j++) {if (arr[j] > arr[index])index = j;}swap(arr, index, arr.length - 1 - i);}}public static void MergeSort(int[] arr) {if (arr == null || arr.length < 2)return;MergeSort(arr, 0, arr.length - 1);}public static void MergeSort(int[] arr, int l, int r) {if (l < r) {int mid = l + ((r - l) >> 1);MergeSort(arr, l, mid);MergeSort(arr, mid + 1, r);Merge(arr, l, mid, r);}}public static void Merge(int[] arr, int l, int mid, int r) {int p1 = l;int p2 = mid + 1;int[] help = new int[r - l + 1];int i = 0;while (p1 <= mid && p2 <= r) {if (arr[p1] <= arr[p2])help[i++] = arr[p1++];elsehelp[i++] = arr[p2++];}while (p1 <= mid)help[i++] = arr[p1++];while (p2 <= r)help[i++] = arr[p2++];for (int j = 0; j < help.length; j++)arr[l + j] = help[j];}public static void QuickSort(int[] arr) {if (arr == null || arr.length < 2)return;QuickSort(arr, 0, arr.length - 1);}public static void QuickSort(int[] arr, int l, int r) {if (l < r) {int[] p = Partition(arr, l, r);QuickSort(arr, l, p[0]);QuickSort(arr, p[1], r);}}public static int[] Partition(int[] arr, int l, int r) {swap(arr, r, l + (int) (Math.random() * (r - l + 1)));int val = arr[r]; // split standard.int p1 = l - 1;int p2 = r;while (l < p2) {if (arr[l] < val)swap(arr, l++, ++p1);else if (arr[l] > val)swap(arr, l, --p2);elsel++;}swap(arr, p2++, r);return new int[] { p1, p2 };}public static void HeapSort(int[] arr) {if (arr == null || arr.length < 2)return;for (int i = 1; i < arr.length; i++)HeapInsert(arr, i);int size = arr.length;while (size > 1) {swap(arr, 0, --size);Heapify(arr, 0, size);}}public static void HeapInsert(int[] arr, int index) {while (index > 0) {if (arr[index] > arr[(index - 1) >> 1]) {swap(arr, index, (index - 1) >> 1);index = (index - 1) >> 1;} elsereturn;}}public static void Heapify(int[] arr, int index, int size) {while ((index << 1) + 1 < size) {int leftchild = (index << 1) + 1;int childlargest = leftchild + 1 < size && arr[leftchild + 1] > arr[leftchild] ? leftchild + 1 : leftchild;int largest = arr[index] >= arr[childlargest] ? index : childlargest;if (largest == index)return;swap(arr, index, largest);index = largest;}}public static void BucketSort(int[] arr) {if (arr == null || arr.length < 2)return;int min = Integer.MAX_VALUE;int max = Integer.MIN_VALUE;for (int i = 0; i < arr.length; i++) {min = arr[i] < min ? arr[i] : min;max = arr[i] > max ? arr[i] : max;}// 針對負數int[] buckets = new int[max - min + 1];for (int i = 0; i < arr.length; i++)arr[i] -= min;for (int i = 0; i < buckets.length; i++)buckets[i] = 0;for (int i = 0; i < arr.length; i++)buckets[arr[i]]++;int j = 0;for (int i = 0; i < buckets.length; i++)while (buckets[i] != 0) {arr[j++] = i;buckets[i]--;}for (int i = 0; i < arr.length; i++)arr[i] += min;}public static void RadixSort(int[] arr) {if (arr == null || arr.length < 2)return;final int radix = 10;RadixSort(arr, radix);}public static void RadixSort(int[] arr, int radix) {int maxbit = getmaxbit(arr, radix);int[] count = new int[radix];int[] buckets = new int[arr.length];for (int bit = 1; bit <= maxbit; bit++) {for (int i = 0; i < count.length; i++)count[i] = 0;for (int i = 0; i < arr.length; i++) {int digit = getdigit(arr[i], bit, radix);count[digit]++;}for (int i = 1; i < count.length; i++)count[i] += count[i - 1];for (int i = arr.length - 1; i >= 0; i--) {int digit = getdigit(arr[i], bit, radix);buckets[--count[digit]] = arr[i];}for (int i = 0; i < buckets.length; i++)arr[i] = buckets[i];}}public static int getmaxbit(int[] arr, int radix) {int max = Integer.MIN_VALUE;for (int i = 0; i < arr.length; i++)max = arr[i] > max ? arr[i] : max;int bit = 0;while (max != 0) {bit++;max /= radix;}return bit;}public static int getdigit(int val, int bit, int radix) {return (int) ((val / (int) Math.pow(radix, bit - 1)) % radix);}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {// arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue *// Math.random());arr[i] = (int) ((maxValue + 1) * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr == null) {return null;}int[] res = new int[arr.length];for (int i = 0; i < arr.length; i++) {res[i] = arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {return false;}if (arr1 == null && arr2 == null) {return true;}if (arr1.length != arr2.length) {return false;}for (int i = 0; i < arr1.length; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr == null) {return;}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();} }

?

總結

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

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