基本思想 通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序。 用到了分治和递归的思想。 代码
public class QuickSort { public static void quickSort(int[] arr, int low, int high) { if (low < high) { int middle = getMiddle(arr, low, high); // 将数组进行一分为二 quickSort(arr, low, middle - 1); // 对低字表进行递归排序 quickSort(arr, middle + 1, high); // 对高字表进行递归排序 } } public static int getMiddle(int[] arr, int low, int high) { int tmp = arr[low]; // 数组的第一个作为中轴 while (low < high) { while (low < high && arr[high] > tmp) { high--; } arr[low] = arr[high]; // 比中轴小的记录移到低端 while (low < high && arr[low] < tmp) { low++; } arr[high] = arr[low]; // 比中轴大的记录移到高端 } arr[low] = tmp; // 中轴记录到尾 return low; // 返回中轴的位置 } public static void quickSort(int[] arr) { quickSort(arr, 0, arr.length - 1);//选第一个元素为基准 } public static void main(String[] args) { int[] a = new int[] { 49, 38, 65, 97, 76, 13, 27, 50 }; quickSort(a); for (int i : a) System.out.print(i + " "); } }时间复杂度 O(n)——-最好 O(nlog2n)-平均 O(n^2)—-最坏
