快速排序（Hoare法实现partition）

96 阅读 0 评论 64 点赞

我是靠谱客的博主清脆未来，最近开发中收集的这篇文章主要介绍快速排序（Hoare法实现partition），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、什么是快速排序？

快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

二、快速排序的排序流程
快速排序是通过多次比较和交换来实现排序的。

首先在待排序列中确定一个基准值，遍历整个序列，将小于（可包含等于）基准值的元素放到基准值左边，将大于（可包含等于）基准值的元素放到其右边。（降序序列可将位置调整）
此时基准值将序列分割成俩个部分，左边的元素全部小于基准值，右边的元素全部大于基准值。
将分割的左右俩部分进行如上俩步操作，实则为递归。
通过递归将左右俩侧排好序，直至分割的小序列个数为1，排序全部完成。

以上为快速排序的思路和排序流程。

从上面的信息我们可以得出：
（1）排序之前需要确定一个基准值，在这里我们约定基准值为每个序列的第一个元素。
（2）排序需要递归，递归函数的形参列表为待排序序列。递归出口是形参列表的序列的元素个数为1.

递归函数：

public static void quickSortInter(int[] arr,int left,int right){
        if(left >= right){//当数组长度小于等于1时return
            return;
        }
        int pivotIndex = partition(arr,left,right);//基准值下标

        //递归方法，用partition将数组分为左右俩个小数组，用同样的方法将小数组分割，直至小数组元素个数小于等于1
        quickSortInter (arr,left,pivotIndex-1);
        quickSortInter (arr,pivotIndex+1,right);

    }

但是如何以基准值为界，将待排序列分为左右俩个部分呢？
我们有三种方式实现partiton：

Hoare法

Hoare法实现partition核心代码：

 public static int partition(int[] arr,int left,int right){
        int begin = left;
        int end = right;
        int pivot = arr[left];//基准值
        
        //遍历整个数字，以基准值为标准分割数组
        while(begin < end) {
            while (begin < end && arr[end] >= pivot) {
                end--;
            }
            while (begin < end && arr[begin] <= pivot) {
                begin++;
            }
            swap(arr,begin,end);
        }
        // 遍历完整个数组后，begin的位置是小于pivot的最后一个数字，将其与left（基准值）的值交换
        // 此时begin左边的都是小于基准值的数字，右边都是大于基准值的数字，成功将数字分割
        swap(arr,begin,left);
        return begin;
    }