排序算法 - 快速排序 | 王洪博's blog

基本思想

1）选择一个基准元素,通常选择第一个元素或者最后一个元素,
2）如果选择第一个元素作为基准元素，则先从右向左找比基准元素小的元素，再从左向右找比基准元素大的元素，交换这两个元素的位置。（如果选择最后一个元素做基准元素，则先从左向右找）直到找到同一位置，跟基准元素位置交换，第一趟排序就结束。
3）通过一趟排序将记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。
4）此时基准元素在其排好序后的正确位置
5）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

算法流程图

$快速排序流程图$

快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。

代码如下

package main.java.com.study.sortingAalgorithm;

import main.java.com.study.utils.CommonUtils;

/**
 * @author: whb
 * @description: 快速排序
 */
public class QuickSort {

    /**
     * 快速排序的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
     * <p>
     * 一趟快速排序（或一次划分）的过程如下：首先任意选取一个记录（通常可选第一个记录）作为枢轴（或支点）（pivot），然后按下列原则重新排列其余记录：将所有关键字比它小的记录都安置在它的位置之前，将所有关键字比它大的记录都安置在它的位置之后。
     * <p>
     * 经过一趟快速排序之后，以该枢轴记录最后所落的位置i作分界线，将序列分割成两个子序列，之后再分别对分割所得的两个子序列进行快速排序。
     * <p>
     * 可以看出这个算法可以递归实现，可以用一个函数来实现划分，并返回分界位置。然后不断地这么分下去直到排序完成，可以看出函数的输入参数需要提供序列的首尾位置。
     */
    public static void quickSort(int[] numArr, int left, int right) {
        //不管使用哪种分割方式，都可以通过递归形式进行排序
        // 需要注意的是这个if语句不能少，不然没法停止，会导致堆栈溢出的异常。
        if (left < right) {
            //分割数组，找到分割点
            int point = partitionTwo(numArr, left, right);
            //递归调用，对左子数组进行快速排序
            quickSort(numArr, left, point - 1);
            //递归调用，对右子数组进行快速排序
            quickSort(numArr, point + 1, right);
        }
    }

    /**
     * 划分实现1 （枢轴跳来跳去法）
     * 一趟快速排序的实现：设两个指针left和right，设枢轴记录的关键字为first，则首先从right所指位置起向前搜索找到第一个关键字小于first的记录和枢轴记录互相交换，
     * 然后从left所指位置起向后搜索，找到第一个关键字大于first的记录和枢轴记录互相交换，重复这两步直至left==right为止。
     */
    public static int partitionOne(int[] numArr, int left, int right) {
        //用数组的第一个元素做基准元素
        int first = numArr[left];
        while (left < right) {
            while (left < right && numArr[right] >= first) {
                right--;
            }
            //交换
            swap(numArr, left, right);
            while (left < right && numArr[left] <= first) {
                left++;
            }
            //交换
            swap(numArr, left, right);
        }
        //返回分割点所在的位置
        return left;
    }

    /**
     * 划分实现2 （枢轴一次到位法）
     * partitionOne实现可以看出，枢轴元素（即最开始选的“中间”元素（其实往往是拿第一个元素作为“中间”元素））需要不断地和其他元素交换位置，而每交换一次位置实际上需要三次赋值操作。
     * <p>
     * 实际上，只有最后left=right的位置才是枢轴元素的最终位置，所以可以先将枢轴元素保存起来，排序过程中只作元素的单向移动，直至一趟排序结束后再将枢轴元素移至正确的位置上。
     *
     * @return
     */
    public static int partitionTwo(int[] numArr, int left, int right) {
        int first = numArr[left];
        int temp = numArr[left];
        while (left < right) {
            while (left < right && numArr[right] >= first) {
                right--;
            }
            numArr[left] = numArr[right];
            while (left < right && numArr[left] <= first) {
                left++;
            }
            numArr[right] = numArr[left];
        }
        numArr[left] = temp;
        return left;
    }

    /**
     * 交换数组中两个位置的元素
     */
    public static void swap(int[] numArr, int left, int right) {
        int temp = 0;
        if (numArr != null && numArr.length > 0) {
            temp = numArr[left];
            numArr[left] = numArr[right];
            numArr[right] = temp;
        }
    }

    public static void main(String[] args) {
        int[] numArr = {27, 11, 13, 45, 34, 22, 19, 8, 3, 99, 74, 55, 88, 66};
        System.out.println("**************快速排序******************");
        System.out.println("排序前：");
        CommonUtils.display(numArr);
        System.out.println("排序后：");
        quickSort(numArr, 0, numArr.length - 1);
        CommonUtils.display(numArr);
    }
}

CommonUtils工具类：

package main.java.com.study.utils;

/**
 * @author: whb
 * @description: 工具类
 */
public class CommonUtils {

    /**
     * 遍历打印
     *
     * @param numArr
     */
    public static void display(int[] numArr) {
        if (numArr != null && numArr.length > 0) {
            for (int num : numArr) {
                System.out.print(num + "  ");
            }
        }
        System.out.println("");
    }
}

测试结果

快速排序测试