package 排序算法; /** * 1.選擇排序 * 2.插入排序 * 3.歸并排序 * 4.快速排序 * * @author Administrator * */ public class 4種排序算法 { public static void main(String[] args) { int[] arr = { 2, 5, 6, 7, 4, 3, 1, 1, 3, 4, 5, 1, 3, 6, 3 }; // selectSort(arr); // insertedSort(arr); // mergeSort(arr, 0, arr.length - 1); quickSort(arr, 0, arr.length - 1); out(arr); } // 輸出 public static void out(int[] arr) { for (int e : arr) System.out.print(e + ","); } // 1.選擇排序 public static void selectSort(int[] a) { for (int i = 0; i < a.length; i++) for (int j = i + 1; j < a.length; j++) { int key = a[i]; if (key > a[j]) { a[i] = a[j]; a[j] = key; } } } // 2.插入排序 public static void insertedSort(int[] a) { for (int i = 1; i < a.length; i++) { int key = a[i]; int j = i - 1; while (j >= 0 && key < a[j]) { a[j + 1] = a[j]; a[j] = key; j--; } } } // 3.歸并排序(分治法) public static void mergeSort(int[] a, int low, int high) { if (low < high) { int mid = (low + high) / 2; // 遞歸到最小原子 mergeSort(a, low, mid); mergeSort(a, mid + 1, high); // 合并數組 mergeArray(a, low, mid, high); } } // 合并數組 private static void mergeArray(int[] a, int low, int mid, int high) { int N = high - low; int[] temp = new int[N + 1]; int i = low, j = mid + 1; int m = mid, n = high; int k = 0; while (i <= m && j <= n) temp[k++] = (a[i] < a[j] ? a[i++] : a[j++]); while (i <= m) temp[k++] = a[i++]; while (j <= n) temp[k++] = a[j++]; for (i = 0; i < k; i++) a[low + i] = temp[i]; } // 4.快速排序(分治法) public static void quickSort(int[] a, int low, int high) { if (low < high) { int r = adjustArray(a, low, high); quickSort(a, low, r - 1); quickSort(a, r + 1, high); } } // 提取數組中的首個元素，分割。小的元素放在<strong>標志</strong>的左側，比 // 標志大的元素放在其右側，最后返回標志元素的位置 private static int adjustArray(int[] a, int low, int high) { int i = low, j = high; int spcValue = a[low]; while (i < j) { while (a[j] >= spcValue && i < j) j--; if (a[j] < spcValue) a[i++] = a[j]; while (a[i] <= spcValue && i < j) i++; if (a[i] > spcValue) a[j--] = a[i]; } a[i] = spcValue; return i; } }