本章内容
快速排序
快速排序核心思想：
1）选取一个基准元素（pivot），一般选择第一个元素或者最后一个元素。
2）从数列的左右两端开始向中间扫描，设两个指针left和right，其中left指向数列的左端，right指向数列的右端。
3）比较基准元素和left所指向的元素，如果left所指向的元素小于基准元素，则left右移一位；否则停止移动。
4）比较基准元素和right所指向的元素，如果right所指向的元素大于基准元素，则j左移一位；否则停止移动。
5）如果left和right都停止移动，则交换left和right所指向的元素。
6）重复步骤3到步骤5，直到left和right相遇。
7）将基准元素与left所指向的元素交换。
8）递归地对左右两个子序列进行快速排序。
注意事项：
1）如果选取数列的第一个元素为基准元素，则从right所指向的元素开始与基准元素进行比较；如果选取数列的最后一个元素为基准元素，则从left所指向的元素开始与基准元素进行比较。
2）如果选取数列的第一个元素为基准元素，left所指向的元素与基准元素第一次对比时，left下标与基准元素下标相等（即：判断条件中添加等号）；如果选取数列的最后一个元素为基准元素，right所指向的元素与基准元素第一次对比时，right下标与基准元素下标相等。
快速排序图文演示
将一个无序数列3、7、8、1、5、2、6、4按从小到大的顺序进行排序。按照快速排序的思想，先选取一个基准元素，以数列的第一个元素3为例。
如图所示：
1）选取数列的第一个元素3为基准元素，从数列的右指针开始，比较右指针指向的元素4与基准元素3，4>3，因此右指针向左移动一位。
如图所示：
2）比较右指针指向的元素6与基准元素3，6>3，因此右指针继续向左移动一位。
如图所示：
3）比较右指针指向的元素2与基准元素3，2<3，右指针停止移动；比较左指针指向的元素3与基准元素3，3=3，因此左指针向右移动一位。
如图所示：
4）比较左指针指向的元素7与基准元素3，7>3，左指针停止移动，交换左右指针指向的元素（即：元素7与元素2交换位置）。
如图所示：
5）比较右指针指向的元素7与基准元素3，7>3，因此右指针向左移动一位，以此类推，直到左右指针重合。
如图所示：
6）注意：左右指针在元素1处重合，期间元素1和元素8通过对比基准元素交换了位置。此时，交换基准元素3与左指针（右指针也可以，因为左右指针已经指向同一个位置）指向的元素1的位置，并返回基准点（即：基准元素所在下标p=2），第一轮排序结束。
如图所示：
此时，小于基准元素3的元素（1，2）在基准元素左边，大于基准元素3的元素（8，5，7，6，4）在基准元素右边，继续对左右两边的元素进行递归排序，最终得到完整排序后的有序数列。
其中：
pivot：选取的基准元素（图中为待排序数列的第一个元素）
p：基准元素所在下标。
left：待排序数列左指针。
right：待排序数列右指针。
快速排序代码实现
/** * @author 南秋同学 * 快速排序算法 */public class QuickSort { /** * 快速排序 * @param a 待排序数组 * @param l 待排序数组left下标 * @param r 待排序数组right下标 */ public static void quickSort(int[] a, int l, int r){ // 终止条件 if(l >= r){ return ; } // 获取基准元素下标 int p = partition(a, l, r); // 递归排序左右分区 quickSort(a, l, p-1); quickSort(a, p+1, r); } /** * 获取每轮排序后基准点（即：基准元素在数组中的位置） * @param a 待排序数组 * @param l 待排序数组left下标 * @param r 待排序数组right下标 * @return 每轮排序后基准点 */ private static int partition(int[] a, int l, int r){ // 选取基准元素，此处为数列的第一个元素 int p = a[l]; // 设置左右指针left和right int left = l; int right = r; while (left < right){ // 比较基准元素和right所指向的元素，如果right所指向的元素大于基准元素，则j左移一位；否则停止移动。 while (left < right && a[right] > p){ right--; } // 比较基准元素和left所指向的元素，如果left所指向的元素小于基准元素，则left右移一位；否则停止移动。 // 特别注意：由于选取数列的第一个元素为基准元素，判断时left所指向的元素时可以等于基准元素。 while (left < right && a[left] <= p){ left++; } // 交换left和right所指向的元素。 swap(a, left, right); } // 将基准元素与left所指向的元素交换。 swap(a,l,left); System.out.println(Arrays.toString(a) + " 排序后，基准元素["+p+"]在数列中的下标为：" + left); return left; } /** * 交换left和right所指向的元素 * @param a 待排序数组 * @param left 元素下标 * @param right 元素下标 */ public static void swap(int[] a,int left,int right){ int t=a[left]; a[left]=a[right]; a[right]=t; } public static void main(String[] args) { int[] a = {3,7,8,1,5,2,6,4}; System.out.println("待排序数组："+Arrays.toString(a)); QuickSort.quickSort(a, 0, a.length-1); }}快速排序复杂度
快速排序是一种原地、不稳定的排序算法，时间复杂度一般为 O(nlogn) ，最坏退化成O(n2)（如：原来数组已经有序，快速排序的时间复杂度就退化成O(n2)）。
【作者简介】
一枚热爱技术和生活的老贝比，专注于Java领域，关注【南秋同学】带你一起学习成长～
