5种java排序算法汇总工具类
程序员文章站
2024-03-13 14:20:18
工具类简单明了地总结了java的快速排序,希尔排序,插入排序,堆排序,归并排序五种排序算法,代码中并没有对这几种排序算法的一个说明,关于思想部分希望在自行查阅相关说明,这里...
工具类简单明了地总结了java的快速排序,希尔排序,插入排序,堆排序,归并排序五种排序算法,代码中并没有对这几种排序算法的一个说明,关于思想部分希望在自行查阅相关说明,这里只是对这几种算法进行一个概括,以供大家使用。
public class sort { public static <anytype extends comparable<? super anytype>> void insertionsort(anytype[] a) { insertionsort(a, 0, a.length - 1); } private static <anytype extends comparable<? super anytype>> void insertionsort(anytype[] a, int left, int right) { int j; // 记录第一个比tmp小的元素的后边一位的位置 for (int p = left; p <= right; p++) { anytype tmp = a[p]; for (j = p; j > left && tmp.compareto(a[j - 1]) < 0; j--) { a[j] = a[j - 1]; } a[j] = tmp; } } public static <anytype extends comparable<? super anytype>> void shellsort(anytype[] arr) { int j; for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; i++) { anytype tmp = arr[i]; for (j = i; j >= gap && tmp.compareto(arr[j - gap]) < 0; j -= gap) { arr[j] = arr[j - gap]; } arr[j] = tmp; } } } private static int leftchild(int i) { return i * 2 + 1; } private static <anytype extends comparable<? super anytype>> void perculatedown(anytype[] arr, int i, int size) { anytype tmp = arr[i]; for (int child; (child = leftchild(i)) < size; i = child) { if (child != size - 1 && arr[child].compareto(arr[child + 1]) < 0) { child++; } if (tmp.compareto(arr[child]) < 0) { arr[i] = arr[child]; } else { break; } } arr[i] = tmp; } public static <anytype extends comparable<? super anytype>> void heapsort(anytype[] arr) { for (int i = arr.length / 2; i >= 0; i--) { perculatedown(arr, i, arr.length); } for (int i = arr.length - 1; i >= 0; i--) { swapreferences(arr, 0, i); perculatedown(arr, 0, i); } } private static <anytype extends comparable<? super anytype>> void swapreferences(anytype[] arr, int i, int j) { anytype tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } public static <anytype extends comparable<? super anytype>> void mergesort(anytype[] arr) { anytype[] tmp = ((anytype[]) new comparable[arr.length]); mergesort(arr, 0, arr.length - 1, tmp); } private static <anytype extends comparable<? super anytype>> void mergesort(anytype[] arr, int start, int end, anytype[] tmp) { if (start < end) { int mid = (start + end) >> 1; mergesort(arr, start, mid, tmp); mergesort(arr, mid + 1, end, tmp); merge(arr, start, mid, end, tmp); } } private static <anytype extends comparable<? super anytype>> void merge(anytype[] arr, int start, int mid, int end, anytype[] tmp) { int i = start, j = mid + 1, k = start; while (i <= mid && j <= end) { if (arr[i].compareto(arr[j]) < 0) { tmp[k++] = arr[i++]; } else { tmp[k++] = arr[j++]; } } while (i <= mid) { tmp[k++] = arr[i++]; } while (j <= end) { tmp[k++] = arr[j++]; } for (int m = start; m <= end; m++) { arr[m] = tmp[m]; } } public static <anytype extends comparable<? super anytype>> void quicksort(anytype[] arr) { quicksort(arr, 0, arr.length - 1); } private static <anytype extends comparable<? super anytype>> void quicksort(anytype[] arr, int left, int right) { if (left + length_diff <= right) { anytype pivot = medium(arr, left, right); int i = left, j = right; while (true) { while (arr[++i].compareto(pivot) < 0); while (arr[--j].compareto(pivot) > 0); if (i < j) { swapreferences(arr, i, j); } else { break; } } swapreferences(arr, i, right); quicksort(arr, left, i - 1); quicksort(arr, i + 1, right); } else { insertionsort(arr, left, right); } } private static <anytype extends comparable<? super anytype>> anytype medium(anytype[] arr, int left, int right) { int center = (left + right) / 2; if (arr[center].compareto(arr[left]) < 0) { swapreferences(arr, center, left); } if (arr[left].compareto(arr[right]) > 0) { swapreferences(arr, left, right); } if (arr[center].compareto(arr[right]) < 0) { swapreferences(arr, center, right); } return arr[right]; } private final static int length_diff = 20; }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。