package runoob;
import java.util.Arrays;
public class Quick_sort {
public static void sort(Integer[] arr, int L, int R) {
//边界条件是只有一个元素的时候退出也就是左边等于右边
if (L >= R) {
return;
}//nextlow指向即将填充比pivot小的值得位置
long pivot = arr[L];
int nextLow = L + 1;
int now = L + 1;//小于等于是因为不排除相同的情况
while (now <= R) {
if (arr[now] <= pivot) {
swap(arr, now, nextLow);
nextLow++;
now++;
} else {
now++;
}
}
swap(arr, L, nextLow - 1);
sort(arr, L, nextLow - 1 - 1);
sort(arr, nextLow, R);
}
public static void RondamQuickSort(Integer[] arr) {
if (arr == null || arr.length < 2) {
return;
}
Process(arr, 0, arr.length - 1);
}
public static void swap(Integer[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void Process(Integer[] arr, int L, int R) {
if (L >= R) {
return;
}
swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
Integer[] equalArea = Nether_lands(arr, L, R);
Process(arr, L, equalArea[0] - 1);
Process(arr, equalArea[1] + 1, R);
}
public static Integer[] Nether_lands(Integer[] arr, int L, int R) {
if (L > R) {
return new Integer[]{-1, -1};
}
if (L == R) {
return new Integer[]{L, R};
}
int less = L - 1;
int more = R;
int index = L;
while (index < more) {
if (arr[index].equals(arr[R])) {
index++;
} else if (arr[index] < arr[R]) {
swap(arr, index++, ++less);
} else {
swap(arr, index, --more);
}
}
swap(arr, more, R);
return new Integer[]{less + 1, more};
}
public static void Quicksort_text(long num) {
Integer[] arr = SortHelper.generateRandomArray(num, 0, 100);//使用数的范围1-100
Integer[] arr2 = Arrays.copyOfRange(arr, 0, arr.length - 1);
long start = System.nanoTime();
sort(arr, 0, arr.length - 1);
long mid = System.nanoTime();
RondamQuickSort(arr2);
long end = System.nanoTime();
System.out.println("当前数据数量为"+num+"为了页面干净选择忽略打印排序结果");
System.out.println("快速排序"+"花费时间:" + (mid - start)/1000 + "(ms)");
System.out.println("随机快速排序"+"花费时间:" + (end - mid)/1000 + "(ms)");
}
}
基于JAVA的千万级算法测试平台
需积分: 5 50 浏览量
2022-06-24
13:04:48
上传
评论
收藏 46KB RAR 举报
Sort_trak.rar （49个子文件） 
Sort_trak src runoob 
RandomSelect.java 2KB ShellSort.java 949B InsertionSort.java 1022B SortHelper.java 960B main.java 2KB Fibonacci.java 2KB MergeSort.java 3KB Power_reckon.java 1KB CountSort.java 2KB Truangle_num.java 2KB SelectionSort.java 1KB Climb.java 1KB Count_road.java 1KB midSort.java 3KB Quick_sort.java 3KB text_sort QuickSort.java 2KB rectangle.java 694B .idea uiDesigner.xml 9KB misc.xml 239B modules.xml 265B workspace.xml 7KB .gitignore 188B out production runoob-algorithm-merge-sort runoob main.class 1KB SortTestHelper.class 1KB SelectionSort.class 2KB ShellSort.class 2KB InsertionSort.class 2KB MergeSort.class 2KB main$textSort.class 1KB Sort_trak runoob main.class 1KB Count_road.class 2KB SortHelper.class 1KB Truangle_num.class 2KB SelectionSort.class 2KB ShellSort.class 2KB CountSort.class 2KB Power_reckon.class 2KB InsertionSort.class 2KB Climb.class 2KB midSort.class 2KB MergeSort.class 3KB Fibonacci.class 2KB Quick_sort.class 3KB main$textSort.class 2KB RandomSelect.class 3KB text_sort Circle.class 980B rectangle.class 311B QuickSort.class 2KB Sort_trak.iml 433B
评论0