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

技术文章第一时间送达！

昨天排版出了问题，今天重新发一下。

自己最近的一些感想，英语+算法这两个知识也是很重要的，以前总是听别人说这些都不重要，还觉得挺有道理。现在谁要是再和我说不重要，可能会想打死他了，当然是玩笑

。

所以现在也在学习英语+算法方面的知识，这些东西可能在短时间看不到显著的成效，不过越往后面，对你的帮助会越来越大。除非，你一直都想当个菜鸟。

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 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;

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

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

排序结果

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

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

有写得不好的地方，可以后台告诉我。

如果觉得文章不错，随手点赞转发，每周都会为你带来算法知识。