迈向高级的Java面试突围课|资源分享
download:迈向高级的Java面试突围课
public class Sort {
public static > void insertionSort(AnyType[] a) {
insertionSort(a, 0, a.length - 1);
}
private static > 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 > 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 > 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 > 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 > void swapReferences(AnyType[] arr, int i, int j) {
AnyType tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static > void mergeSort(AnyType[] arr) {
AnyType[] tmp = ((AnyType[]) new Comparable[arr.length]);
mergeSort(arr, 0, arr.length - 1, tmp);
}
private static > 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 > 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 > void quickSort(AnyType[] arr) {
quickSort(arr, 0, arr.length - 1);
}
【迈向高级的Java面试突围课|资源分享】private static > 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;
}
}
推荐阅读
- JAVA(抽象类与接口的区别&重载与重写&内存泄漏)
- 事件代理
- Java|Java OpenCV图像处理之SIFT角点检测详解
- java中如何实现重建二叉树
- 数组常用方法一
- 【Hadoop踩雷】Mac下安装Hadoop3以及Java版本问题
- Java|Java基础——数组
- RxJava|RxJava 在Android项目中的使用(一)
- java之static、static|java之static、static final、final的区别与应用
- Java基础-高级特性-枚举实现状态机