【Java】数据结构-快速排序（完整代码）
本帖最后由 孤樱懶契 于 2021-10-23 22:40 编辑# 快速排序执行耗时结果截图
!(https://gitee.com/gylq/cloudimages/raw/master/img/image-20210630045234675.png)
# 快速排序执行（完整代码）
## QuickSort.java（进行了三层优化之后的算法时间进行比较）
```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){
//生成之间的随机索引
int p = l + rnd.nextInt(r-l+1);
swap(arr, l , p);
// arr < v; arr >v
int j=l;
for(int i = l + 1; i<= r; i++){
if(arr.compareTo(arr) < 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){
//生成之间的随机索引
int p = l + rnd.nextInt(r-l+1);
swap(arr, l , p);
// arr < v; arr >v
// int j=l;
// for(int i = l + 1; i<= r; i++){
// if(arr.compareTo(arr) < 0){
// j ++;
// swap(arr, j, i);
// }
// }
// swap(arr, l,j);
// return j;
// arr <= v; arr >= v
int i = l+1 , j = r;
while(true){
while(i <= j && arr.compareTo(arr) < 0)
i ++;
while(j >= i && arr.compareTo(arr) > 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;
//生成之间的随机索引
int p = l + rnd.nextInt(r-l+1);
swap(arr, l , p);
// arr < v, arr == v , arr > v
int lt = l , i = l + 1, gt = r + 1; //初始空区间
while(i < gt){
if(arr.compareTo(arr)<0){
lt ++;
swap(arr, i , lt );
i ++;
}
else if(arr.compareTo(arr)>0){
gt --;
swap(arr, i, gt);
}
else{ // arr == arr
i ++;
}
}
swap(arr,l ,lt);
// arr < v, arr == v, arr > 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;
arr = arr;
arr = 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个元素的数组)
```java
import java.util.Random;
public class ArrayGenerator {
private ArrayGenerator(){}
public static Integer[] generateOrderedArray(int n){
Integer[] arr = new Integer;
for(int i = 0; i < n ; i++)
arr = i;
return arr;
}
// 生成一个长度为 n 的随机数组， 每个数字的范围是[ 0 , bound)
public static Integer[] generateRandomArray(int n, int bound){
Integer[] arr = new Integer;
Random rnd = new Random();
for(int i = 0 ; i < n; i++)
arr = 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.compareTo(arr) > 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));
}
}
```
过来学习学习!! 不要用包装类，会慢很多 过来看看学习学习。
页:
[1]