vlambda博客
学习文章列表

• 1、什么是快速排序？

• 2、算法设计

• 3、如何选择基准元素？

• 4、图解算法

• 5、伪代码详解

• 6、快速排序代码第一版

• 7、快速算法优化

• 8、快速排序代码优化版

1、什么是快速排序？

快速排序是通过一组排序将要排序的数据分割成独立的两个部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归实现，以此使所有数据变成有序序列。

2、算法设计

（1）分解：先从数列中取出一个元素作为基准元素。将问题分解为两个子序列，小于或等于基准元素的子序列在左侧，大于基准元素的子序列在右侧。

（2）治理：对两个子序列进行快速排序

（3）合并：将排好序的有序子序列进行合并，得到最终的有序序列

快速排序与合并排序的区别：

合并排序分解容易，合并难，属于 “先易后难” 。

快速排序合并容易，分解难，属于 “先难后易” 。

假设当前待排序的序列为 R[low:high]，其中 low<=high，如果序列的规模足够小，则直接进行排序，否则分 3 步处理。

（1）分解：在 R[low:high] 中选定一个元素 R[pivot]，以此为基准元素，将要排序的序列划分为两个序列 R[low:pivot-1] 和 R[pivot+1:high]，此时基准元素已经位于正确位置，它无需参加后面的排序，如图3-24所示。

（2）治理：对于两个序列 R[low:pivot-1] 和 R[pivot+1:high] ，分别通过递归调用快速排序算法来进行排序。

（3）合并：由于对两个序列 R[low:pivot-1] 和 R[pivot+1:high]的排序是原地进行的，所以在 R[low:pivot-1] 和 R[pivot+1:high] 都已经排好序之后，合并步骤无需做什么，序列 R[low:high] 就已经排好序了。

3、如何选择基准元素？

如何分解是一个难题，因为如果基准元素选取不当，就有可能分解成规模为 0 和 n-1 的两个子序列，这样就退化成冒泡排序了，例如下面这两种情况。

（1）一个原本逆序的数列，期望排序成顺序数列

（2）选取不当时

例如序列（30，24，5，58，18，36，12，42，39），第一次选取 5 做基准元素，分解后如图3-25所示。

第二次选取 12 做基准元素，分解后如图3-26所示。

这两种选取方法并没有将整个数列分成一半一半，每一轮仅仅确定了一个基准元素的位置，所以这就是快速排序的极端情况，如果需要进行 N 轮，时间复杂度退化为 O(N^2)。

（3）基准元素的选取方法

• 取第一个元素
• 去最后一个元素
• 取中间位置元素
• 取第一个、最后一个、中间位置元素三者之中位数
• 取第一个和最后一个之间位置的随机数 k (low<=k<=high)

4、图解算法

假设当前待排序的序列为 R[low:high]，其中 low<=high（这里选取第一个元素为基准元素）

步骤 1：首先选取数组第一个元素作为基准元素，其中 low<=high。

步骤 2：从右向左扫描，找小于等于 pivot 的数，如果找到 R[i] 与 R[j] 交换，并且 i++。

步骤 3：从左向右扫描，找大于 pivot 的数，如果找到 R[i] 与 R[j] 交换，j--。

步骤 4：重复步骤 2~3，直到 i 和 j 指针重合，返回该位置 mid = i，该位置的数正好是 pivot 元素。

这里以序列（30，24，5，58，18，36，12，42，39）为例，演示排序过程。

（1）初始化。i = low，j = high，pivot = R[low] = 30，如图3-27所示。

（2）向左走。从数组的右边位置向左找，一直找到小于等于 pivot 的数，找到 R[j] = 12，R[i] 和 R[j] 交换，i++，如图3-28 和 3-29所示。

（3）向右走。从数组的左边位置向右找，一直找到大于 pivot 的数，找到 R[i] = 58，R[i] 和 R[j] 交换，j--，如图3-30 和 3-31所示。

（4）向左走。从数组的右边位置向左找，一直找到小于等于 pivot 的数，找到 R[j] = 18，R[i] 和 R[j] 交换，i++，如图3-32和 3-33所示。

（5）向右走。从数组的左边位置向右找，一直找到大于 pivot 的数，这时 i = j，第一轮排序结束并返回 i 的位置，mid = i，如图3-34所示。

