目录
一、单边快排
代码：已是该算法的最优情况
package com.wxl;
import java.lang.reflect.Array;
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = {5, 3, 7, 2, 9, 8, 1, 4};
singleFastSort(arr);
}
private static void swap(int[] arr, int pre, int after) {
if (arr[pre] > arr[after]) {
int temp = arr[pre];
arr[pre] = arr[after];
arr[after] = temp;
}
}
private static void singleFastSort(int[] arr) {
singleFastSortRecursion(arr, 0, arr.length - 1);
System.out.println("最终结果：");
System.out.println(Arrays.toString(arr));
}
private static void singleFastSortRecursion(int[] arr, int startIndex, int endIndex) {
if (startIndex >= endIndex) {
return;
}
int p = singleFastSortPartition(arr, startIndex, endIndex);
singleFastSortRecursion(arr, startIndex, p - 1);//左边区域继续调用
singleFastSortRecursion(arr, p + 1, endIndex);//右边区域继续调用
}
private static int singleFastSortPartition(int[] arr, int startIndex, int endIndex) {
int i = startIndex;//最小下标标记指针
int standpoint = arr[endIndex];//基准点，取最右边
for (int j = startIndex; j < endIndex; j++) {
if (arr[j] < standpoint) {
if (i != j) {
swap(arr, i, j);
}
i++;//后移一位
}
}
if (i != endIndex) {
swap(arr, i, endIndex);
}
System.out.println(Arrays.toString(arr) + " i=" + i);
return i;//返回边界下标
}
}
运行结果：
[3, 2, 1, 4, 9, 8, 7, 5] i=3
[1, 2, 3, 4, 9, 8, 7, 5] i=0
[1, 2, 3, 4, 9, 8, 7, 5] i=2
[1, 2, 3, 4, 5, 8, 7, 9] i=4
[1, 2, 3, 4, 5, 8, 7, 9] i=7
[1, 2, 3, 4, 5, 7, 8, 9] i=5
最终结果：
[1, 2, 3, 4, 5, 7, 8, 9]单边快排排序逻辑：
数组：5, 3, 7, 2, 9, 8, 1, [4]
基准点用[]，拍好序的部分用()，下次排序的部分{}
第一次排序：{3, 2, [1]}, (4), 9, 8, 7, 5 i=3
第二次排序：(1), {2, [3]}, (4), 9, 8, 7, 5 i=0
第三次排序：(1, 2, 3, 4), {9, 8, 7, [5]} i=1
第四次排序：(1, 2, 3, 4, 5), {8, 7, [9]} i=4
第五次排序：(1, 2, 3, 4, 5), {8, [7]}, (9) i=7
第六次排序：(1, 2, 3, 4, 5, 7, 8, 9) i=5二、双边快排
代码：
package com.wxl;
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = {5, 3, 7, 2, 9, 8, 1, 4};
dubbleFastSort(arr);
}
private static void swap(int[] arr, int pre, int after) {
if (arr[pre] > arr[after]) {
int temp = arr[pre];
arr[pre] = arr[after];
arr[after] = temp;
}
}
private static void dubbleFastSort(int[] arr) {
dubbleFastSortRecursion(arr, 0, arr.length - 1);
System.out.println("最终结果：");
System.out.println(Arrays.toString(arr));
}
private static void dubbleFastSortRecursion(int[] arr, int startIndex, int endIndex) {
if (startIndex >= endIndex) {
return;
}
int p = dubbleFastSortPartition(arr, startIndex, endIndex);
dubbleFastSortRecursion(arr, startIndex, p - 1);//左边区域继续调用
dubbleFastSortRecursion(arr, p + 1, endIndex);//右边区域继续调用
}
private static int dubbleFastSortPartition(int[] arr, int startIndex, int endIndex) {
int standPoint = arr[startIndex];//基准点
int i = startIndex;//从左往右找大于基准点
int j = endIndex;//从右往左找小于基准点
while (i < j) {
while (i < j && arr[j] > standPoint) {
j--;
}
while (i < j && arr[i] <= standPoint) {
i++;
}
swap(arr, i, j);
}
swap(arr, startIndex, j);
System.out.println(Arrays.toString(arr) + " j=" + j);
return j;
}
}
运行结果：
[1, 3, 4, 2, 5, 8, 9, 7] j=4
[1, 3, 4, 2, 5, 8, 9, 7] j=0
[1, 2, 3, 4, 5, 8, 9, 7] j=2
[1, 2, 3, 4, 5, 7, 8, 9] j=6
最终结果：
[1, 2, 3, 4, 5, 7, 8, 9]双边快排排序逻辑：
数组：[5], 3, 7, 2, 9, 8, 1, 4
基准点用[]，拍好序的部分用()，下次排序的部分{}
第一次排序：{[1], 3, 4, 2}, (5), 8, 9, 7 j=4
第二次排序：(1), {[3], 4, 2}, (5), 8, 9, 7 j=0
第三次排序：(1), 2, (3), 4, (5), {[8], 9, 7} j=2
第四次排序：(1, 2, 3, 4, 5), 7, (8), 9 j=6
可以看到双边快排比单边快排效率高些
