package baseJava; /** * @title SortMethods.java * @author DonsenChen * @Date 2018年5月2日 上午10:16:03 * @Description */ public class SortMethods { public static void main(String[] args) { int[] arr = { 3, 7, 9, 1, 4, 8, 2, 6, 5 }; binarySort(arr); bubbleSort(arr); quickSort(arr, 0, 0); selectSort(arr); insertSort(arr); shellSort(arr); mergeSort(arr, 0, 0); } // 1. 二分法排序 public static void binarySort(int[] numbers) { int i, j, temp; int low, hight, mid; for (i = 1; i < numbers.length; i++) { temp = numbers[i]; low = 0; hight = i - 1; while (low <= hight) { mid = (low + hight) / 2; if (numbers[mid] > temp) hight = mid - 1; else low = mid + 1; } for (j = i - 1; j > hight; j--) numbers[j + 1] = numbers[j]; numbers[hight + 1] = temp; } System.out.print("二分法排序："); printArr(numbers); System.out.println(); } // 2. 冒泡排序 public static void bubbleSort(int[] numbers) { int temp; // 记录临时中间值 int size = numbers.length; // 数组大小 for (int i = 0; i < size - 1; i++) { for (int j = i + 1; j < size; j++) { if (numbers[i] > numbers[j]) { // 交换两数的位置(ps:这里的大于号小于号决定数组排序的升序或降序) temp = numbers[i]; numbers[i] = numbers[j]; numbers[j] = temp; } } } System.out.print("冒泡排序："); printArr(numbers); System.out.println(); } // 3. 快速排序 public static void quickSort(int[] numbers, int start, int end) { if (start < end) { int base = numbers[start]; // 选定的基准值（第一个数值作为基准值） int temp; // 记录临时中间值 int i = start, j = end; do { while ((numbers[i] < base) && (i < end)) i++; while ((numbers[j] > base) && (j > start)) j--; if (i <= j) { temp = numbers[i]; numbers[i] = numbers[j]; numbers[j] = temp; i++; j--; } } while (i <= j); if (start < j) quickSort(numbers, start, j); if (end > i) quickSort(numbers, i, end); } System.out.print("快速排序："); printArr(numbers); System.out.println(); } // 4. 选择排序 public static void selectSort(int[] numbers) { int size = numbers.length, temp; for (int i = 0; i < size; i++) { int k = i; for (int j = size - 1; j > i; j--) { if (numbers[j] < numbers[k]) k = j; } temp = numbers[i]; numbers[i] = numbers[k]; numbers[k] = temp; } System.out.print("选择排序："); printArr(numbers); System.out.println(); } // 5. 插入排序 public static void insertSort(int[] numbers) { int size = numbers.length, temp, j; for (int i = 1; i < size; i++) { temp = numbers[i]; for (j = i; j > 0 && temp < numbers[j - 1]; j--) numbers[j] = numbers[j - 1]; numbers[j] = temp; } System.out.print("插入排序："); printArr(numbers); System.out.println(); } // 6. 希尔排序 public static void shellSort(int[] numbers) { int n = numbers.length; // 进行分组，最开始的增量(gap)为数组长度的一半 for (int gap = n / 2; gap > 0; gap /= 2) { // 对各个分组进行插入排序 for (int i = gap; i < n; i++) { // 将art[i]插入到所在分组的正确位置上 insertI(numbers, gap, i); } } System.out.print("希尔排序："); printArr(numbers); System.out.println(); } // 希尔排序插入方法 // 将art[i]插入到所在分组的正确位置上 private static void insertI(int[] arr, int gap, int i) { int inserted = arr[i]; int j; for (j = i - gap; j >= 0 && inserted < arr[j]; j -= gap) { arr[j + gap] = arr[j]; } arr[j + gap] = inserted; } // 7. 归并排序 public static void mergeSort(int[] numbers, int left, int right) { int t = 1;// 每组元素个数 int size = right - left + 1; while (t < size) { int s = t;// 本次循环每组元素个数 t = 2 * s; int i = left; while (i + (t - 1) < size) { merge(numbers, i, i + (s - 1), i + (t - 1)); i += t; } if (i + (s - 1) < right) merge(numbers, i, i + (s - 1), right); } System.out.print("归并排序："); printArr(numbers); System.out.println(); } // 归并算法实现 private static void merge(int[] data, int p, int q, int r) { int[] B = new int[data.length]; int s = p; int t = q + 1; int k = p; while (s <= q && t <= r) { if (data[s] <= data[t]) { B[k] = data[s]; s++; } else { B[k] = data[t]; t++; } k++; } if (s == q + 1) B[k++] = data[t++]; else B[k++] = data[s++]; for (int i = p; i <= r; i++) data[i] = B[i]; } // 打印数组 private static void printArr(int[] arr) { System.out.print("["); for (int i = 0; i < arr.length; i++) { if (i == arr.length - 1) { System.out.print(arr[i] + "]"); } else { System.out.print(arr[i] + ", "); } } } }
***********************
心得之谈：欢迎指正，一起学习。
***********************