此时已完成第一轮排序，以 pivot 为界，将序列分为两个子序列，左侧子序列都比 pivot 小，右侧序列都比 pivot 大。然后接着对这两个子序列进行快速排序。

5、伪代码详解

（1）分解函数

• 将原序列进行分解，分解为两个子序列。先从右往左扫描，找比基准元素小或等于的数，找到后两者交换；再从左往右扫描，找到比基准元素大的数，找到后两者交换。扫描交替，直到 i = j 停止，返回划分的中间位置 i。

/*划分函数，找到基准元素的位置*/
public static int partition(int[] R,int low,int high) {
    int i=low,j=high;
    int pivot=R[low]; //取第一个元素做基准
    while(i<j) {
        while(i<j&&R[j]>pivot)//从右向左扫描，若R[j]大于基准则继续向左走
            j--;
        if(i<j) { //while循环跳出说明找到一个小于基准的元素
            int temp=R[i]; //交换元素位置
            R[i]=R[j];
            R[j]=temp;
            i++;
        }
        while(i<j&&R[i]<pivot)//从左向右扫描，若R[i]小于基准则继续向右走
            i++;
        if(i<j) { //while跳出循环说明找到一个大于基准的元素
            int temp=R[i]; //交换位置
            R[i]=R[j];
            R[j]=temp;
            j--;
        }
    }
    return i;
}

（2）快速排序递归算法

• 首先对原序列进行分解，得到划分的中间位置，然后以中间位置为界，再对左侧(low , mid-1) 和右侧(mid+1 , high) 执行快速排序。递归结束的条件是 low>=high

/*快速排序递归算法*/
public static void quickSort(int[] R,int low,int high) {
    int mid;
    if(low<high) {
        mid=partition(R,low,high);//对原序列进行分解，找到基准位置
        quickSort(R,low,mid-1);//左区间递归快速排序
        quickSort(R,mid+1,high);//右区间递归快速排序
    }
}

6、快速排序代码第一版

/**
 * 快速排序---第一版
 */
public class QuickSort {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        System.out.println("请先输入要排序的数据的个数：");
        int N=input.nextInt();
        System.out.println("请输入要排序的数字：");
        int[] R=new int[N];
        for(int i=0;i<N;i++){
            R[i]=input.nextInt();
        }

        quickSort(R,0,N-1);                                //调用快速排序算法
        System.out.println("排序后的序列为：");
        for(int i=0;i<N;i++) {
            System.out.print(R[i] + " ");
        }
    }

    /*划分函数，找到基准元素的位置*/
    public static int partition(int[] R,int low,int high) {
        int i=low,j=high;
        int pivot=R[low]; //取第一个元素做基准
        while(i<j) {
            while(i<j&&R[j]>pivot)//从右向左扫描，若R[j]大于基准则继续向左走
                j--;
            if(i<j) { //while循环跳出说明找到一个小于基准的元素
                int temp=R[i]; //交换元素位置
                R[i]=R[j];
                R[j]=temp;
                i++;
            }
            while(i<j&&R[i]<pivot)//从左向右扫描，若R[i]小于基准则继续向右走
                i++;
            if(i<j) { //while跳出循环说明找到一个大于基准的元素
                int temp=R[i]; //交换位置
                R[i]=R[j];
                R[j]=temp;
                j--;
            }
        }
        return i;
    }
    /*快速排序递归算法*/
    public static void quickSort(int[] R,int low,int high) {
        int mid;
        if(low<high) {
            mid=partition(R,low,high);//对原序列进行分解，找到基准位置
            quickSort(R,low,mid-1);//左区间递归快速排序
            quickSort(R,mid+1,high);//右区间递归快速排序
        }
    }

}

7、快速算法优化

上述算法每次交换都是和基准元素进行交换，实际上没有必要这样做，我们的目的只是想要将原序列分成以基准元素为界的两个子序列而已。其实我们可以这样做：从右往左扫描，找到小于等于基准元素的数 R[j]，然后从左往右扫描，找到大于基准元素的数 R[i]，让 R[i] 和 R[j] 交换，一直交替进行，直到 i = j，这时就将基准元素与 R[i] 交换即可，这样就完成了一次分解过程，但比起上面的算法这里交换的元素个数少了很多。

