八大排序-快速排序（搞定面试之手写快排）「建议收藏」

概要

快速排序由C. A. R. Hoare在1960年提出，是八大排序算法中最常用的经典排序算法之一。其广泛应用的主要原因是高效，核心算法思想是分而治之。快速排序经常会被作为面试题进行考察，通常的考察思路是快排思想、编码实践之手写快排以及进一步对快排的优化。事实上在Java标准库中Arrays类的sort方法里源码也正是使用了优化后的快速排序（具体源码以及优化分析后续会推文讲解），掌握快排算法对于数据结构与算法入门极为重要。

原理

快速排序的核心思想是分治：选择数组中某个数作为基数，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数都比基数小，另外一部分的所有数都都比基数大，然后再按此方法对这两部分数据分别进行快速排序，循环递归，最终使整个数组变成有序。

基数选择

由于快速排序需要选定一个基数进行划分排序，关于基数选择有很多方式，而基数选择直接关系到快排的效率。事实上，选取基准元素应该遵循平衡子问题的原则：即使得划分后的两个子序列的长度尽量相同本篇以待排序数组首元素作为基数进行说明。本篇以最常见的使用数组首元素作为基数进行快速排序原理说明。

一趟排序

以数组int n[] = { 6, 5, 2, 7, 3, 9, 8, 4, 10, 1 }为例：

八大排序-快速排序（搞定面试之手写快排）「建议收藏」_https://bianchenghao6.com/blog_编程文档_第1张

以第一个数字6作为基数，使用双指针i,j进行双向遍历：

1、i从左往右寻找第一位大于基数（6）的数字，j从右往左寻找第一位小于基数（6）的数字；
2、找到后将两个数字进行交换。继续循环交换直到i>=j结束循环；
3、最终指针i=j,此时交换基数和i(j)指向的数字即可将数组划分为小于基数（6）/基数（6）/大于基数（6）的三部分，即完成一趟快排；

伪代码

见编码注释

编码实践

public class Test {

	public static void main(String[] args) {
		int n[] = { 6, 5, 2, 7, 3, 9, 8, 4, 10, 1 };
		quicksort(n);
		System.out.print("快排结果：");
		for (int m : n) {
			System.out.print(m + " ");
		}
	}

	public static void quicksort(int n[]) {
		sort(n, 0, n.length - 1);
	}

	public static void sort(int n[], int l, int r) {
		if (l < r) {
			// 一趟快排，并返回交换后基数的下标
			int index = patition(n, l, r);
			// 递归排序基数左边的数组
			sort(n, l, index - 1);
			// 递归排序基数右边的数组
			sort(n, index + 1, r);
		}

	}

	public static int patition(int n[], int l, int r) {
		// p为基数，即待排序数组的第一个数
		int p = n[l];
		int i = l;
		int j = r;
		while (i < j) {
			// 从右往左找第一个小于基数的数
			while (n[j] >= p && i < j) {
				j--;
			}
			// 从左往右找第一个大于基数的数
			while (n[i] <= p && i < j) {
				i++;
			}
			// 找到后交换两个数
			swap(n, i, j);
		}
		// 使划分好的数分布在基数两侧
		swap(n, l, i);
		return i;
	}

	private static void swap(int n[], int i, int j) {
		int temp = n[i];
		n[i] = n[j];
		n[j] = temp;
	}

}