（数组）8. 快速排序

题解思路

快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。

实现代码

public static void quickSort(int[] array) { int len = array.length; if(array == null || len == 0 || len == 1) { return ; } sort(array, 0, len - 1); } /** * 快排核心算法，递归实现 * @param array * @param left * @param right */ public static void sort(int[] array, int left, int right) { if(left > right) { return; } // base中存放基准数 int base = array[left]; int i = left, j = right; while(i != j) { // 顺序很重要，先从右边开始往左找，直到找到比base值小的数 while(array[j] >= base && i < j) { j--; } // 再从左往右边找，直到找到比base值大的数 while(array[i] <= base && i < j) { i++; } // 上面的循环结束表示找到了位置或者(i>=j)了，交换两个数在数组中的位置 if(i < j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } // 将基准数放到中间的位置（基准数归位） array[left] = array[i]; array[i] = base; // 递归，继续向基准的左右两边执行和上面同样的操作 // i的索引处为上面已确定好的基准值的位置，无需再处理 sort(array, left, i - 1); sort(array, i + 1, right); }