-
介绍
快速排序又称分割交换排序法，是目前公认最佳的排序法。它的原理和冒泡排序法一样都是用交换的方式，不过它会现在数据中找到一个虚拟的中间值，把小于中间值的数据放在左边，而大于中间值的数据放在右边，再以同样的方式分别处理左右两边的数据，直到完成为止。 -
演示
代码如下：
private static void quickSort(int arr[], int low, int high) {
int l = low, h = high, povit = arr[low], tmp;
while (l < h) {
while (l < h && arr[h] >= povit) h--;
if (l < h) {
tmp = arr[h];
arr[h] = arr[l];
arr[l] = tmp;
l++;
}
while (l < h && arr[l] <= povit) l++;
if (l < h) {
tmp = arr[h];
arr[h] = arr[l];
arr[l] = tmp;
h--;
}
}
if (l > low) quickSort(arr, low, l - 1);
if (h < high) quickSort(arr, l + 1, high);
}
运行效果：
快速排序运行效果.png
- 分析
- 在最快及平均情况下，时间复杂度为O(nlog底数为2 的n)。最坏情况就是每次挑中的中间值不是最大就是最小，起时间复杂度为O(n²)；
- 不是稳定排序法；
- 在最差的情况下，空间复杂度为O(n)，而最佳情况为O(log以2为底的n)；
