快速排序的新用法

普通快排

简介

快速排序是一种高效的排序算法，利用分治的思想进行排序。它的基本原理是在待排序的n个数据中任取一个数据为分区标准，把所有小于该排序码的数据移到左边，把所有大于该排序码的数据移到右边，中间放所选记录，称之为一趟排序。然后，对前后两个子序列重复上述过程，直到所有记录都排好序。通俗点说，大致过程是对于一个无序序列，找到一个"哨兵数"，将序列中所有比哨兵数小的数字都移在哨兵数的左边，所有比哨兵数大的数字都移在哨兵数的右边；然后分别对哨兵数左边和右边再使用同样的方法找到新的哨兵数，并再次进行分类，直到集合不可分割为止。

过程

实现快速排序的过程大致如下：

1. 从数组的中间位置开始，取出一个数字作为临时变量；
2. 然后再从数组的右边开始遍历，寻找一个值比临时变量小的数，挖出这个数来，对上一个坑进行填坑；
3. 然后从数组前面遍历，寻找一个比临时变量大的数，填上面的坑。

以上是快速排序的基本步骤，需要注意的是，在实际的编程实现中，还需要处理一些特殊情况，例如当待排序数组为空或只有一个元素时。

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]

省下一个变量空间的快排

步骤

这个实现的基本步骤是：

1. 选择一个"哨兵数"（这里选择的是数组的第一个元素），并将数组分为两部分，一部分是小于哨兵数的元素，另一部分是大于哨兵数的元素。这个操作由partition函数完成。
2. 对小于哨兵数的元素和大于哨兵数的元素分别进行递归排序。也就是说，对这两部分再分别调用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;
    }
}