本章内容

快速排序

快速排序核心思想：

• 1）选取一个基准元素（pivot），一般选择第一个元素或者最后一个元素。
• 2）从数列的左右两端开始向中间扫描，设两个指针left和right，其中left指向数列的左端，right指向数列的右端。
• 3）比较基准元素和left所指向的元素，如果left所指向的元素小于基准元素，则left右移一位；否则停止移动。
• 4）比较基准元素和right所指向的元素，如果right所指向的元素大于基准元素，则j左移一位；否则停止移动。
• 5）如果left和right都停止移动，则交换left和right所指向的元素。
• 6）重复步骤3到步骤5，直到left和right相遇。
• 7）将基准元素与left所指向的元素交换。
• 8）递归地对左右两个子序列进行快速排序。

注意事项：

• 1）如果选取数列的第一个元素为基准元素，则从right所指向的元素开始与基准元素进行比较；如果选取数列的最后一个元素为基准元素，则从left所指向的元素开始与基准元素进行比较。
• 2）如果选取数列的第一个元素为基准元素，left所指向的元素与基准元素第一次对比时，left下标与基准元素下标相等（即：判断条件中添加等号）；如果选取数列的最后一个元素为基准元素，right所指向的元素与基准元素第一次对比时，right下标与基准元素下标相等。

快速排序示例

将一个无序数列3、7、8、1、5、2、6、4按从小到大的顺序进行排序。按照快速排序的思想，先选取一个基准元素，以数列的第一个元素3为例。

如图所示：

1）选取数列的第一个元素3为基准元素，从数列的右指针开始，比较右指针指向的元素4与基准元素3，4>3，因此右指针向左移动一位。

2）比较右指针指向的元素6与基准元素3，6>3，因此右指针继续向左移动一位。

3）比较右指针指向的元素2与基准元素3，2<3，右指针停止移动；比较左指针指向的元素3与基准元素3，3=3，因此左指针向右移动一位。

4）比较左指针指向的元素7与基准元素3，7>3，左指针停止移动，交换左右指针指向的元素（即：元素7与元素2交换位置）。

5）比较右指针指向的元素7与基准元素3，7>3，因此右指针向左移动一位，以此类推，直到左右指针重合。

6）注意：左右指针在元素1处重合，期间元素1和元素8通过对比基准元素交换了位置。此时，交换基准元素3与左指针（右指针也可以，因为左右指针已经指向同一个位置）指向的元素1的位置，并返回基准点（即：基准元素所在下标p=2），第一轮排序结束。

此时，小于基准元素3的元素（1，2）在基准元素左边，大于基准元素3的元素（8，5，7，6，4）在基准元素右边，继续对左右两边的元素进行递归排序，最终得到完整排序后的有序数列。

其中：

• pivot：选取的基准元素（图中为待排序数列的第一个元素）
• p：基准元素所在下标。
• left：待排序数列左指针。
• right：待排序数列右指针。

快速排序代码实现

/**
 * @author 南秋同学
 * 快速排序算法
 */
public class QuickSort {
  
    /**
     * 快速排序
     * @param a 待排序数组
     * @param l 待排序数组left下标
     * @param r 待排序数组right下标
     */
    public static void quickSort(int[] a, int l, int r){
        // 终止条件
        if(l >= r){
           return ;
        }
        // 获取基准元素下标
        int p = partition(a, l, r);
        // 递归排序左右分区
        quickSort(a, l, p-1);
        quickSort(a, p+1, r);
    }

    /**
     * 获取每轮排序后基准点（即：基准元素在数组中的位置）
     * @param a 待排序数组
     * @param l 待排序数组left下标
     * @param r 待排序数组right下标
     * @return 每轮排序后基准点
     */
    private static int partition(int[] a, int l, int r){
        // 选取基准元素，此处为数列的第一个元素
        int p = a[l];
        // 设置左右指针left和right
        int left = l;
        int right = r;
        while (left < right){
            // 比较基准元素和right所指向的元素，如果right所指向的元素大于基准元素，则j左移一位；否则停止移动。
            while (left < right && a[right] > p){
                right--;
            }
            // 比较基准元素和left所指向的元素，如果left所指向的元素小于基准元素，则left右移一位；否则停止移动。
            // 特别注意：由于选取数列的第一个元素为基准元素，判断时left所指向的元素时可以等于基准元素。
            while (left < right && a[left] <= p){
                left++;
            }
            // 交换left和right所指向的元素。
            swap(a, left, right);
        }
        // 将基准元素与left所指向的元素交换。
        swap(a,l,left);
        System.out.println(Arrays.toString(a) + " 排序后，基准元素["+p+"]在数列中的下标为：" + left);
        return left;
    }

    /**
     * 交换left和right所指向的元素
     * @param a 待排序数组
     * @param left 元素下标
     * @param right 元素下标
     */
    public static void swap(int[] a,int left,int right){
        int t=a[left];
        a[left]=a[right];
        a[right]=t;
    }

    public static void main(String[] args) {
        int[] a = {3,7,8,1,5,2,6,4};
        System.out.println("待排序数组："+Arrays.toString(a));
        QuickSort.quickSort(a, 0, a.length-1);
    }
}

快速排序复杂度

快速排序是一种原地、不稳定的排序算法，时间复杂度一般为 O(nlogn) ，最坏退化成O(n2)（如：原来数组已经有序，快速排序的时间复杂度就退化成O(n2)）。

【内容推荐】

堆与堆排序算法->请移步【一发入魂】堆与堆排序算法。

【作者简介】

一枚热爱技术和生活的老贝比，专注于Java领域，关注【南秋同学】带你一起学习成长～