它的基本思想是：选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
package suanFa; public class QuickSort { /* * 快速排序 * * 参数说明： arr -- 待排序的数组 left -- 数组的左边界(例如，从起始位置开始排序，则left=0) right -- * 数组的右边界(例如，排序截至到数组末尾，则right=a.length-1) */ public static void quickSort(int[] arr, int left, int right) { if (left < right) { int i, j, x; i = left; j = right; x = arr[i]; while (i < j) { while (i < j && arr[j] > x) j--; // 从右向左找第一个小于x的数 if (i < j) arr[i++] = arr[j]; while (i < j && arr[i] < x) i++; // 从左向右找第一个大于x的数 if (i < j) arr[j--] = arr[i]; } arr[i] = x; quickSort(arr, left, i - 1); /* 递归调用 */ quickSort(arr, i + 1, right); /* 递归调用 */ } } public static void main(String[] args) { int arr[] = { 58, 48, 68, 38, 78, 28, 88, 18, 98 }; System.out.println("排序之前："); for (int i = 0; i < arr.length; i++) { System.out.printf(" " + arr[i] + " "); } System.out.println(""); // 调用函数 quickSort(arr, 0, arr.length - 1); System.out.println("排序之后："); for (int i = 0; i < arr.length; i++) { System.out.printf(" " + arr[i] + " "); } } } 排序之前： 58 48 68 38 78 28 88 18 98 排序之后： 18 28 38 48 58 68 78 88 98快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。
这句话很好理解：假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢？至少lg(N+1)次，最多N次。
