import java.util.Arrays;
import java.util.Random;
public class Sort {
public static void main(String[] args) {
test();
// sort();
}
private static void sort() {
int[] nums = createArr(20, 200);
print(nums);
gnomeSort1(nums);
print(nums);
}
private static void test() {
long time1, time2;
int[] ints;
int length = 100000; //生成的数组长度
int[] nums = createArr(length, Integer.MAX_VALUE);
System.out.println(length + "长度数组排序测试");
ints = Arrays.copyOf(nums, length);
time1 = System.currentTimeMillis();
selectionSort(ints);
time2 = System.currentTimeMillis();
System.out.println("选择排序耗时：" + (time2 - time1) + "ms");
ints = Arrays.copyOf(nums, length);
time1 = System.currentTimeMillis();
bubbleSort(ints);
time2 = System.currentTimeMillis();
System.out.println("冒泡排序耗时：" + (time2 - time1) + "ms");
ints = Arrays.copyOf(nums, length);
time1 = System.currentTimeMillis();
cockSort(ints);
time2 = System.currentTimeMillis();
System.out.println("鸡尾酒排序耗时：" + (time2 - time1) + "ms");
ints = Arrays.copyOf(nums, length);
time1 = System.currentTimeMillis();
insertSort(ints);
time2 = System.currentTimeMillis();
System.out.println("插入排序耗时：" + (time2 - time1) + "ms");
ints = Arrays.copyOf(nums, length);
time1 = System.currentTimeMillis();
shellSort(ints);
time2 = System.currentTimeMillis();
System.out.println("希尔排序耗时：" + (time2 - time1) + "ms");
ints = Arrays.copyOf(nums, length);
time1 = System.currentTimeMillis();
heapSort(ints);
time2 = System.currentTimeMillis();
System.out.println("堆排序耗时：" + (time2 - time1) + "ms");
ints = Arrays.copyOf(nums, length);
time1 = System.currentTimeMillis();
quickSort(ints, 0, ints.length - 1);
time2 = System.currentTimeMillis();
System.out.println("快速排序耗时：" + (time2 - time1) + "ms");
ints = Arrays.copyOf(nums, length);
time1 = System.currentTimeMillis();
quickSort(ints, 0, ints.length - 1);
time2 = System.currentTimeMillis();
System.out.println("双轴快速排序耗时：" + (time2 - time1) + "ms");
ints = Arrays.copyOf(nums, length);
time1 = System.currentTimeMillis();
mergeSort(ints, 0, ints.length - 1);
time2 = System.currentTimeMillis();
System.out.println("归并排序耗时：" + (time2 - time1) + "ms");
ints = Arrays.copyOf(nums, length);
time1 = System.currentTimeMillis();
gnomeSort(ints);
time2 = System.currentTimeMillis();
System.out.println("地精排序耗时：" + (time2 - time1) + "ms");
ints = Arrays.copyOf(nums, length);
time1 = System.currentTimeMillis();
gnomeSort1(ints);
time2 = System.currentTimeMillis();
System.out.println("地精排序优化版耗时：" + (time2 - time1) + "ms");
ints = Arrays.copyOf(nums, length);
time1 = System.currentTimeMillis();
Arrays.sort(ints);
time2 = System.currentTimeMillis();
System.out.println("系统排序耗时：" + (time2 - time1) + "ms");
ints = Arrays.copyOf(nums, length);
time1 = System.currentTimeMillis();
stoogeSort(ints, 0, ints.length - 1);
time2 = System.currentTimeMillis();
System.out.println("神经病排序耗时：" + (time2 - time1) + "ms");
}
//打印数组
private static void print(int[] arr) {
System.out.println(Arrays.toString(arr));
}
//生成随机数组
public static int[] createArr(int length, int bounds) {
int[] arr = new int[length];
Random random = new Random();
for (int i = 0; i < length; i++) {
arr[i] = random.nextInt(bounds);
}
return arr;
}
//交换数组索引ij的数值
private static void swap(int[] arr, int i, int j) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
//选择排序
public static void selectionSort(int[] arr) {
int min;
for (int i = 0; i < arr.length - 1; i++) {
min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
swap(arr, i, min);
}
}
//冒泡排序
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
//鸡尾酒冒泡
public static void cockSort(int[] arr) {
int min = 0, max = arr.length - 1;
int index = 0;
while (min < max) {
for (int i = min; i < max; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
index = i;
}
}
max = index;
for (int i = max; i > min; i--) {
if (arr[i] < arr[i - 1]) {
swap(arr, i, i - 1);
index = i;
}
}
min = index;
}
}
//插入排序
public static void insertSort(int[] arr) {
int num, j;
for (int i = 1; i < arr.length; i++) {
num = arr[i];
j = i - 1;
while (j >= 0 && num < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = num;
}
}
//希尔排序
public static void shellSort(int[] arr) {
int num, j, gap = arr.length / 2;
while (gap >= 1) {
for (int i = gap; i < arr.length; i++) {
num = arr[i];
j = i - gap;
while (j >= 0 && num < arr[j]) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = num;
}
gap >>>= 1;
}
}
//神经病排序
public static void stoogeSort(int[] arr, int i, int j) {
int temp;
if (arr[j] < arr[i]) {
swap(arr, i, j);
}
if (j - i + 1 > 2) {
temp = (j - i + 1) / 3;
stoogeSort(arr, i, j - temp);
stoogeSort(arr, i + temp, j);
stoogeSort(arr, i, j - temp);
}
}
//快速排序
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) return;
int i = left, j = right, temp = arr[left];
while (i < j) {
while (i < j && arr[j] >= temp) {
j--;
}
while (i < j && arr[i] <= temp) {
i++;
}
if (i < j) {
swap(arr, i, j);
}
}
arr[left] = arr[i];
arr[i] = temp;
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
//双轴快排
public static void QuickSortDualPivot(int[] A, int L, int R) {
if (L >= R) {
return;
}
if (A[L] > A[R]) {
swap(A, L, R); //保证pivot1 <= pivot2
}
int pivot1 = A[L];
int pivot2 = A[R];
int i = L + 1;
int k = L + 1;
int j = R - 1;
OUT_LOOP:
while (k <= j) {
if (A[k] < pivot1) {
swap(A, i, k);
k++;
i++;
} else if (A[k] >= pivot1 && A[k] <= pivot2) {
k++;
} else {
while (A[j] > pivot2) {
j--;
if (j < k) {//当k和j错过
break OUT_LOOP;
}
}
if (A[j] >= pivot1 && A[j] <= pivot2) {
swap(A, k, j);
k++;
j--;
} else {//A[j] < pivot1
swap(A, j, k);//注意k不动
j--;
}
}
}
i--;
j++;
swap(A, L, i);//将pivot1交换到适当位置
swap(A, R, j);//将pivot2交换到适当位置
//一次双轴切分至少确定两个元素的位置，这两个元素将整个数组区间分成三份
QuickSortDualPivot(A, L, i - 1);
QuickSortDualPivot(A, i + 1, j - 1);
QuickSortDualPivot(A, j + 1, R);
}
//归并排序
public static void mergeSort(int[] arr, int start, int end) {
if (start >= end) return;
int middle = (start + end) / 2;
mergeSort(arr, start, middle);
mergeSort(arr, middle + 1, end);
merge(arr, start, middle, end);
}
private static void merge(int[] array, int start, int middle, int end) {
int[] aux = new int[end - start + 1];
System.arraycopy(array, start, aux, 0, end - start + 1);
int left = start;
int right = middle + 1;
for (int k = start; k <= end; k++) {
if (left > middle) {
array[k] = aux[right - start];
right++;
} else if (right > end) {
array[k] = aux[left - start];
left++;
} else if (aux[left - start] > aux[right - start]) {
array[k] = aux[right - start];
right++;
} else {
array[k] = aux[left - start];
left++;
}
}
}
//堆排序
public static void heapSort(int[] arr) {
int len = arr.length - 1;
//生成大顶堆
for (int parent = len / 2 - 1; parent >= 0; parent--) {
heapAdjust(arr, parent, len);
}
//每次截取大顶堆的根结点，排在数组最后，然后调整剩下的堆使其保持大顶堆
while (len >= 0) {
swap(arr, 0, len--);
heapAdjust(arr, 0, len);
}
}
//从parent节点开始调整堆保持parent它的子节点为大顶堆
private static void heapAdjust(int[] arr, int parent, int len) {
int leftChild, rightChild, maxChild;
while ((leftChild = parent * 2 + 1) <= len) {
rightChild = leftChild + 1;
maxChild = leftChild;
if (maxChild < len && (arr[leftChild] < arr[rightChild])) {
maxChild++;
}
if (arr[parent] < arr[maxChild]) {
swap(arr, parent, maxChild);
parent = maxChild;
} else {
break;
}
}
}
//地精排序
public static void gnomeSort(int[] arr) {
for (int i = 0; i < arr.length; ) {
if (i == 0 || arr[i - 1] <= arr[i]) i++;
else swap(arr, i, --i);
}
}
//地精排序优化版1
public static void gnomeSort1(int[] arr) {
for (int i = 0, p = 0; i < arr.length; ) {
if (i == 0 || arr[i - 1] <= arr[i]) i = ++p;
else swap(arr, i, --i);
}
}
}
网友评论