Java:根据所给的数据,分别对前100、前1000及全部数据分别使用冒泡排序和Java的Qsort进行排序,并计时。
时间: 2024-09-25 20:10:12 浏览: 36
java数组排序示例(冒泡排序、快速排序、希尔排序、选择排序)
在Java中,我们可以使用`System.currentTimeMillis()`来获取当前时间,然后在开始和结束排序操作时记录时间,以此计算排序算法的时间复杂度。这里我们将演示如何分别对前100、前1000以及全部数据进行冒泡排序和快速排序(Java标准库中的`Arrays.sort()`函数实际上使用了快速排序),并记录它们各自所需的时间。
首先,我们来创建一个简单的冒泡排序方法:
```java
public class BubbleSort {
public static void bubbleSort(int[] data, int n) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (data[j] > data[j + 1]) {
// 交换元素
int temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
}
long endTime = System.currentTimeMillis();
long duration = endTime - startTime;
System.out.printf("Bubble sort on %d elements took %d milliseconds\n", n, duration);
}
}
```
对于快速排序,可以直接使用`Arrays.sort()`:
```java
import java.util.Arrays;
public class QuickSort {
public static void quickSort(int[] data, int low, int high) {
long startTime = System.currentTimeMillis();
Arrays.sort(data, low, high);
long endTime = System.currentTimeMillis();
long duration = endTime - startTime;
System.out.printf("Quick sort on %d elements took %d milliseconds\n", data.length, duration);
}
}
```
现在,你可以按照以下步骤进行:
1. 创建一个足够大的数组,比如10000个随机整数。
2. 分别提取前100个、前1000个元素到新的数组里。
3. 对这三组数据(100、1000和全部)分别调用上述两个排序方法。
注意,由于快速排序通常比冒泡排序快得多,所以当你处理大数组时,冒泡排序的性能会非常显著地落后于`Arrays.sort()`.
阅读全文