疾速排序三个步骤：
- 抉择基准值：在待排序列中，依照某种形式挑出一个元素，作为基准值。
- 宰割操作：以该基准值在序列中的理论地位，把序列分成两个子序列，一边是比它大的值，另外一边是比它小的值。
- 递归：对两个子序列进行快排，直到序列为空或者只有一个元素。
代码实现
package sort;import java.util.Arrays;public class QuickSort { public static void quickSort(int[] arr, int left, int right){ // 递归的进口：只剩下一个元素的时候 if (left >= right){ return; } int pivot = arr[left]; int i = left, j = right; while (i < j) { // 这里如果pivot 选在左侧，就要先从右侧开始遍历，反之则先从左侧开始 // 小于等于来解决反复的元素 while (arr[j] >= pivot && i < j){ j--; } // 找到比基准小的数换到左侧 arr[i] = arr[j]; while (arr[i] <= pivot && i < j) { i++; } // 找到比基准大的数换到右侧去 arr[j] = arr[i]; } // 最初将基准放到两头地位 arr[i] = pivot; // 递归快排左侧数列 quickSort(arr, left, i - 1); // 递归遍历右侧数列 quickSort(arr, i + 1, right); } public static void main(String[] args) { int[] arr = {7,3,2,1,6,4,5,6}; int left = 0; int right = arr.length - 1; quickSort(arr, left, right); System.out.println(Arrays.toString(arr)); }}工夫复杂度
对n个元素进行疾速排序的过程形成一棵递归树，在这样的递归树中，每一层最多对n个元素进行划分，所花的工夫为O(n)。当初始排序数据随机散布，使每次分成的两个子区间中的元素个数大抵相等时，递归树高度为log2n，疾速排序出现最好状况，即最好状况下的工夫复杂度为O(nlog2n)。疾速排序算法的均匀工夫复杂度也是O(nlog2n)。所以疾速排序是一种高效的算法。
最坏状况为，每一轮分不成两组，每一轮都只能把基准值索引放到第一个或者最初一个，因而一共须要n轮。
因而，最坏工夫复杂度为O(n^2)。