前言
冒泡排序解决了桶排序浪费空间的问题，但在算法的执行效率上却牺牲了很多，它的时间复杂度达到了O(N2)。假如我们的计算机每秒钟可以运行10 亿次，那么对1 亿个数进行排序，桶排序只需要0.1 秒，而冒泡排序则需要1 千万秒，达到115 天之久，是不是很吓人？那有没有既不浪费空间又可以快 一点的排序算法呢？那就是“快速排序”啦！
快排思想
在数序列中找一个数作为基准数（一般为第一个数），经过比较调整，将所有小于基准数的数放在基准数左边，将所有大于基准数的数放在基准数放在右边。然后分别递归基准数左边和右边的序列。 如下图：
Java代码实现
public class QuickSort {
public static void main(String[] args) {
System.out.println(
"输入排序的个数n：");
Scanner input =
new Scanner(System.in);
int n = input.nextInt();
int array[] =
new int[n];
System.out.println(
"请输入要排序的数字：");
for (
int i =
0; i < n; i++) {
array[i] = input.nextInt();
}
System.out.println(
"排序结果为：");
quick(array,
0, n -
1);
for (
int i =
0; i < n; i++) {
System.out.print(array[i] +
" ");
}
}
public static void quick(
int array[],
int left,
int right) {
if (left >= right) {
return;
}
int temp = array[left];
int i = left;
int j = right;
while (i != j) {
while (array[j] >= temp && i < j) j--;
while (array[i] <= temp && i < j) i++;
if (i < j) {
int t = array[i];
array[i] = array[j];
array[j] = t;
}
}
array[left] = array[i];
array[i] = temp;
quick(array, left, i -
1);
quick(array, i +
1, right);
}
}
复杂度
快速排序之所以比较快，是因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进行交换，交换的距离就大得多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的，都是O(N2)，它的平均时间复杂度为O (NlogN)。
