排序 -- 快排/归并

聊聊排序吧

• 冒泡排序

• 选择排序

• 插入排序

• 快速排序

• 归并排序

• 计数排序

• 桶排序

• 堆排序

本篇 快排/归并

之前的三种排序(冒泡/插入/选择)都是O(N^2)的时间复杂度, 下面介绍两种更加高效的排序算法.

• 快排和归并两种算法都是递归 + 分治的思路

---

快速排序

• 排序思路
  • 每次选择一个pivot, 将当前数组分为两部分, 左半部分小于pivot, 右半部分大于pivot
  • 对其他部分继续递归处理
• 代码实现

private void doSort(int[] arr, int p, int r) {

    if (p >= r) {
        return;
    }
    int q = partition(arr, p, r);

    // 这下面一个是 q - 1, 一个是 q + 1
    // q 已经排序过了，如果把 q - 1 换成 q 就会死循环
    doSort(arr, p, q - 1);
    doSort(arr, q + 1, r);
}

private int partition(int[] arr, int p, int r) {
    // 选定一个pivot
    int pivot = arr[r];
    int x = p - 1;

    int tmp;

    for (int j = p; j < r; j++) {
        if (arr[j] <= pivot) {
            x++;
            // swap arr[x] arr[j]
            if (x == j) continue;
            tmp = arr[x];
            arr[x] = arr[j];
            arr[j] = tmp;
        }
    }
    // swap arr[x + 1] arr[r]
    if (r != x + 1) {
        tmp = arr[x + 1];
        arr[x + 1] = arr[r];
        arr[r] = tmp;
    }
    return x + 1;
}

• x指向的小于pivot部分的最后一个元素
• 后面比较碰到大于pivot的元素, 则将下标x自增后的元素与之交换
• 最后将x + 1与pivot交换, 数组达到有序

- 时间复杂度

思路挺简单, 来分析一下其时间复杂度
对于使用递归思想的算法, 首先要写出其递推公式
快排的时间复杂度分为两部分

1. 分区函数 partition
2. 分区后两部分的递归排序

分区函数是对数组的遍历操作, 时间复杂度为O(N). 使T(n)代表排序n个数的数组所需时间复杂度, 写成递推公式就是这样,

T(n) = n + 2T(n/2)

多写几行看看:

  T(n)  = n + 2T(n/2)
        = n + 2 * (n/2 + 2T(n/4)) = 2n + 4T(n/4)
        = 2n + 4 * (n/4 + 2T(n/8)) = 3n + 8T(n/8)
        ...
        = kn + 2^k * T(n / 2^k)

对于数组长度为1数组，排序时间复杂度为常数级别O(1)：

T(1) = C

所以

T(n / 2^k) = T(1)
k = log2n

因为大O的时间复杂度表示法中是会忽略系数与低阶的，而又有logkn = logk2 * log2n, 所以下文的log级别都写成 lg

代回去得到：

T(n) = nlgn + Cn

快排的时间复杂度就是 O(nlgn)

为了方便阅读, 上面公式成立的前提我们是假设每次都均分(n/2), 但是不可能每次你都能选到数组的中位数做pivot 吧?
不是均分也是一样的分析, 假如是1 : 7:

T(n) = n + 7T(7n / 8) + T(n/8)

照上述方法继续算一遍就可以得到相同的结果，就不展开了~
不过你可能听过一句话：

快排在极端情况下会退化为冒泡排序

这句话是对的, 上面的大多数情况都可以保证O(nlgn)的时间复杂度, 但如果数组完全逆序排列的而每次都选举最大的那个数为pivot, 那每次排序都需要扫描n/2的数据, 时间复杂度就退化为O(N^2)

为了快排不退化, 可以优化pivot的选择条件(三数取中法/随机选取)

- 原地和稳定

• 没有用到其他额外空间, 是原地排序
• 存在交换非相邻元素操作, 不是稳定排序

归并排序

• 排序思路
  • 待排序数组均分两部分
  • 这两部分进行排序
  • 两部分都有序后合并成整体有序
  • 对每部分都递归此方法
• 代码实现

/**
 * doSort
 * 
 * @param arr 待排序数组
 * @param p 起始下标
 * @param r 结束下标
 */
private void doSort(int[] arr, int p, int r) {

    if (p < r) {
        int q = (p + r) >> 1;
        // 对子数组排序
        doSort(arr, p, q);
        doSort(arr, q + 1, r);
        // 合并两个子数组
        merge(arr, p, q, r);
    }
}

/**
 * merge
 * 
 * @param arr 待排序数组
 * @param p 起始下标
 * @param q 合并的分界点下标
 * @param r 结束下标
 */
private void merge(int[] arr, int p, int q, int r) {

    int[] tmp = new int[arr.length];
    // 记录本次循环数组开始位置, 用于后面替换数组
    int pn = p;
    // 第二个子数组开始下标
    int p1 = q + 1;

    // p -> q, q + 1 -> r
    int n = 0;
    while (p <= q && p1 <= r) {
        if (arr[p] <= arr[p1]) {
            tmp[n] = arr[p];
            p++;
        } else {
            tmp[n] = arr[p1];
            p1++;
        }
        n++;
    }

    // 将多出部分入数组
    while (p <= q) {
        tmp[n++] = arr[p++];
    }
    while (p1 <= r) {
        tmp[n++] = arr[p1++];
    }

    // 从 tmp 到 arr 数组替换
    // tmp 从 0 开始填充数据
    // arr 从 pn 开始的比较
    // 总计n个数, 下标 + 1 为实际数量
    System.arraycopy(tmp, 0, arr, pn, n);
}

- 时间复杂度

归并的时间复杂度分为三部分

• 俩子数组的排序
• 合并函数merge

是不是跟快排灰常像? 下面我们继续来分析一波~
老规矩, 先写递推公式:
合并函数是遍历两个子数组, 时间复杂度为O(N)

T(n) = n + 2T(n/2)

这几乎和上面的是一样一样的, 就不照抄一遍了, 时间复杂度为O(nlgn), 而且这跟数组的原始有序程度无关, 归并可以做到最好/最坏/平均 时间复杂度都是O(nlgn)

- 稳定和原地

• 稳定的关键在于merge函数只要保持数据原有顺序就行了, 所以是稳定排序
• 合并数组时需要一个额外最大为原数组长度的数组, 空间复杂度 O(N), 不是原地排序

稳定性 如此高/如此好, 缺陷也是如此明显, 可惜可惜...

快排与归并的比较

• 基本比较

名称	原地	稳定	最好	最坏	平均
归并排序	否(O(N))	是	O(NlgN)	O(NlgN)	O(NlgN)
快速排序	是	否	O(NlgN)	O(N^2)	O(NlgN)

• 归并是从下向上有序, 快排是从上向下有序

网上找了一张图(侵删)

快排与归并

---

犹豫就会败北, 果断就会白给

今天又是颓废的一天啊~~~~