给出1000个通过随机生成的数据,分别用简单选择排序,希尔排序法,堆排序法进行排序

Question

给出1000个通过随机生成的数据,分别用简单选择排序,希尔排序法,堆排序法进行排序急，求大神解答

Answer 1

//这是我目前所知道的所有排序了整合了一下:我测试用的是20个数字,你把数量改成1000即可!
import java.util.Scanner;
public class TestSort {
private static Scanner sc=new Scanner(System.in);
private static HeapSort myHs=new HeapSort();
public static void main(String[] args) {
int[] arr = new int[20];//数量!
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 10 + 1);
}
sop("原始顺序:\n");
for (int a : arr)
sop(a + ",");
sop("\n\n----------------请选择需要使用的方法----------------\n");
sop("\n-----1:冒泡;2:选择;3:插排;4:快排;5:希尔;6:堆排------\n");
int tem=sc.nextInt();
window(arr,tem);
sop("\n排序后:\n");
for (int a : arr)
sop(a + ",");
}// 菜单!
private static void window(int arr[], int a) {
switch(a) {
case 1:myBubble(arr);
break;
case 2:mySelect(arr);
break;
case 3:myInsert(arr);
break;
case 4:quicksort(arr);
break;
case 5:myshell(arr);
break;
default :
myHs.buildMaxHeapify(arr);
myHs.heapSort(arr);
break;
}
}
// 冒泡!
private static void myBubble(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])
swp(arr, j, j + 1);
}// 选择!
private static void mySelect(int[] arr) {
for (int i = 0; i < arr.length - 1; i++)
for (int j = i + 1; j < arr.length; j++)
if (arr[i] > arr[j])
swp(arr, i, j);
}// 插排!
private static void myInsert(int[] arr) {
for (int i = 1; i < arr.length; i++)
for (int j = i; j > 0; j--)
if (arr[j] < arr[j - 1])
swp(arr, j, j - 1);
}// 快排!
public static void quicksort(int[] arr) {
int start = 0;
int end = arr.length - 1;
quickSort(arr, start, end);
}
public static void quickSort(int[] arr, int start, int end) {
if (start < end) {
int base = arr[start]; //
int i = start, j = end;
do {
while ((arr[i] < base) && (i < end))
i++;
while ((arr[j] > base) && (j > start))
j--;
if (i <= j) {
swp(arr, i, j);
i++;
j--;
}
} while (i <= j);
if (start < j)
quickSort(arr, start, j);
if (end > i)
quickSort(arr, i, end);
}
}// 希尔
private static void myshell(int[] arr) {
int i, j, gap, n;
n = arr.length;
for (gap = n / 2; gap > 0; gap /= 2)
for (i = gap; i < n; i++)
for (j = i - gap; j >= 0 && arr[j] > arr[j + gap]; j -= gap) {
int tem = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = tem;
}
}// 堆!
private static class HeapSort {
void buildMaxHeapify(int[] data) {
int startIndex = getParentIndex(data.length - 1);
for (int i = startIndex; i >= 0; i--) {
maxHeapify(data, data.length, i);
}
}
void maxHeapify(int[] data, int heapSize, int index) {
int left = getChildLeftIndex(index);
int right = getChildRightIndex(index);
int largest = index;
if (left < heapSize && data[index] < data[left]) {
largest = left;
}
if (right < heapSize && data[largest] < data[right]) {
largest = right;
}
if (largest != index) {
int temp = data[index];
data[index] = data[largest];
data[largest] = temp;
maxHeapify(data, heapSize, largest);
}
}
private void heapSort(int[] data) {
for (int i = data.length - 1; i > 0; i--) {
int temp = data[0];
data[0] = data[i];
data[i] = temp;
maxHeapify(data, i, 0);
}
}
private int getParentIndex(int current) {
return (current - 1) >> 1;
}
private int getChildLeftIndex(int current) {
return (current << 1) + 1;
}
private int getChildRightIndex(int current) {
return (current << 1) + 2;
}
}// 交换!
private static void swp(int[] arr, int i, int j) {
int tem = arr[i];
arr[i] = arr[j];
arr[j] = tem;
}// 打印!
private static <T> void sop(T t) {
System.out.print(t);
}
}