平均时间复杂度：
/** * 快速排序(标准版) * * @param arr * @return */ public static void quickSort(int[] arr) { quickSort(arr, 0, arr.length - 1); } public static void quickSort(int[] arr, int low, int high) { if (low >= high) { return; } // 找被比较的基数，将比基数小的数放到其前面，基数大的数放到其后面 int part = partition(arr, low, high); // 给基数左边的数快排 quickSort(arr, low, part - 1); // 给基数右边的数快排 quickSort(arr, part + 1, high); } // 找被比较的基数，将比基数小的数放到其前面，基数大的数放到其后面 public static int partition(int[] arr, int low, int high) { // 比较的基数，默认是第一个数 int leader = arr[low]; while (low < high) { // 当右边的数大于基数时，不改变数组，high-- while (low < high && arr[high] >= leader) { high--; } // 否则 将high位置的数放到low处 arr[low] = arr[high]; // 当左边的数小于基数时，不改变数组，low++ while (low < high && arr[low] <= leader) { low++; } // 否则 将low位置的数放到high处 arr[high] = arr[low]; } arr[low] = leader; return low; }