快速排序是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。
基本思想：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，递归这个过程，最终完成排序。
算法描述：
以升序为例。以最左边的数为基准数。设置左右两个指针，左指针初始位置为数组下标1位置，右指针初始位置为数组最大下标位置。
首先，右指针逐步向左移，直至找到一个比基准数小的数，赋值到左指针所指为位置，
然后，左指针逐步向右移，直至找到一个比基准数大的数，赋值到右指针所指为位置，
重复上述步骤，直至左、右指针位置重合，
将此位置上的数字与基准数交换，
至此，本轮完成，基准数归位。
对基准数左右两边的数，分别进行上述步骤，递归进行，完成排序。
过程如下图所示：
Java代码实现：
1 /** 2 * 用快速排序算法对整型数组进行升序排序 3 * 4 * @param arr：待排序数组 5 */ 6 private static void quickSort(int[] arr) { 7 if (arr == null || arr.length <= 1) 8 return; 9 _quickSort(arr, 0, arr.length - 1);10 }11 12 /**13 * 快速排序算法的实现14 *15 * @param arr：待排序数组16 * @param left：数组下标下界17 * @param right：数组下标上界18 */19 private static void _quickSort(int[] arr, int left, int right) {20 if (left < right) {21 int mid = getMid(arr, left, right);22 //分治、递归23 _quickSort(arr, left, mid - 1);24 _quickSort(arr, mid + 1, right);25 }26 }27 28 /**29 * 快速排序算法的一轮排序过程30 *31 * @param arr：待排序数组32 * @param low：左指针初始位置33 * @param high：右指针初始位置34 * @return 基准数归位后的位置35 */36 private static int getMid(int[] arr, int low, int high) {37 int key = arr[low];38 while (low < high) {39 //右指针向左遍历40 while (low < high && arr[high] > key)41 high--;42 arr[low] = arr[high];43 //左指针向右遍历44 while (low < high && arr[low] < key)45 low++;46 arr[high] = arr[low];47 }48 //基准数归位49 arr[low] = key;50 return low;51 }
特点：
1. 相对于冒泡排序，快速排序过程的比较和交换和是跳跃式的，因些总的比较和交换次数会变少。其平均时间复杂度是O(NlogN)，最坏情况下的时间复杂度为冒泡排序一样，为O(N2)。
2. 由于快速排序的交换基于基准数，如果待排序数组存在相同大小元素，过程中有可能会改变相同大小元素的顺序，因此快速排序是一种不稳定的排序算法。
3. 快速排序基于递归进行，因此会大量占用栈空间。
优化：
对基准位置的选取，有3种方式：固定切分、随机切分和三数取中切分。上述采取的是固定切分方式，其效率并不理想。随机切分也较常用，效率稍高。最理想的是三数取中切分方式。
下面是三数取中切分方式的代码：
1 /** 2 * 快速排序算法的一轮排序过程 3 * 4 * @param arr：待排序数组 5 * @param low：左指针初始位置 6 * @param high：右指针初始位置 7 * @return 基准数归位后的位置 8 */ 9 private static int getMid(int[] arr, int low, int high) {10 int key = getKey(arr, low, high); //基准数11 while (low < high) {12 //右指针向左遍历13 while (low < high && arr[high] > key)14 high--;15 arr[low] = arr[high];16 //左指针向右遍历17 while (low < high && arr[low] < key)18 low++;19 arr[high] = arr[low];20 }21 //基准数归位22 arr[low] = key;23 return low;24 }25 26 /**27 * 三数取中方式获取基准数28 *29 * @param arr：待排序数组30 * @param low：左指针初始位置31 * @param high：右指针初始位置32 * @return 基准数33 */34 private static int getKey(int[] arr, int low, int high) {35 int mid = (high - low) / 2 + low;36 if (arr[mid] > arr[high]) {37 int temp = arr[mid];38 arr[mid] = arr[high];39 arr[high] = temp;40 }41 if (arr[low] > arr[high]) {42 int temp = arr[low];43 arr[low] = arr[high];44 arr[high] = temp;45 }46 if (arr[mid] > arr[low]) {47 int temp = arr[low];48 arr[low] = arr[mid];49 arr[mid] = temp;50 }51 return arr[low];52 }