【十大编程算法】算法一：快速排序算法

Myth丶恋晨 2022-04-04 03:07 173阅读 0赞

# 快速排序算法 #

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序是对冒泡排序的改进，它使用分治法的思想，每次循环根据指定的基准数，将其他元素分别放置其左右（升序排序，大的放右小的放左），第二次循环，以基准数为中心，分为左右两部分，每部分再通过新的基准数排序…（下边来个小例子解释）。

快速排序和冒泡排序对比：如果遇到排序问题，尽量用快速排序，它比冒泡排序，不仅逼格高，效率还杠杠的。

**基准数**：一般指定第一个元素或最后一个元素为基准数（任意元素都可以作为基准数）。

**来个小例子： **  
对一个int型数组升序排序（第一个位置为基准数），两个指针分别指向数组头尾：

int[] nums = {66, 13, 51, 76, 81, 26, 57, 69, 23};
    int first = 0;
    int last = 8;
    int index = nums[0];

**1、第一次循环**

第一次循环的时候，first指向nums\[0\]的位置，last指向nums\[8\]的位置，基准数指定数组的第一个位置。

首先从右开始向左查找，找出第一个比基准数小或者等于它的数，last指向 nums\[8\] = 23，找到后这个数之后，停下来。

之后从左开始往右查找，找出第一个比基准数大或者等于它的数，first指向 nums\[3\] = 76，找到后这个数之后，停下来。

交换 nums\[3\] 和 nums\[8\] 俩的值进行交换，注意：first 必须 小于 last才可以

int[] nums = {66, 13, 51, 23, 81, 26, 57, 69, 76};
    int first = 3;
    int last = 8;

我们进行下一次循环，last继续往左查找，指向 nums\[6\] = 57，找到之后，停下来。

first继续往右查找，指向 nums\[4\] = 81，找到之后，停下来。

我们对他们进行交换，交换之后各个变量的值为

int[] nums = {66, 13, 51, 23, 57, 26, 81, 69, 76};
    int first = 4;
    int last = 6;

在进行下一次循环，last继续往左查找，指向 nums\[5\] = 26，first继续往右查找，指向 nums\[5\] = 26

这里需要注意，当last == first的之后，我们交换 基准数 与 nums\[5\]

int[] nums = {26, 13, 51, 23, 57, 66, 81, 69, 76};
    int first = 5;
    int last = 5;

至此，基准数左边的数都小于它，基准数右边的数都大于它。

第一次循环结束

**2、第二次循环**

先在基准数左边的数和左边的数是未排序好的，以基准数为线，可以将nums数组划分为两个数组

int[] nums = {26, 13, 51, 23, 57};
    int[] nums = {81, 69, 76};

分别是0到i-1的数组，j+1到nums.length-1的数组，第二次循环，先将基准数左边的数排序好

int[] nums = {26, 13, 51, 23, 57};
    int first = 0;
    int last = 4;

基准数为26，first和last分别是0和数组长度减1，进行第一次循环的步骤，从右往左找出小于该基准数的数，从左往右找出大于该基准数的数，交换它们的位置，直至first == last。

//基准数
    int index = 26;
    
    //第一次交换
    int[] nums = {26, 13, 23, 51, 57};
    int first = 2;
    int last = 3;
    
    //第二次不交换   
    int[] nums = {26, 13, 23, 51, 57};
    int first = 2;
    int last = 2;

第二次是不交换的，因为查找的时候，first 必须还要满足 小于 last的条件才查找，否则就不进行查找。

所以这里last查找一次之后，first == last 了，first 将不小于 last，所以从左往右就不进行查找操作，它俩相等之后，交换基准数和nums\[first\]的位置

int[] nums = {23, 13, 26, 51, 57};
    int first = 2;
    int last = 2;

然后结束这一轮循环，得到新的数组，同时因为first == last，所以结束这一轮排序。

看到这里，是不是数组很眼熟呢，没错，基准数26左边的数都小于它，基准数26右边的数都大于它，但是左边的数还没有排序好，再次重复之前的操作，以基准数为界线，再次将数组划分为两个数组

int[] nums = {23, 13};
    int[] nums = {51, 57};

再次进行排序

**3、第三次排序**

基准数：23

first = 0

last = 1

第一次查找得到 first指向 num\[1\] = 13，last指向 num\[0\] = 23，满足first < last，所以进行交换

int[] nums = {13, 23};
    int first = 0;
    int last = 1;

所有基准数右边的数组，同理，也以此类推进行排序。

**递归调用来实现快速排序算法**

/**
     * @author: LKP
     * @date: 2018/12/14
     */
    public class quickSortAlgorithm {
    
        private static int[] nums = {66, 13, 51, 76, 81, 26, 57, 69, 23};
    
        public static void quickSort(int[] nums, int first, int last) {
            //递归退出条件
            if (first > last) {
                return;
            }
            
            int i = first;
            int j = last;
            int index = nums[first];
    
            while (i != j) {
                while (nums[j] >= index && j > i) {
                    j--;
                }
                while (nums[i] <= index && i < j) {
                    i++;
                }
                if (i < j) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
    
            if (i == j) {
                nums[first] = nums[i];
                nums[i] = index;
            }
    
            quickSort(nums, first, i - 1);
            quickSort(nums, i + 1, last);
    
        }
    
        public static void main(String[] args) {
            quickSort(nums, 0, nums.length - 1);
            for (int num : nums) {
                System.out.print(num + "\t");
            }
        }
    
    }

排序结果为：

![20181214193447344.png][]

思考一个问题，为什么要先从右边开始查找呢？

参考这篇文章：[快速排序法为什么一定要从右边开始的原因][Link 1]

[20181214193447344.png]: /images/20220404/737e322cc04c4cbfab130a13b7129627.png
[Link 1]: https://blog.csdn.net/lkp1603645756/article/details/85008715