知识卡片

普通读书笔记卡 · 5654.c.1.a.2.a.2.a.17 · 生成模型:未记录

快排优先处理较小子区间

理解等级:中级

分区后递归处理较小一侧,并以循环继续处理较大一侧,可使同时存在的递归层数为 O(log n):每一层递归的区间最多为上一层的一半。显式栈也可以先压入大区间、后压入小区间,使小区间先出栈;实现仍应检查栈容量。

栈空间控制与比较次数是不同问题,极端分区仍可能导致 O(n²) 时间。对于大量重复键,三路分区将小于、等于、大于枢轴的元素分组,再跳过等值区,可避免全等输入反复处理同一批等值元素。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      首先处理小的子数组。 如果系统栈的深度是可预见的,那么快速排序也许不适合你的应用程序。一种打破这个僵局的方法是使用一个栈的数据结构来存储将要解决的子问题,而不是依赖于递归。 为小数组使用简单的插入排序 在小数组上,插入排序比快速排序要快得多,当处理大数组时,快速排序最终还是将大数组切分成无数的待排序

    参考来源

    - 位置:《算法技术手册》第4章《变种》(spine1511;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1474.html;u084-ch04-018)。 - 结论依据:84全文实读;递归加循环和三路分区为应用推导。 - 原始内容:首先处理小的子数组。 如果系统栈的深度是可预见的,那么快速排序也许不适合你的应用程序。一种打破这个僵局的方法是使用一个栈的数据结构来存储将要解决的子问题,而不是依赖于递归。 为小数组使用简单的插入排序 在小数组上,插入排序比快速排序要快得多,当处理大数组时,快速排序最终还是将大数组切分成无数的待排序