快速排序执行耗时结果截图
快速排序执行（完整代码）
QuickSort.java（进行了三层优化之后的算法时间进行比较）
import java.util.Arrays;
import java.util.Random;
public class QuickSort {
private QuickSort(){}
public static <E extends Comparable<E>> void sort(E[] arr){
Random rnd = new Random();
sort(arr, 0, arr.length-1, rnd);
}
private static <E extends Comparable<E>> void sort(E[] arr, int l , int r, Random rnd){
if(l >= r) return;
int p = partition(arr, l , r, rnd);
sort(arr, l, p-1, rnd);
sort(arr, p+1 , r, rnd);
}
private static <E extends Comparable<E>> int partition(E[] arr, int l, int r, Random rnd){
//生成[l,r]之间的随机索引
int p = l + rnd.nextInt(r-l+1);
swap(arr, l , p);
// arr[l+1...j] < v; arr[j+1...i] >v
int j=l;
for(int i = l + 1; i<= r; i++){
if(arr[i].compareTo(arr[l]) < 0){
j ++;
swap(arr, j, i);
}
}
swap(arr, l,j);
return j;
}
public static <E extends Comparable<E>> void sort2ways(E[] arr){
Random rnd = new Random();
sort2ways(arr, 0, arr.length-1, rnd);
}
private static <E extends Comparable<E>> void sort2ways(E[] arr, int l , int r, Random rnd){
if(l >= r) return;
int p = partition2(arr, l , r, rnd);
sort2ways(arr, l, p-1, rnd);
sort2ways(arr, p+1 , r, rnd);
}
private static <E extends Comparable<E>> int partition2(E[] arr, int l, int r, Random rnd){
//生成[l,r]之间的随机索引
int p = l + rnd.nextInt(r-l+1);
swap(arr, l , p);
// arr[l+1...j] < v; arr[j+1...i] >v
// int j=l;
// for(int i = l + 1; i<= r; i++){
// if(arr[i].compareTo(arr[l]) < 0){
// j ++;
// swap(arr, j, i);
// }
// }
// swap(arr, l,j);
// return j;
// arr[l+1...i-1] <= v; arr[j+1...r] >= v
int i = l+1 , j = r;
while(true){
while(i <= j && arr[i].compareTo(arr[l]) < 0)
i ++;
while(j >= i && arr[j].compareTo(arr[l]) > 0)
j --;
if(i >= j) break;
swap(arr, i , j);
i ++;
j --;
}
swap(arr, l , j);
return j;
}
public static <E extends Comparable<E>> void sort3ways(E[] arr){
Random rnd = new Random();
sort3ways(arr, 0, arr.length-1, rnd);
}
private static <E extends Comparable<E>> void sort3ways(E[] arr, int l , int r, Random rnd){
if(l >= r) return;
//生成[l,r]之间的随机索引
int p = l + rnd.nextInt(r-l+1);
swap(arr, l , p);
// arr[l + 1, lt] < v, arr[lt + 1, i - 1] == v , arr[gt, r] > v
int lt = l , i = l + 1, gt = r + 1; //初始空区间
while(i < gt){
if(arr[i].compareTo(arr[l])<0){
lt ++;
swap(arr, i , lt );
i ++;
}
else if(arr[i].compareTo(arr[l])>0){
gt --;
swap(arr, i, gt);
}
else{ // arr[i] == arr[l]
i ++;
}
}
swap(arr,l ,lt);
// arr[l, lt - 1 ] < v, arr[lt , gt - 1] == v, arr[gt, r ] > v
sort3ways(arr, l , lt-1, rnd);
sort3ways(arr, gt , r, rnd);
}
private static <E> void swap(E[] arr, int i , int j){
E t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
int n = 10000000;
Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
Integer[] arr2 = Arrays.copyOf(arr, arr.length);
SortingHelper.sortTest("QuickSort", arr);
SortingHelper.sortTest("QuickSort2", arr2);
arr = ArrayGenerator.generateOrderedArray(n);
arr2 = Arrays.copyOf(arr, arr.length);
SortingHelper.sortTest("QuickSort", arr);
SortingHelper.sortTest("QuickSort2", arr2);
arr = ArrayGenerator.generateRandomArray(n, 1);
arr2 = Arrays.copyOf(arr, arr.length);
Integer[] arr3 = Arrays.copyOf(arr, arr.length);
SortingHelper.sortTest("QuickSort2", arr2);
SortingHelper.sortTest("QuickSort3", arr3);
}
}
ArrayGenerator.java(生成随机n个元素的数组)
import java.util.Random;
public class ArrayGenerator {
private ArrayGenerator(){}
public static Integer[] generateOrderedArray(int n){
Integer[] arr = new Integer[n];
for(int i = 0; i < n ; i++)
arr[i] = i;
return arr;
}
// 生成一个长度为 n 的随机数组， 每个数字的范围是[ 0 , bound)
public static Integer[] generateRandomArray(int n, int bound){
Integer[] arr = new Integer[n];
Random rnd = new Random();
for(int i = 0 ; i < n; i++)
arr[i] = rnd.nextInt(bound); //从0到bound前闭后开
return arr;
}
}
SortingHelper.java（辅助进行算法时间输出的）
public class SortingHelper {
private SortingHelper(){} //私有类
public static <E extends Comparable<E>> boolean isSorted(E[] arr){
for(int i = 1; i< arr.length; i++)
if (arr[i - 1].compareTo(arr[i]) > 0)
return false;
return true;
}
public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
long startTime = System.nanoTime();
if(sortname.equals("SelectionSort")) {
SelectionSort.sort(arr);
} else if(sortname.equals("InsertionSort"))
InsertionSort.sort(arr);
else if(sortname.equals("InsertionSort2"))
InsertionSort.sort2(arr);
else if(sortname.equals("MergeSort"))
MergeSort.sort(arr);
else if(sortname.equals("MergeSort2"))
MergeSort.sort2(arr);
else if(sortname.equals("MergeSort3"))
MergeSort.sort3(arr);
else if(sortname.equals("MergeSort4"))
MergeSort.sort4(arr);
else if(sortname.equals("MergeSortBU"))
MergeSort.sortBU(arr);
else if(sortname.equals("QuickSort"))
QuickSort.sort(arr);
else if(sortname.equals("QuickSort2"))
QuickSort.sort2ways(arr);
else if(sortname.equals("QuickSort3"))
QuickSort.sort3ways(arr);
long endTime = System.nanoTime();
double time = (endTime - startTime) / 1000000000.0; //纳米要/9个零
if(!SortingHelper.isSorted(arr))
throw new RuntimeException(sortname + "failed");
System.out.println(String.format("%s , n = %d : %f s ", sortname, arr.length, time));
}
}
发表于 2021-6-30 04:55
