文章目录
排序工具
1 生成随机数
/**
* 生成一个随机数数
*
* @param n 数组中的元素数量
* @param rangeL 左区间
* @param rangeR 右区间
* @return
*/
public static Integer[] generateRandomArray(int n, int rangeL, int rangeR) {
if (rangeL >= rangeR) {
return null;
}
Integer arr[] = new Integer[n];
for (int i = 0; i < n; i++) {
int random = (int) (Math.random() * (rangeR - rangeL + 1) + rangeL);
arr[i] = random;
}
return arr;
}
2 计算耗时
public static void testSortSpendTime(ISort iSort, Comparable[] arr) {
long startTime = System.currentTimeMillis();
if (iSort != null) {
iSort.sort();
}
long endTime = System.currentTimeMillis();
long spendTime = endTime - startTime;
System.out.println("算法消耗的时间为： " + spendTime + "ms");
}
public interface ISort {
void sort();
}
3 近乎有序随机数
public static Integer[] generateNearlyOrderArray(int n, int swapTimes) {
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++) {
arr[i] = new Integer(i);
}
for (int i = 0; i < swapTimes; i++) {
int indexA = (int) (Math.random() * n);
int indexB = (int) (Math.random() * n);
int t = arr[indexA];
arr[indexA] = arr[indexB];
arr[indexB] = t;
}
return arr;
}
4 检测数组是否有序
/**
* 检查数组是否是正序
*
* @param arr
* @return
*/
public static boolean isSorted(Comparable[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i].compareTo(arr[i + 1]) < 0) {
return false;
}
}
return true;
}
1 选择排序
private static void selectSort(Comparable[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if ((arr[j].compareTo(arr[minIndex])) < 0) {
minIndex = j;
}
}
swap(arr, minIndex, i);
}
}
private static void swap(Comparable[] arr, int i, int j) {
Comparable t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
2 插入排序
private static void insertSort(Comparable[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
Comparable e = arr[i];
int j = i;
for (; j > 0; j--) {
if (arr[j - 1].compareTo(e) > 0) {
arr[j] = arr[j - 1];
} else {
break;
}
}
arr[j] = e;
}
}
3 希尔排序
public static void shellSort(Comparable[] arr) {
int n = arr.length;
int h = 1;
//1 计算增量的值
while (h < n / 3) {
h = 3 * h + 1;
}
//2 增量h递减
while (h >= 1) {
//3 对增量为h的数组进行插入排序
for (int i = h; i < n; i++) {
Comparable element = arr[i];
int j = i;
for (; j >= h; j -= h) {
if (element.compareTo(arr[j - h]) < 0) {
arr[j] = arr[j - h];
} else {
break;
}
}
arr[j] = element;
}
h /= 3;
}
}
4 归并排序
public static void merge(Comparable[] arr, int left, int right) {
int middle = (left + right) / 2;
Comparable[] cpArray = Arrays.copyOfRange(arr, left, right + 1);
int leftIndex = left;
int rightIndex = middle + 1;
for (int k = left; k <= right; k++) {
//1 左边的已经排好序
if (leftIndex > middle) {
arr[k] = cpArray[rightIndex - left];
rightIndex++;
//2 右边的已经排好序
} else if (rightIndex > right) {
arr[k] = cpArray[leftIndex - left];
leftIndex++;
//3 左边小于右边
} else if (cpArray[leftIndex - left].compareTo(cpArray[rightIndex - left]) < 0) {
arr[k] = cpArray[leftIndex - left];
leftIndex++;
//4 右边小于左边
} else {
arr[k] = cpArray[rightIndex - left];
rightIndex++;
}
}
}
private static void mergeSort(Comparable[] arr, int left, int right) {
if (left >= right) {
return;
}
int middle = (left + right) / 2;
mergeSort(arr, left, middle);
mergeSort(arr, middle + 1, right);
merge(arr, left, right);
}
5 快速排序
private static int partition(Comparable[] arr, int left, int right) {
Comparable v = arr[left];
int j = left;
for (int i = left + 1; i <= right; i++) {
if (v.compareTo(arr[i]) > 0) {
j++;
SortTestUtils.swap(arr, j, i);
}
}
SortTestUtils.swap(arr, j, left);
return j;
}
private static void sort(Comparable[] arr, int left, int right) {
if (left >= right) {
return;
}
int p = partition(arr, left, right);
sort(arr, left, p - 1);
sort(arr, p + 1, right);
}
6 双路快排
避免重复键值导致效率低问题
private static int partition_2(Comparable[] arr, int left, int right) {
int randomIndex = (int) (Math.random() * (right - left + 1) + left);
SortTestUtils.swap(arr, left, randomIndex);
Comparable v = arr[left];
int i = left + 1, j = right;
while (true) {
//1 找到第一个比v大的index
while (i <= right && arr[i].compareTo(v) < 0) {
i++;
}
//2 找到后面往前第一个比v小的index
while (j >= left + 1 && arr[j].compareTo(v) > 0) {
j--;
}
//3 表示left到right之前的index已经遍历结束
if (i > j) {
break;
}
//4 交换i和j的值，此时i的值时比v大，j的值比v小
SortTestUtils.swap(arr, i, j);
//5 index分别向后和向前挪一位
i++;
j--;
}
SortTestUtils.swap(arr, left, j);
return j;
}
7 三路快排
private static void quickSort_3(Comparable[] arr, int left, int right) {
if(left >= right){
return;
}
int randomIndex = (int) (Math.random() * (right - left + 1) + left);
SortTestUtils.swap(arr, left, randomIndex);
Comparable v = arr[left];
int leftIndex = left;
int rightIndex = right + 1;
int i = left + 1;
while (i < rightIndex) {
if (arr[i].compareTo(v) < 0) {
SortTestUtils.swap(arr, i, leftIndex + 1);
i++;
leftIndex++;
} else if (arr[i].compareTo(v) > 0) {
SortTestUtils.swap(arr, i, rightIndex - 1);
rightIndex--;
} else {
i++;
}
}
SortTestUtils.swap(arr, left, leftIndex);
quickSort_3(arr, left, leftIndex - 1);
quickSort_3(arr, rightIndex, right);
}
8 堆排序
public static void sort(Comparable[] arr) {
int n = arr.length;
for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
shiftDown(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
shiftDown(arr, i, 0);
}
}
private static void shiftDown(Comparable[] arr, int n, int k) {
Comparable e = arr[k];
while (2 * k + 1 < n) {
int j = 2 * k + 1;
if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0) {
j += 1;
}
if (e.compareTo(arr[j]) >= 0) {
break;
}
swap(arr, k, j);
k = j;
}
}