普通快排
简介
快速排序是一种高效的排序算法，利用分治的思想进行排序。它的基本原理是在待排序的n个数据中任取一个数据为分区标准，把所有小于该排序码的数据移到左边，把所有大于该排序码的数据移到右边，中间放所选记录，称之为一趟排序。然后，对前后两个子序列重复上述过程，直到所有记录都排好序。通俗点说，大致过程是对于一个无序序列，找到一个"哨兵数"，将序列中所有比哨兵数小的数字都移在哨兵数的左边，所有比哨兵数大的数字都移在哨兵数的右边；然后分别对哨兵数左边和右边再使用同样的方法找到新的哨兵数，并再次进行分类，直到集合不可分割为止。
过程
实现快速排序的过程大致如下：
- 从数组的中间位置开始，取出一个数字作为临时变量；
- 然后再从数组的右边开始遍历，寻找一个值比临时变量小的数，挖出这个数来，对上一个坑进行填坑；
- 然后从数组前面遍历，寻找一个比临时变量大的数，填上面的坑。
以上是快速排序的基本步骤，需要注意的是，在实际的编程实现中，还需要处理一些特殊情况，例如当待排序数组为空或只有一个元素时。
public class QuickSort { public static void quickSort(int[] arr, int left, int right) { if (left < right) { int pivotIndex = partition(arr, left, right); quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex + 1, right); } } private static int partition(int[] arr, int left, int right) { int pivot = arr[right]; // 选择最右边的数作为哨兵数 int i = left - 1; // i指向比哨兵数小的数所在的位置 for (int j = left; j < right; j++) { if (arr[j] <= pivot) { i++; swap(arr, i, j); // 将比哨兵数小的数移到左边 } } swap(arr, i + 1, right); // 将哨兵数移到正确的位置上 return i + 1; // 返回哨兵数的位置 } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
运行结果
int[] arr = {9, 2, 7, 5, 1}; QuickSort.quickSort(arr, 0, arr.length - 1); System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 5, 7, 9]
省下一个变量空间的快排
步骤
这个实现的基本步骤是：
- 选择一个"哨兵数"（这里选择的是数组的第一个元素），并将数组分为两部分，一部分是小于哨兵数的元素，另一部分是大于哨兵数的元素。这个操作由
partition函数完成。 - 对小于哨兵数的元素和大于哨兵数的元素分别进行递归排序。也就是说，对这两部分再分别调用
quickSort函数进行排序。
在partition函数中，核心的思路是利用两个指针，一个从数组的右边开始向左移动，另一个从数组的左边开始向右移动。当左边的指针找到的数小于等于哨兵数，而右边的指针找到的数大于哨兵数时，交换这两个数。这样，经过一段时间后，左边的指针就会碰到第一个小于哨兵数的数，右边的指针就会碰到第一个大于哨兵数的数。这个时候，将哨兵数放到这两个数的中间位置。这样，就完成了一趟排序。
详细讲解
让我来为你讲解一下这段Java代码实现的快速排序算法。
首先，我们定义了一个名为quickSort的静态方法，它接受一个整数数组arr以及两个索引low和high作为参数。这个方法用于对数组的一部分进行排序，其中low是起始索引，而high是结束索引。
在quickSort方法中，我们首先检查low是否小于high。如果不是，说明数组已经排好序了，我们直接返回。
接下来，我们调用partition方法来对数组进行分区。这个方法会选择一个"哨兵数"，然后将数组分为两部分：一部分是小于哨兵数的元素，另一部分是大于哨兵数的元素。这个过程是通过交换元素的位置来实现的。
然后，我们对小于哨兵数的元素和大于哨兵数的元素分别递归调用quickSort方法进行排序。这样，我们就可以保证在每一层递归中，都比上一层的排序更加精确。
接下来，我们来看看partition方法的实现。在这个方法中，我们选择数组的最后一个元素作为哨兵数。然后，我们使用两个指针，一个从数组的左边开始向右移动，另一个从数组的右边开始向左移动。当左边的指针找到的数小于等于哨兵数，而右边的指针找到的数大于哨兵数时，交换这两个数。这样，经过一段时间后，左边的指针就会碰到第一个小于哨兵数的数，右边的指针就会碰到第一个大于哨兵数的数。这个时候，将哨兵数放到这两个数的中间位置。这样，就完成了一趟排序。
最后，返回的是排好序的数组。你可以使用循环遍历输出数组中的每个元素来查看排序结果。
package com.learn; public class QuickSort { public static void main(String[] args) { int[] arr = {3, 8, 2, 5, 1, 4, 7, 6}; quickSort(arr, 0, arr.length - 1); for (int i : arr) { System.out.print(i + " "); } } public static void quickSort(int[] arr, int low, int high) { if (low < high) { int pivotIndex = partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex + 1, high); } } public static int partition(int[] arr, int low, int high) { int pivot = arr[low];//会有优化 while (low < high) { while (low < high && arr[high] >= pivot) { high--; } arr[low] = arr[high]; while (low < high && arr[low] <= pivot) { low++; } arr[high] = arr[low]; } arr[low] = pivot; return low; } }
