1.java代码
public class SortUtil { //冒泡排序 public static void bubble(int[] a) { int len = a.length; int flag = len; while (flag > 0) { flag = 0; for (int i = 1; i < len; i++) { if (a[i] < a[i - 1]) { int temp = a[i]; a[i] = a[i - 1]; a[i - 1] = temp; flag = i; } } len = flag; } } //简单选择排序 public static void select(int[] a) { for (int i = 0; i < a.length - 1; i++) { int min = i; for (int j = i + 1; j < a.length; j++) { if (a[j] < a[min]) { min = j; } } if (i != min) { int temp = a[min]; a[min] = a[i]; a[i] = temp; } } } //插入排序 public static void insert(int[] a) { for (int i = 1; i < a.length; i++) { int j = i; int temp = a[i]; while (j > 0 && a[j - 1] > temp) { a[j] = a[j - 1]; j--; } a[j] = temp; } } //快速排序 public static void quick(int[] a, int start, int end) { if (start > end) return; int left = start; int right = end; int partition = a[start]; while (left < right) { while (left < right && a[right] >= partition) { right--; } while (left < right && a[left] <= partition) { left++; } if (left < right) { int temp = a[right]; a[right] = a[left]; a[left] = temp; } } a[start] = a[left]; a[left] = partition; quick(a, start, left - 1); quick(a, right + 1, end); } //希尔排序 public static void shell(int[] arr) { // i表示希尔排序中的第n/2+1个元素（或者n/4+1） // j表示希尔排序中从0到n/2的元素（n/4） // r表示希尔排序中n/2+1或者n/4+1的值 // 划组排序 for (int r = arr.length / 2; r >= 1; r = r / 2) { for (int i = r; i < arr.length; i++) { int tmp = arr[i]; int j = i - r; // 一轮排序 while (j >= 0 && tmp < arr[j]) { arr[j + r] = arr[j]; j -= r; } arr[j + r] = tmp; } } } //构建大根堆 public static void buildMaxHeap(int[] a, int lastIndex) { for (int i = (lastIndex - 1) / 2; i >= 0; i--) { int k = i; int bigIndex = 2 * k + 1; if (bigIndex + 1 <= lastIndex && a[bigIndex] < a[bigIndex + 1]) { bigIndex++; } if (a[k] < a[bigIndex]) { int temp = a[bigIndex]; a[bigIndex] = a[k]; a[k] = temp; } } } //堆排序 public static void heap(int[] a) { for (int i = 0; i < a.length-1; i++) { buildMaxHeap(a, a.length - 1 - i); int temp = a[0]; a[0] = a[a.length - 1 - i]; a[a.length - 1 - i] = temp; } } //合并 public static void merge(int[] a, int start, int mid, int end) { int[] temp = new int[a.length]; int i = start; int j = mid + 1; int k = start; while (i <= mid && j <= end) { if (a[i] <= a[j]) { temp[k++] = a[i++]; } else { temp[k++] = a[j++]; } } while (i <= mid) { temp[k++] = a[i++]; } while (j <= end) { temp[k++] = a[j++]; } for (int n = start; n <= end; n++) { a[n] = temp[n]; } } //归并排序 public static void merge(int[] a, int start, int end) { if (start < end) { int mid = (start + end) / 2; merge(a, start, mid); merge(a, mid + 1, end); merge(a, start, mid, end); } } //基数排序 public static void radix(int[] a) { int disisor = 1; int[][] bucket = new int[10][a.length]; int[] count = new int[10]; int digit; for (int i = 1; i <= 3; i++) { for (int temp : a) { digit = (temp / disisor) % 10; bucket[digit][count[digit]++] = temp; } int k = 0; for (int m = 0; m < 10; m++) { if (count[m] == 0) { continue; } for (int n = 0; n < count[m]; n++) { a[k++] = bucket[m][n]; } count[m] = 0; } disisor *= 10; } } //二分插入排序 public static void advanceInsertSortWithBinarySearch(int[] arr) { for (int i = 1; i < arr.length; i++) { int temp = arr[i]; int low = 0, high = i - 1; int mid = -1; while (low <= high) { mid = low + (high - low) / 2; if (arr[mid] > temp) { high = mid - 1; } else { // 元素相同时，也插入在后面的位置 low = mid + 1; } } for(int j = i - 1; j >= low; j--) { arr[j + 1] = arr[j]; } arr[low] = temp; } } //计数排序 public static void count(int[] a,int maxNum){ int[] b=new int[maxNum+1];//maxNum为数组a中最大的数，+1是因为有0这个数 for (int i=0;i 0){ a[k++]=j; b[j]--; } } }}