排序算法之快速排序

前言

快速排序可谓是我们老生常谈的话题了，如果要让大家说出他的原理可能大家都能叙述出来，而要手写出来可能就要花费一定的时间了。

今天我就来谈一谈我对快速排序的理解，以及快速排序的模板。

大家不要知其然而不知其所以然。

快速排序概述

快速排序是根据多次的比较并交换来实现的

先找到一个哨兵（基准元素），一般选择第一个，然后将比哨兵大的元素放在他的右边，将比哨兵小的元素放在他的左边
然后哨兵左边右边就形成了两个独立的数组，我们再按照这个思想来排序，直到剩下最后一个元素为止
很明显这是一个递归调用，通过递归排序左边，然后再通过递归排序右边，到最后如果左边和右边都排序完成，排序也就完成了

快速排序图文讲解

快速排序1.png

这里指定第一个元素为哨兵（基准元素），然后定义两个指针，分别指向数组头和数组尾快速排序2.png

先从后往前找，找到第一个比哨兵（基准元素）小的

再从前往后找，找到第一个比哨兵（基准元素）大的

因为我们是从小到大排序，如果想要从大到小排序，反过来即可快速排序3.png

找到之后交换它们

快速排序4.png

因为此时左指针和右指针还没有重合，循环要继续下去，我们继续按照上面那个步骤继续寻找元素

先从后往前找，找到第一个比哨兵（基准元素）小的元素

再从前往后找，这个时候，我们发现左右指针重合了我们也没有成功找到该元素，此时应该终止循环

快速排序5.png 交换哨兵（基准元素）和左右指针重合的那个元素

快速排序6.png

我们此时可以发现哨兵的左右已经被我们分割好了，左边是比哨兵小的，右边是比哨兵大的，后面的我就不在赘述。

接下来我们来实现代码

快速排序代码实现

这里我使用Java来实现快速排序

我们先封装一个交换函数，方便我们来交换。

private static void swap(int[] nums,int i ,int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

因为快排使用的是递归的思想，一般我在写递归函数的时候，会想到递归三要素，这里的递归三要素是我自己总结的，分别是：确定递归函数的参数和返回值、确定终止条件、确定单层逻辑

我们按照这个思想来确定快排的实现

确定递归函数的参数和返回值

返回值应该是不需要的，因为我们直接修改的是数组内部的元素顺序，我们只需要将该数组传过来就可以了，根据上面的我们还需要两个指针，左指针和右指针，这样我们很容易得出了参数。

private static void sort(int[] nums, int left, int right) {       

}

确定终止条件

在终止条件这一方面，我们上面也已经说过了，当元素仅仅剩下一个的时候我们的排序就算完成了，那我们很容易想到。

if(left >= right)return;

确定单层逻辑

而单层逻辑是快排比较重要的一环了，我们知道，先确定一个哨兵（一般选择数组第一个元素），然后将比哨兵大的元素放在哨兵右边，将比哨兵小的元素放在哨兵左边，然后递归调用该函数即可。

这个思想我们知道了我们实现过程中该怎么来呢？

我们肯定要先完成确定哨兵元素然后移动比哨兵大的元素和比哨兵小的元素，这里我封装了一个函数来完成，我们先来看代码

private static int help(int[] nums, int left, int right) {
//这里我同样选择第一个元素为哨兵元素
    int i = left;//左指针
    int j = right;//右指针
    while(i < j){
    //先从后往前遍历，当遇到的元素比哨兵大的时候j--
        while(i < j && nums[j] >= nums[left])j--;
    //再从前往后遍历，当遇到的元素比哨兵元素小的时候i++
        while(i < j && nums[i] <= nums[left])i++;
    //交换左指针和右指针的值，如果i仍然小于j就继续循环
        swap(nums, i, j);
    }
    //此时i已经和j重合，我们交换i和哨兵元素的值
    swap(nums, i, left);
    //最后返回i即为我们所需
    return i;
}

这样我们就能确定哨兵元素了，接下来我们还需要递归调用，因为，help()函数为我们返回了哨兵的索引，很容易我们就能想到。

sort(nums, left, index - 1);
sort(nums, index + 1, right);

然后我们的快速排序就完成了，我们来看看整合到一起的代码吧！

最终代码

private static void sort(int[] nums, int left, int right) {       
    if(left >= right)return;
    int index = help(nums,left,right);
    sort(nums, left, index - 1);
    sort(nums, index + 1, right);
}
private static int help(int[] nums, int left, int right) {
    int i = left;
    int j = right;
    while(i < j){
        while(i < j && nums[j] >= nums[left])j--;
        while(i < j && nums[i] <= nums[left])i++;
        swap(nums, i, j);
    }
    swap(nums, i, left);
    return i;
}

private static void swap(int[] nums,int i ,int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

前言​

快速排序概述​

快速排序图文讲解​

快速排序代码实现​

确定递归函数的参数和返回值​

确定终止条件​

确定单层逻辑​

最终代码​

前言