快速排序快速排序(Quicksort )是使用分治思想改进的冒泡排序，非常高效。 基本思想是，将排序的数据分割排序为独立的两个部分，其中一部分的所有数据都比另外一部分的所有数据都要小，用这种方法排序为对这两部分数据分别进行快速排序
一、递归(亦称基准元素) )。
二、实现思路，部分数据小于或等于透视元素，其他数据大于透视元素
三.选取一个枢轴元素
快速代码是专用语音语音quicksort (int [ ] arr，int start，int end )//递归结束条件if ) start=end ) { return； //在第一步中，添加分区后的透视，例如[ 2，1，3 ]，透视为2，分区后的透视后缀为1intpivotindex=partition(arr，start，end ) //步骤2，左部分数组按快速排序(arr，start，pivotIndex - 1 )排序； //步骤3，快速排序(arr，pivotIndex 1，end )按右侧数组排序}现在，快速列的主干代码已完成。 今后只要知道将数组分割成两部分，我们的代码就完全可以实现。 其实，这才是实现快速排队需要思考的中心问题
对分割的子数组递归地执行步骤一二，直到无法分割
这里有两种方法如何实现分区并返回枢轴元素的下标
如何实现分区并返回枢轴元素的下标？
选择第一个元素3作为透视元素，int pivot=a[0]； 此时，可能在下标为0的地方挖了一个洞【蓝色填充表示洞】； 为了给皮特留下深刻的印象，我在这里问一个简单的问题。 如何将数组中的元素a[3]放置在a[0]的位置而不丢失a[0]？ 那就是先保存a[0]。 可以定义并保存变量，然后可以将a[0]移动到其他位置。 什么方法都可以。 然后是a[0]=a[3]。 因此，此处挖掘枢轴元素的方法是定义保存枢轴元素的变量，而其他位置元素的挖掘方法是将该位置的元素移动到数组中的另一个位置，即孔所在的位置
定义两个指针，其中左箭头指向数组的左端，右箭头指向数组的右端
left用于从左向右扫描数组，查找大于pivot的元素
right用于从右向左扫描数组，查找小于pivot的元素
首先从右向左开始扫描，寻找比pivot小的数量，准备填补漏洞
left=0，right=6，此时将a[right]pivot，a[right]填充到a[left]中，将left向右移动
此时排列为
(问两个关于以上操作的问题：
1 .为什么要从右向左扫描
2 .为什么要将left向右移动)
这时，right指向了新的洞
改变扫描方向，从左向右扫描，寻找大于pivot的数量准备填孔
left=1，right=6，a[left]pivot，不满足条件，left向右移动
left=2，right=6，a[left]pivot，满足条件，将a[left]嵌入a[right]，将right向左移动
此时排列为
此时，left指向新的孔
改变扫描方向，从右向左扫描，准备找比pivot小的数量填补漏洞
left=2，right=5，a[right]pivot，不满足条件，right向左移动
left=2，right=4，a[right]pivot，满足条件，将a[right]填入a[left]，将left向右移动
此时排列为
这时，right指向了新的洞
改变扫描方向，从左向右扫描，寻找大于pivot的数量准备填孔
left=3，right=4，a[left]pivot，满足条件，将a[left]嵌入a[right]，将right向左移动
此时排列为
此时，left=right，left和right同时指向的是新的凹坑
left和right相遇时，pivot进入了坑
此时排列为
此时，pivot的左边的数据都在pivot以下，pivot的右边的数据都大于pivot，完成了一次分区。 对于子序列分区也同样，可以重复上述步骤
挖坑填数
1、以a[0]=3为基准
元素，将基准元素保存起来，此时相当于在a[0]挖了个坑。int pivot = a[0];2、定义两个扫描指针（引用），left指向数组左端，right指向数组右端
3、right从右往左扫描，如果a[right]<pivot，将a[right]填入a[0]并右移left，此时a[right]变成一个坑
如果a[right]>pivot，right继续左移，直到找到比基准元素小的数
4、left从左往右扫描，如果a[left]>pivot，将a[left]填入a[right]坑中并左移right，此时a[left]变成一个坑
如果a[left]<pivot，left继续右移，直到找到比基准元素大的数
5、当left=right，扫描完成
6、将基准元素填入坑中，此时基准元素左边的数全部小于基准元素，基准元素右边的数全部大于基准元素，分区完成
③ 代码实现 private static int partition(int[] arr, int start, int end) { // 确定枢轴元素 int pivot = arr[start]; // 定义两个指针（引用），一个指向数组左端，一个指向数组右端 int left = start; int right = end; while (left < right) { // 从右往左扫描，寻找比枢轴元素小的，并填入坑中 while (left < right && arr[right] >= pivot) { right--; } if (left < right) { arr[left++] = arr[right]; } // 从左往右扫描，寻找比枢轴元素大的，并填入新坑中 while (left < right && arr[left] < pivot) { left++; } if (left < right) { arr[right--] = arr[left]; } } // 扫描完成后,将枢轴元素填入新坑中 arr[left] = pivot; return left; }
左右指针
① 图解分析
选取第一个元素为枢轴元素 int pivot=3
定义两个指针（引用）
left从左往右扫描，寻找大于pivot的数，left不必扫描pivot
right从右往左扫描，寻找小于等于pivot的数
先从左往右扫描，直到a[left]>pivot
再从右往左扫描，直到a[right]<=pivot
交换a[left]和a[right]
此时，a[left]>pivot，a[right]<pivot，交换a[left]和a[right]
数组变为
继续扫描
此时，a[left]>pivot，a[right]<pivot，交换a[left]和a[right]
数组变为
继续从左往右扫描l eft=4，a[left]>pivot，满足条件，停止扫描
从右往左扫描，right=3，a[right]<pivot，满足条件，停止扫描
此时left>right，不做交换，退出扫描
交换枢轴元素和a[right]
此时pivot左边的数全部小于等于pivot，pivot右边的数全部大于pivot，一趟分区完成，对于子序列分区也是如此，重复上述步骤即可
② 思路总结
③ 代码实现
private static int partition(int[] arr, int start, int end) { // 枢轴元素 int pivot = arr[start]; // 左指针，用于从左往右扫描元素 int left = start + 1; // 右指针，用于从右往左扫描元素 int right = end; while (true) { // 从左往右扫描，寻找比枢轴大的元素 while (arr[left] <= pivot) { left++; // 防止越界 if (left == end) break; } // 从右往左扫描，寻找比枢轴小的元素 while (arr[right] > pivot) { right--; if (right == start) break; } if (left >= right) break; // 如果left<right, 交换a[left]和a[right] swap(arr, left, right); } // 交换轴枢和right所在位置元素 swap(arr, start, right); return right; } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } 总结以上快速排序的实现，还有很大的优化空间
比如，基准元素的选择
比如，当序列较短时，使用插入排序更高效
由于时间的关系，本篇暂告一段落
白话经典算法系列之六 快速排序 快速搞定
快速排序(三种算法实现和非递归实现)
百度百科