目录
1. 快速排序介绍
- 快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
2. 示意图
- 以数组最后一个数作为基准比较大小，小于基准放左边，大于基准放右边，等于基准放中间，然后递归对小于和大于基准的区域继续比较大小，最后将整个数组变成有序序列
3. 代码实现
- 这里说明以下，以数组最右侧的值作为基准，但是为了防止最坏情况出现（比如1，2，3，4，5，6，7，8，9），所以从数组里随机选一个数字和最右侧数字交换位置，然后作为基准
import java.util.Arrays;
import java.util.Random;
public class QuickSort {
public static void main(String[] args) {
int[] arr = new int[10];
Random random = new Random();
for (int j = 0; j < 10; j++) {
arr[j] = random.nextInt(100);
}
System.out.println("排序前" + Arrays.toString(arr));
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后" + Arrays.toString(arr));
}
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
// 为了防止最差情况，比如1，2，3，4，5，6，7，8，9，如果使用最右侧数字作为基准值进行比较，时间复杂度则变为O(n^2)
// 从数组中随机挑选一个数，交换到最右侧，作为基准值进行比较，时间复杂度则变为O(n * log n)
// swap(arr, left + (new Random().nextInt(right - left + 1)), right);
swap(arr, left + (int) (Math.random() * (right - left + 1)), right);
int[] equalArea = process(arr, left, right);
quickSort(arr, left, equalArea[0] - 1);
quickSort(arr, equalArea[1] + 1, right);
}
public static int[] process(int[] arr, int left, int right) {
if (left > right) {
return new int[]{-1, -1};
}
if (left == right) {
return new int[]{left, right};
}
// 定义小于区域的索引位置
int less = left - 1;
// 定义大于区域的索引位置
int more = right;
// 从left位置开始遍历
int index = left;
// 只有还没到达大于区域的边界就继续遍历
while (index < more) {
// 设置arr[right]为基准值进行比较，并且arr[right]这个数字不动
if (arr[index] == arr[right]) {
// 等于基准值，索引后移
index++;
} else if (arr[index] < arr[right]) {
// 找到小于基准值的数字
// 1.将index位置的数和less右边的数进行交换
// 2.将less+1右移一位
// 3.将index+1后移一位
swap(arr, index++, ++less);
} else {
// 找到大于基准值的数字
// 1.将index位置的数和more左边的数进行交换
// 2.more-1左移一位
// 3.index位置不动（因为从右边换过来的数字还没比较过，所以这个index不变；
// 上面需要后移是因为左边的数字都遍历比较过了，所以index+1）
swap(arr, index, --more);
}
// 经过上面的比较和交换，最终<=less区间的数字都小于arr[right]
// less+1~more-1间的数字都等于arr[right]
// more~right-1间的数字都大于arr[right]
}
// 最后把arr[right]和arr[more]交换，这样等于arr[right]的数字就全在数组中间位置了，即less+1~more
swap(arr, more, right);
return new int[]{less + 1, more};
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
排序前[87, 19, 53, 86, 46, 51, 26, 92, 44, 60]
排序后[19, 26, 44, 46, 51, 53, 60, 86, 87, 92]
