本文實現了八個常用的排序算法：插入排序、冒泡排序、選擇排序、希爾排序、快速排序、歸併排序、堆排序和LST基數排序
首先是EightAlgorithms.java文件，代碼如下：
import java.util.Arrays; /* * 實現了八個常用的排序算法：插入排序、冒泡排序、選擇排序、希爾排序* 以及快速排序、歸併排序、堆排序和LST基數排序* @author gkh178 */ public class EightAlgorithms { //插入排序：時間複雜度o(n^2) public static void insertSort(int a[], int n) { for (int i = 1; i < n; ++i) { int temp = a[i]; int j = i - 1; while (j >= 0 && a[j] > temp) { a[j + 1] =a[j]; --j; } a[j + 1] = temp; } } //冒泡排序：時間複雜度o(n^2) public static void bubbleSort(int a[], int n) { for (int i = n - 1; i > 0; --i) { for (int j = 0; j < i; ++j) { if (a[j] > a[j + 1]) { int temp = a[j]; a[j] = a [j + 1]; a[j + 1] = temp; } } } } //選擇排序：時間複雜度o(n^2) public static void selectSort(int a[], int n) { for (int i = 0; i < n - 1; ++i) { int min = a[i]; int index = i; for (int j = i + 1; j < n; ++j) { if (a[ j] < min) { min = a[j]; index = j; } } a[index] = a[i]; a[i] = min; } } //希爾排序：時間複雜度介於o (n^2)和o(nlgn)之間public static void shellSort(int a[], int n) { for (int gap = n / 2; gap >= 1; gap /= 2) { for (int i = gap; i < n; ++i) { int temp = a[i]; int j = i -gap; while (j >= 0 && a[j] > temp) { a[j + gap] = a [j]; j -= gap; } a[j + gap] = temp; } } } //快速排序：時間複雜度o(nlgn) public static void quickSort(int a[], int n) { _quickSort( a, 0, n-1); } public static void _quickSort(int a[], int left, int right) { if (left < right) { int q = _partition(a, left, right); _quickSort(a, left, q - 1); _quickSort(a, q + 1, right); } } public static int _partition(int a[], int left, int right) { int pivot = a[left]; while (left < right ) { while (left < right && a[right] >= pivot) { --right; } a[left] = a[right]; while (left <right && a[left] <= pivot) { ++left ; } a[right] = a[left]; } a[left] = pivot; return left; } //歸併排序：時間複雜度o(nlgn) public static void mergeSort(int a[], int n) { _mergeSort(a, 0 , n-1); } public static void _mergeSort(int a[], int left, int right) { if (left <right) { int mid = left + (right - left) / 2; _mergeSort (a, left, mid); _mergeSort(a, mid + 1, right); _merge(a, left, mid, right); } } public static void _merge(int a[], int left, int mid, int right ) { int length = right - left + 1; int newA[] = new int[length]; for (int i = 0, j = left; i <= length - 1; ++i, ++j) { newA [i] = a[j]; } int i = 0; int j = mid -left + 1; int k = left; for (; i <= mid - left && j <= length - 1; ++k) { if (newA[i] < newA[j]) { a[k] = newA[i++]; } else { a[k] = newA[j++]; } } while (i <= mid - left) { a [k++] = newA[i++]; } while (j <= right - left) { a[k++] = newA[j++]; } } //堆排序：時間複雜度o(nlgn) public static void heapSort(int a[], int n) { builtMaxHeap(a, n);//建立初始大根堆//交換首尾元素，並對交換後排除尾元素的數組進行一次上調整for (int i = n - 1; i >= 1; --i) { int temp = a[0]; a[0] = a[i]; a[i] = temp; upAdjust(a, i); } } //建立一個長度為n的大根堆public static void builtMaxHeap(int a[], int n) { upAdjust(a, n); } //對長度為n的數組進行一次上調整public static void upAdjust(int a[], int n) { //對每個帶有子女節點的元素遍歷處理，從後到根節點位置for (int i = n / 2; i >= 1; --i) { adjustNode(a, n, i); } } //調整序號為i的節點的值public static void adjustNode(int a[], int n, int i) { //節點有左右孩子if (2 * i + 1 <= n) { //右孩子的值大於節點的值，交換它們if (a[2 * i] > a[i - 1]) { int temp = a[2 * i]; a[2 * i] = a[i - 1]; a[i - 1] = temp; } //左孩子的值大於節點的值，交換它們if (a[2 * i -1] > a[i - 1]) { int temp = a[2 * i - 1]; a[2 * i - 1] = a[i - 1]; a[i - 1] = temp; } //對節點的左右孩子的根節點進行調整adjustNode(a, n, 2 * i); adjustNode(a, n, 2 * i + 1); } //節點只有左孩子，為最後一個有左右孩子的節點else if (2 * i == n) { //左孩子的值大於節點的值，交換它們if (a[2 * i -1] > a[i - 1]) { int temp = a[2 * i - 1]; a[2 * i - 1] = a[i - 1]; a[i - 1] = temp; } } } //基數排序的時間複雜度為o(distance(n+radix)),distance為位數，n為數組個數，radix為基數//本方法是用LST方法進行基數排序，MST方法不包含在內//其中參數radix為基數，一般為10；distance表示待排序的數組的數字最長的位數；n為數組的長度public static void lstRadixSort(int a[], int n, int radix, int distance) { int[] newA = new int[n];//用於暫存數組int[] count = new int[radix];//用於計數排序，保存的是當前位的值為0 到radix-1的元素出現的的個數int divide = 1; //從倒數第一位處理到第一位for (int i = 0; i < distance ; ++i) { System.arraycopy(a, 0, newA, 0, n);//待排數組拷貝到newA數組中Arrays.fill(count, 0);//將計數數組置0 for (int j = 0; j < n; ++j) { int radixKey = (newA[j] / divide) % radix; //得到數組元素的當前處理位的值count[radixKey]++; } //此時count[]中每個元素保存的是radixKey位出現的次數//計算每個radixKey在數組中的結束位置，位置序號範圍為1-n for (int j = 1; j < radix; ++j) { count[j] = count[j] + count[j - 1]; } //運用計數排序的原理實現一次排序，排序後的數組輸出到a[] for (int j = n - 1; j > = 0; --j) { int radixKey = (newA[j] / divide) % radix; a[count[radixKey] - 1] = newA[j]; --count[radixKey]; } divide = divide * radix ; } } }然後測試代碼TestEightAlgorithms.java ，代碼如下：
public class TestEightAlgorithms { public static void printArray(int a[], int n) { for (int i = 0; i < n; ++i) { System.out.print(a[i] + " "); if ( i == n - 1) { System.out.println(); } } } public static void main(String[] args) { for (int i = 1; i <= 8; ++i) { int arr [] = {45, 38, 26, 77, 128, 38, 25, 444, 61, 153, 9999, 1012, 43, 128}; switch(i) { case 1: EightAlgorithms.insertSort(arr, arr.length ); break; case 2: EightAlgorithms.bubbleSort(arr, arr.length); break; case 3: EightAlgorithms.selectSort(arr, arr.length); break; case 4: EightAlgorithms.shellSort(arr, arr.length); break; case 5: EightAlgorithms.quickSort(arr, arr.length); break; case 6: EightAlgorithms.mergeSort(arr, arr.length); break; case 7: EightAlgorithms.heapSort(arr, arr.length); break; case 8: EightAlgorithms.lstRadixSort(arr, arr.length, 10, 4); break; default: break; } printArray(arr, arr.length); } } }最後是運行結果如下：
以上就是Java實現八個常用的排序算法的全部代碼，希望大家對C++排序算法有更進一步的了解。