假设我的数组里有100万个数字且顺序混乱,我需要对这些数字进行排序,要求用最高效的方式进行排序,用Java代码实现
时间: 2024-02-15 22:04:14 浏览: 95
可以使用快速排序(Quick Sort)算法来对这些数字进行排序,它是一种基于比较的排序算法,平均时间复杂度为O(nlogn)。
以下是使用Java代码实现的快速排序算法:
```java
public class QuickSort {
public static void main(String[] args) {
int[] arr = new int[1000000];
// 填充随机数
Random random = new Random();
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(1000000);
}
long start = System.currentTimeMillis();
quickSort(arr, 0, arr.length - 1);
long end = System.currentTimeMillis();
System.out.println("排序用时:" + (end - start) + "ms");
}
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
}
public static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
int i = left + 1;
int j = right;
while (true) {
while (i <= j && arr[i] <= pivot) {
i++;
}
while (i <= j && arr[j] > pivot) {
j--;
}
if (i >= j) {
break;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
arr[left] = arr[j];
arr[j] = pivot;
return j;
}
}
```
使用这段代码可以进行快速排序,其中使用了随机数填充数组,排序用时为排序开始时间和结束时间的差值。
阅读全文