快速排序的时间复杂度和稳定性

快速排序稳定性


快速排序是不稳定的算法，它不满足稳定算法的定义。
算法稳定性 — 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！

快速排序时间复杂度


快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。

这句话很好理解：假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢？至少lg(N+1)次，最多N次。
1. 为什么最少是lg(N+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。因此，快速排序的遍历次数最少是lg(N+1)次。
2. 为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是N次。

模板

取中点，复杂度会低一点

  1. void quick_sort(int[] q, int l ,int r) {
  2.         if (l >= r) return;
  3.         int x = q[l+r>>1], i = l - 1, j = r + 1;
  4.         while (i <j) {
  5.             do i++; while (q[i] < x);
  6.             do j--; while (q[j] > x);
  7.             if (i <j) {
  8.                 int t = q[i];
  9.                 q[i] = q[j];
  10.                 q[j] = t;
  11.             }
  12.         }
  13.         quick_sort(q, l , j);
  14.         quick_sort(q, j + 1, r);
  15.     }

思想

快排主要是分治的思想，这点体现在他的递归调用上。

  1. 首先==确定一个分界值 x ==，这个 x 可以是最左边(q[l]），最右边(q[r])，中间值(q[ l + r >> 1])和随机值。

注：q[ l + r >> 1]即q[(l + r) /2]，移1位比/2速度要快50倍。
常常容易混淆的运算符优先级：算数运算 > 移位运算 > 位运算 > 逻辑运算

  1. 使得 x 左边所有数不大于 x， x 右边所有数不小于 x（递增排序，如果递减排序则翻一下就行）
  2. 递归处理 x 得左右两段

具体实现：
定义两个指针 i 和 j 。
使 i 向右移，使 j 向左移，保证 i 左边的元素不大于 x ， j 右边的元素不小于x，如果i和j指向的元素不满足这个条件，则使 i 和 j 指向的元素进行交换。
递归将 j 左端和右端的元素进行上续操作。

快排过程以1,5,3,2为例：
快排--模板及思想 - 图1

问题

  1. i 和 j 的指向
    答： 用i和j两个指针分别指向数组的两端，i要指向第一个元素的前一个位置，j要指向最后一个数组的后一个位置，因为模板代码中的循环是do-while循环，每次不管三七二十一都会先向中间聚拢一次。
  2. 模板最后递归调用能不能用 i 做分界？即
    1. quick_sort(q, l , j);
    2. quick_sort(q, j + 1, r);
    这段代码能不能换成 答：可以换，但换成 i 后需要需要将 x 由 q[l] 换成 q[r] 或者 q[(l + r + 1) / 2] ,否则会有边界问题，造成死循环。同理，如果以 j 为分界则 x 不能为 q[r]。
    例子：1 2 两数进行快排，方法调用为quick_sort(q, 0, 1)
    快排--模板及思想 - 图2
    此时递归调用的quick_sort(q, 0, 1)发生了死循环。