前言：
写到快速排序时，之前已经进行了冒泡、选择、插入排序，发现算法问题很多东西都是和实际问题相逆的，实际你可能会由外及里，由上及下，可是算法里面它有时就需要你由里往外去扩散，好比最里面的是小成果，然后一次次往外变化，成果也慢慢变大，最后直至达到最终成果为止。本篇快速排序方法因为调用了递归，你就可以逆着由里及外来思考问题。 写这篇文章光画图就花费了我2小时时间，越抽象就越不好形容和比喻，画的不好，希望各位不要吐槽。
快速排序：先快速排序将队列一分为二，然后对每个队列进行递归调用快速排序方法，直至不能再次分解后依次返回成果。
情景描述：
紧接情景，有一天，被同学称为大湿的体育老师胃疼请假休息了，真好数学老师闲着就来代课了，同样要排列队形，但是数学老师牛了，说同学们，我今天教你们一种快速排序的方法，到时候来了别忘了教你们的体育老师哦（体育老师估计胃更疼了...）
一、
- 我们就把第一个同学当做基数，其他同学和他进行比较，期间，基数不变，此时基数同学站出来，留下了个空位
- 首先从最后一个同学开开始，依次向前和基数进行比较，第一个比基数同学等高或者矮了，就站到基数的位置，自己的位置又空下了
- 步骤2后，我们再从第一位依次向后和基数比较，如果等于或者比基数高，就站到步骤二留下的空位，自己位置空出来
- 排除前后已经换过位置的同学，重复步骤2和3， 依次和基数比较，然后坐入空位，留下新空位
- 直到都和基数进行比较过，然后基数同学站到最后的空位里面
二、
- 通过步骤一我们把要排列的队分为了两队，而两队之内还是高低不齐的
- 首先来排前面的，让前面的队依旧以第一个为基数，结尾到分割线同学的前一位，执行步骤一
- 接着排后面的，以分割线同学的后一位为开始，队列末尾为结束，执行步骤一
- 重复执行步骤2和3，直至不能再拆分即排列完成
步骤一图解
上图为一轮快速排序方法
步骤二图解
上图为依次递归调用快速排序方法，对每次的新队列进行快速排序
代码片段
/** * 快速排序，返回一个中轴下标 * @param arr * @param low 队列起始下标 * @param high 队列结束下标 * @return */ public int quickSort(int[] arr, int low, int high) { int tmp = arr[low]; // 数组的第一个作为中轴 while (low < high) { while (low < high && arr[high] >= tmp) { high--; } arr[low] = arr[high]; // 比中轴小的记录移到低端 while (low < high && arr[low] <= tmp) { low++; } arr[high] = arr[low]; // 比中轴大的记录移到高端 } arr[low] = tmp; // 中轴记录到尾 return low; // 返回中轴的位置 } /** 递归调用快速排序方法，对数组进行排序 **/ public void _quickSort(int[] list, int low, int high) { if (low < high) { int middle = quickSort(list, low, high); // 获得中轴下标 // 对前部分进行排序，递归进行，此时不会执行后半部分，直至不能再次拆分，再依次执行下半部分 _quickSort(list, low, middle - 1); // 对下半部分进行排序 _quickSort(list, middle + 1, high); } } 代码挺少，但是没图的话理解起来太抽象了，还得边拿笔画着边执行着，完了才领悟了其原理。
再来严谨的总结下步骤：
- 设置两个变量i、j，排序开始的时候：i=0，j=N-1
- 从i开始向后搜索，即由前开始向后搜索（i ++ ），找到第一个大于key的A[i]，A[i]与A[j]交换
- 从j开始向前搜索，即由后开始向前搜索（j -- ），找到第一个小于key的值A[j]，A[i]与A[j]交换
- 从i开始向后搜索，即由前开始向后搜索（i ++ ），找到第一个大于key的A[i]，A[i]与A[j]交换
- 重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后令循环结束
优点：速度快，适合基本无序的队列
缺点：多个相同的值的相对位置也许会在算法结束时产生变动，所以不稳定，还有借用了递归思想，数据大量时消耗内存
终于写完了，洗洗睡了:) ，最后把这几天的排序整合下：
写作不易，难免有疏漏和错误，还请慷慨指正，不错请推荐
ps:欢迎转载，转载请注明出处：
每天多学一点点 代码少敲一点点