<分区>
对于 CS 家庭作业，我将在 Java 中创建大小不断增加的随机数组，并将它们的运行时间绘制在图表上。但是，当使用相同的输入运行时，我的插入、合并和快速排序的实现似乎具有相同的运行时间。我已经多次以不同的方式实现它们，但仍然得到相同的结果。这是我的代码:
import java.util.*; import java.util.Random;
public class Complexity {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner input= new Scanner(System.in);
System.out.println("Enter the array size: ");
int a = input.nextInt();
System.out.println("Enter the number size: ");
int n = input.nextInt();
int[] arr = newArr(a, n);
int[] arr2 = arr.clone();
int[] arr3 = arr.clone();
//INSERT SORT
long startTime = System.nanoTime();
insertSort(arr);
long endTime = System.nanoTime();
long duration = (endTime - startTime)/1000000;
System.out.println("Insert Sort Time:" + duration + "ms");
//MERGE SORT
long start = System.nanoTime();
mergeSort(arr2, 0, a-1);
long end = System.nanoTime();
long dur = (end - start)/1000000;
System.out.println("Merge Sort Time:" + duration + "ms");
//QUICK SORT
long s = System.nanoTime();
quickSort(arr3, 0, a-1);
long e = System.nanoTime();
long d = (e - s);
System.out.println("Quick Sort Time:" + duration + "ms");
}
public static int[] newArr(int a, int n) {
Random rand = new Random();
int newArray[] = new int[a];
for (int i = 0; i < a; i++) {
int number= rand.nextInt(n);
newArray[i]=number;
}
return newArray;
}
public static void quickSort(int[] arr, int low, int high) {
if(low<high) {
int pivotIndex = findPivot(arr, low, high);
quickSort(arr, low, pivotIndex-1);
quickSort(arr, pivotIndex+1, high);
}
}
public static int findPivot(int[] arr, int low, int high) {
int pivot = arr[high];
int nextSmallest = (low-1);
for(int currentIndex = low; currentIndex < high; currentIndex++) {
if(arr[currentIndex] <= pivot) {
nextSmallest++;
int temp = arr[nextSmallest];
arr[nextSmallest] = arr[currentIndex];
arr[currentIndex] = temp;
}
}
int temp = arr[nextSmallest+1];
arr[nextSmallest+1] = arr[high];
arr[high] = temp;
return nextSmallest+1;
}
public static void mergeSort(int[] arr, int left, int right){
if(left<right) {
int middle = (left + right) / 2;
mergeSort(arr, left, middle);
mergeSort(arr, middle+1, right);
merge(arr, left, middle, right);
}
}
public static void merge(int[] arr, int left, int middle, int right){
int leftLength = middle - left + 1;
int rightLength = right - middle;
int newL[] = new int [leftLength];
int newR[] = new int [rightLength];
for (int i=0; i<leftLength; ++i)
newL[i] = arr[left + i];
for (int j=0; j<rightLength; ++j)
newR[j] = arr[middle + 1+ j];
int i = 0, j = 0;
int k = left;
while (i < leftLength && j < rightLength) {
if (newL[i] <= newR[j]) {
arr[k] = newL[i];
i++;
}
else {
arr[k] = newR[j];
j++;
}
k++;
}
while (i < leftLength) {
arr[k] = newL[i];
i++;
k++;
}
while (j < rightLength) {
arr[k] = newR[j];
j++;
k++;
}
}
static void printArray(int arr[], String methodName) {
System.out.print(methodName);
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void insertSort(int[] arr){
int temp;
for(int i = 0; i < arr.length; i++) {
for(int j = i ; j > 0 ; j--){
if(arr[j] < arr[j-1]){
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
}
}