假设当前待排序的序列为 R[low:high]，其中 low<=high（这里选取第一个元素为基准元素）

步骤 1：首先选取数组第一个元素作为基准元素，其中 low<=high。

步骤 2：从右向左扫描，找小于等于 pivot 的数 R[j] 就停止运动，i++。

步骤 3：从左向右扫描，找大于 pivot 的数 R[i] 就停止运动。

步骤 4：R[j] 和 R[i] 交换，j--。

步骤 5：重复步骤 2~4，直到 i = j，如果 R[i] 大于 pivot ，则 R[i-1] 和基准元素 R[low] 交换，返回该位置 mid = i-1；否则，R[i] 和 R[low] 交换， 返回该位置 mid = i，该位置正好是基准元素。

下面以序列（6，1，2，7，9，3，4，5，10，8）为例。

（1）初始化。i = low，j = high，pivot = R[low] = 6，如图所示。

（2）向左走。哨兵 j 一步一步地向左挪动（即 j--）,直到找到一个小于等于pivot的数 6 停下来，这时候哨兵 j 停在了数字 5 上。

（3）向右走。哨兵 i 一步一步地向右挪动（即 i++）,直到找到一个大于pivot的数 6 停下来，这时候哨兵 i 停在了数字 7 上。

（4）现在交换哨兵 i 和哨兵 j 所指向的元素的值，如图所示。

（5）向左走。哨兵 j 一步一步继续地向左挪动（即 j--）,直到找到一个小于等于pivot的数 6 停下来，这时候哨兵 j 停在了数字 4 上。

（6）向右走。哨兵 i 一步一步继续地向右挪动（即 i++）,直到找到一个大于pivot的数 6 停下来，这时候哨兵 i 停在了数字 9 上。

（7）现在交换哨兵 i 和哨兵 j 所指向的元素的值，如图所示。

（8）向左走。哨兵 j 一步一步继续地向左挪动（即 j--）,直到找到一个小于等于pivot的数 6 停下来，这时候哨兵 j 停在了数字 3 上。

（9）向右走。哨兵 i 一步一步继续地向右挪动（即 i++）,这时哨兵 i 和哨兵 j 相遇了（i = j），停止移动。

（10）现在交换哨兵 i 和哨兵 j 所指向的元素的值，如图所示。

然后再接着对这两个子序列（3，1，2，5，4）和（9，7，10，8）进行快速排序。

下面来一个霸气的图描述一下整个算法的处理过程。

8、快速排序代码优化版

/**
 * 快速排序---第优化版
 */
public class QuickSort2 {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        System.out.println("请先输入要排序的数据的个数：");
        int N=input.nextInt();
        System.out.println("请输入要排序的数字：");
        int[] R=new int[N];
        for(int i=0;i<N;i++){
            R[i]=input.nextInt();
        }

        quickSort(R,0,N-1);                                //调用快速排序算法
        System.out.println("排序后的序列为：");
        for(int i=0;i<N;i++) {
            System.out.print(R[i] + " ");
        }
    }

    /*划分函数，找到基准元素的位置*/
    public static int partition(int[] R,int low,int high) {
        int i=low,j=high;
        int pivot=R[low]; //取第一个元素做基准
        while(i<j) {
            while(i<j&&R[j]>pivot)//从右向左扫描，若R[j]大于基准则继续向左走
                j--;
            while(i<j&&R[i]<=pivot)//从左向右扫描，若R[i]小于基准则继续向右走
                i++;
            if(i<j) { //交换i和j的元素位置
                int temp=R[i]; //交换位置
                R[i]=R[j];
                R[j]=temp;
            }
        }
        //基准元素和指针重合点交换位置
        int p = R[i];
        R[i] = R[low];
        R[low] = p;

        return i;
    }
    /*快速排序递归算法*/
    public static void quickSort(int[] R,int low,int high) {
        int mid;
        if(low<high) {
            mid=partition(R,low,high);//对原序列进行分解，找到基准位置
            quickSort(R,low,mid-1);//左区间递归快速排序
            quickSort(R,mid+1,high);//右区间递归快速排序
        }
    }

}