实验要求: 1. 用随机函数生成n个2位正整数(10~99); 2. 用插入排序、选择排序、快速排序三种排序算法实现,分别输出排序中间过程、统计关键字的比较次数和记录的移动次数;写一个java算法
时间: 2024-05-21 19:11:42 浏览: 25
好的,您的第一个问题是排序算法相关的。以下是Java的代码实现:
import java.util.Random;
public class SortAlgorithms {
public static void main(String[] args) {
int[] arr = generateRandomNumbers(10); // 生成10个随机数
System.out.println("排序前:");
printArray(arr);
int[] arr1 = arr.clone();
System.out.println("\n插入排序过程:");
int num1 = insertionSort(arr1);
System.out.println("插入排序比较次数:" + num1);
int[] arr2 = arr.clone();
System.out.println("\n选择排序过程:");
int num2 = selectionSort(arr2);
System.out.println("选择排序比较次数:" + num2);
int[] arr3 = arr.clone();
System.out.println("\n快速排序过程:");
int[] arr4 = quickSort(arr3, 0, arr.length - 1);
System.out.println("快速排序比较次数:" + num3);
}
// 生成随机数
public static int[] generateRandomNumbers(int n) {
int[] arr = new int[n];
Random rand = new Random();
for (int i = 0; i < n; i++) {
arr[i] = rand.nextInt(90) + 10; // 生成10~99的随机数
}
return arr;
}
// 插入排序
public static int insertionSort(int[] arr) {
int n = arr.length;
int compares = 0;
int moves = 0;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
compares++;
arr[j + 1] = arr[j];
j = j - 1;
moves++;
}
arr[j + 1] = key;
moves++;
printArray(arr);
}
System.out.println("插入排序移动次数:" + moves);
return compares;
}
// 选择排序
public static int selectionSort(int[] arr) {
int n = arr.length;
int compares = 0;
int moves = 0;
for (int i = 0; i < n - 1; i++) {
int min_index = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
compares++;
}
int temp = arr[min_index];
arr[min_index] = arr[i];
arr[i] = temp;
moves++;
printArray(arr);
}
System.out.println("选择排序移动次数:" + moves);
return compares;
}
// 快速排序
public static int[] quickSort(int[] arr, int low, int high) {
int compares = 0;
int moves = 0;
if (low < high) {
int partition_index = partition(arr, low, high);
quickSort(arr, low, partition_index - 1);
quickSort(arr, partition_index + 1, high);
}
return arr;
}
// 快速排序中的分区函数
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
printArray(arr);
return i + 1;
}
// 打印数组
public static void printArray(int[] arr) {
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
}
希望这个代码可以帮到您!