【十大编程算法】算法一：快速排序算法
技术文章第一时间送达！
昨天排版出了问题，今天重新发一下。
自己最近的一些感想，英语+算法这两个知识也是很重要的，以前总是听别人说这些都不重要，还觉得挺有道理。现在谁要是再和我说不重要，可能会想打死他了，当然是玩笑
。
所以现在也在学习英语+算法方面的知识，这些东西可能在短时间看不到显著的成效，不过越往后面，对你的帮助会越来越大。除非，你一直都想当个菜鸟。
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 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;所有基准数右边的数组，同理，也以此类推进行排序。
递归调用来实现快速排序算法
排序结果
思考一个问题，为什么要先从右边开始查找呢？
参考这篇文章：快速排序法为什么一定要从右边开始的原因
有写得不好的地方，可以后台告诉我。
如果觉得文章不错，随手点赞转发，每周都会为你带来算法知识。