我使用Java进行了一项实验,以确定哪种排序方法(气泡或选择)运行时更快。该程序提示用户输入一个数字n
,该数字是要排序的数组中的项目数。然后,它会创建并排序500个此大小的不同数组,并对运行次数进行计时,以得出使用这两种排序方法进行排序的平均时间。我使用500、1000和2500作为的测试输入n
。我的以下结果表明选择排序的运行速度比气泡排序的运行速度快,但是两种算法的时间复杂度均为O(n ^ 2),那么为什么选择排序的运行速度如此之快?
TimeBubbleSort类
public class TimeBubbleSort {
public static void main(String[] args) {
System.out.print("Enter a number of items in array: ");
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
long start_time = 0;
long end_time = 0;
long running_time = 0;
long final_time = 0;
BubbleSort bubbleSort = new BubbleSort();
for(int i = 0; i < 500; i++) {
int[] array = new int[n];
for(int j = 0; j < array.length; j++) {
array[j] = (int)(Math.random() * n) + 1;
}
start_time = System.nanoTime();
bubbleSort.bubbleSort(array);
end_time = System.nanoTime();
running_time = end_time - start_time;
final_time = final_time + running_time;
}
System.out.println("The average time of each array took " +
(final_time / 500) + " nanoseconds");
}
}
BubbleSort类
public class BubbleSort {
void bubbleSort(int[] arr) {
int n = arr.length;
int temp = 0;
for (int i = 0; i < n; i++)
for (int j = 1; j < (n - i); j++)
if (arr[j - 1] > arr[j]) {
temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
void printArray(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
}
TimeSelectionSort类
public class TimeBubbleSort {
public static void main(String[] args) {
System.out.print("Enter a number of items in array: ");
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
long start_time = 0;
long end_time = 0;
long running_time = 0;
long final_time = 0;
SelectionSort selectionSort = new SelectionSort();
for(int i = 0; i < 500; i++) {
int[] array = new int[n];
for(int j = 0; j < array.length; j++) {
array[j] = (int)(Math.random() * n) + 1;
}
start_time = System.nanoTime();
selectionSort.selectionSort(array);
end_time = System.nanoTime();
running_time = end_time - start_time;
final_time = final_time + running_time;
}
System.out.println("The average time of each array took " +
(final_time / 500) + " nanoseconds");
}
}
SelectionSort类
public class SelectionSort {
void sort(int arr[]) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
void printArray(int arr[]) {
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
}
使用冒泡排序的结果
500的阵列大小:耗时284,979纳秒
数组大小为1000:耗时960,067纳秒
阵列大小2500:耗时7,448,865纳秒
使用选择排序的结果
数组大小为500:耗时107,035纳秒
数组大小为100:花费342,464纳秒
数组大小2500:花费了1,880,215纳秒
首先,与系统时间进行比较不是分析两种算法的时间复杂性的正确方法,因为请记住-您的程序不是系统上运行的唯一程序。因此,即使算法和输入相同,两个运行时间也可能完全不同。
现在得出您的答案,气泡排序具有比选择排序更多的交换数量,在选择排序中,我们仅在每次迭代的最后一步进行交换。因此,这可能是原因。
而且这两种算法具有相同的时间复杂度并不意味着它们的运行时间会相同。首先,它们的时间复杂度被近似估算,这是贡献最大的最大因素。在上述两种情况下,最大因子均为n ^ 2,但还有其他较小的n次方和常数将导致差。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句