8wDlpd.png
8wDFp9.png
8wDEOx.png
8wDMfH.png
8wDKte.png

快速排序讲解(C++20)

LV.2 eofitg 7月前 270

叠甲x

 

只是个曾经学过算法的蒟蒻深夜睡不着在试图整理以前学过的知识,或许已经忘了又或许没忘……

总之,虽然所有代码均经过了测试,但仍然不敢保证完全准确,如果哪里有误欢迎大佬指正(

 

快速排序

 

快速排序 (Quick Sort),是一种高效且复杂度相对稳定的排序算法,在一定优化之后更可以达到绝大多数情况下 O(n log n) 的时间复杂度和不超 O(log n) 的空间复杂度

 

原理

 

快速排序的实现基于分治思想:

每次将原数组分割为两个子数组,保证左子数组中任一元素都小于右子数组中任一元素,然后递归处理两个子数组直到数组只剩一个元素,从而完成对整个数组的排序

 

具体实现

 

  1. 划分数组为两个子数组

  2. 递归继续划分两个子数组

  3. 子数组元素仅剩一个时,达到递归边界,完成排序

 

1. 划分数组

 

先任意选中数组一个值,然后将剩余的元素和这个值相比较,比这个值小的就交换到数组左侧,大的就交换到右侧(类似于冒泡排序的思想)

这个初始值一般情况下随机选取一个即可,但为了进一步减小快速排序退化为冒泡排序的概率,可以在左侧索引 l 和右侧索引 r 以及中间索引 (l+r)/2 指向的三个数中取中位数,来尽可能避免取到极端值

 

// 取三个数的中位数
int median(vector<int> &x, int l, int m, int r) {
    if ((x[l] < x[m]) ^ (x[l] < x[r])) {
        return l;
    } else if ((x[m] < x[l]) ^ (x[m] < x[r])) {
        return m;
    } else {
        return r;
    }
}
// 构建快速排序的两个分治数组,返回分割点的索引
int execute(vector<int> &x, int l, int r) {
    int m = l + r >> 1;
    int check = median(x, l, m, r);
    ...
}

 

为了方便处理(更好地模拟冒泡排序x),可以先将选中值挪到数组的首位,之后再处理 [l, r] (因为在递归处理中除了选中值外的数组元素数量有可能不足 2 ,此时可能需要交换选中值和另一个值,所以要把 l 囊括进去)

 

int execute(vector<int> &x, int l, int r) {
    ...
    // 将选中的值暂时挪到数组最左边,方便对其余值的处理
    swap(x[check], x[l]);
    // 处理区间是第一个值到最后一个值
    int i = l, j = r;
    ...
}

 

之后

从右到左取第一个小于check的索引,

从左到右取第一个大于check的索引,

再将这两个值交换来让更小的值逐渐浮动到左侧

 

int execute(vector<int> &x, int l, int r) {    
    ...
    while (i < j) {
        // 从右到左找到第一个小于选中值的索引
        while (i < j && x[j] >= x[l]) {
            j --;
        }
        // 从左到右找到第一个大于选中值的索引
        while (i < j && x[i] <= x[l]) {
            i ++;
        }
        swap(x[i], x[j]);
    }
    ...
}

 

数据处理完了,但是别忘了初始的选中值还在第一位等待被插入

我们可以观察到,最终的ij会返回一个终止循环的位置,这个位置也就是这两个子数组被分割的地方,但是该怎么在这个位置插入初始值呢?是插到后面还是前面呢?

分析一下代码的运行过程其实就有了答案:

 

∵ 循环中是先从右到左找小于选中值的索引

∴ 必然是满足条件的j先选出,再选出i的值

∴ 一旦发生i >= j必然是i在查找的过程中走到了j的位置

    或j在查找的过程中走到了上一轮已经被j交换了的i的位置

∴ 最终返回的i必然是j上一轮找到的值的索引,必然小于选中值

∴ 可以通过交换x[l]x[i]的方式把选中值放到分割点的位置

 

int execute(vector<int> &x, int l, int r) {
    ...
    // 把选中值再插入回数组中
    swap(x[l], x[i]);
    // 返回分割点的位置,也就是选中值被插入的位置
    return i;
}

 

到此,原数组就已经被成功分割为 [l, i)(i, r] 两个子数组了

 

2. 递归继续划分

 

因为这个划分已经满足了选中值左侧的任一元素都小于该值,右侧的任一元素都大于该值,所以直接递归处理左右两侧的子数组即可

 

void quickSort(vector<int> &x, int l, int r) {
    ...
    // 划分数组
    int split = execute(x, l, r);
    // 递归继续划分
    quickSort(n, l, split - 1);
    quickSort(n, split + 1, r);
}
 
2.1 空间复杂度优化

 

不难发现,如果按照以上方式处理子数组,当遇到一些特殊数据,例如完全倒序的数组时,递归深度会达到n - 1O(n) 的空间复杂度,那么有没有办法优化呢?
其实优化也很简单:每次都只处理较短的那个子数组,较长的子数组等到在下一个递归中被划分后再处理,这样就可以把最差空间复杂度优化到 O(log n)

 

void quickSort(vector<int> &x, int l, int r) {
    while (l < r) { // 递归边界
        // 划分数组
        int split = execute(x, l, r);
        // 仅递归较短的子数组
        if (split - l < r - split) {
            quickSort(x, l, split - 1);
            // 较长的那个留到下次经划分后再处理
            // 故区间为 (split, r]
            l = split + 1;
        } else {
            // 同理
            quickSort(x, split + 1, r);
            r = split - 1;
        }
    }
}

 

3. 排序完成

 

数组仅剩一个元素时代表已经排序完成,也就是递归边界

 

void quickSort(vector<int> &x, int l, int r) {
    // 数组仅剩一个元素
    if (l >= r) {
        return;
    }
    ...
}

 

完整代码

 

// 取三个数的中位数
int median(vector<int> &x, int l, int m, int r) {
    if ((x[l] < x[m]) ^ (x[l] < x[r])) {
        return l;
    } else if ((x[m] < x[l]) ^ (x[m] < x[r])) {
        return m;
    } else {
        return r;
    }
}
// 构建快速排序的两个分治数组,返回分割点的索引
int execute(vector<int> &x, int l, int r) {
    int m = l + r >> 1;
    int check = median(x, l, m, r);

    // 将选中的值暂时挪到数组最左边,方便对其余值的处理
    swap(x[check], x[l]);

    int i = l, j = r;
    /*
     * ∵ 循环中是先从右到左找小于选中值的索引
     * ∴ 必然是满足条件的 j 先选出,再选出 i 的值
     * ∴ 一旦发生 i >= j 必然是 i 在查找的过程中走到了 j 的位置
     *  或 j 在查找的过程中走到了上一轮已经被 j 交换了的 i 的位置
     * ∴ 最终返回的 i 必然是 j 上一轮找到的值的索引,必然小于选中值
     * ∴ 可以通过交换 x[l] 和 x[i] 的方式把选中值放到分割点的位置
     */
    while (i < j) {
        // 从右到左找到第一个小于选中值的索引
        while (i < j && x[j] >= x[l]) {
            j --;
        }
        // 从左到右找到第一个大于选中值的索引
        while (i < j && x[i] <= x[l]) {
            i ++;
        }
        swap(x[i], x[j]);
    }

    // 把选中值再插入回数组中
    swap(x[l], x[i]);

    return i;
}
// 最差空间复杂度 O(n)
void _quickSort(vector<int> &x, int l, int r) {
    // 数组仅剩一个元素
    if (l >= r) {
        return;
    }
    // 划分数组
    int split = execute(x, l, r);
    // 递归继续划分
    _quickSort(n, l, split - 1);
    _quickSort(n, split + 1, r);
}
// 最差空间复杂度 O(log n)
void quickSort(vector<int> &x, int l, int r) {
    while (l < r) { // 递归边界
        // 划分数组
        int split = execute(x, l, r);
        // 仅递归较短的子数组
        if (split - l < r - split) {
            quickSort(x, l, split - 1);
            // 较长的那个留到下次经划分后再处理
            // 故区间为 (split, r]
            l = split + 1;
        } else {
            // 同理
            quickSort(x, split + 1, r);
            r = split - 1;
        }
    }
}

 

论坛对Markdown的适配并不是很好,想要更好的阅读体验可以下载附件里的.md文件(以及可直接编译运行的快速排序模版源码)

 

猜你喜欢:
最新回复 (0)
只看楼主
全部楼主
返回
发新帖