一、快速排序

已经学过的排序

 

 分而治之

 

 

轴点

pivot：

 

 快速排序

 

 坏消息：在原始序列中，轴点未必存在...

必要条件：轴点必定已然就位 // 尽管反之不然

derangement： 2 3 4... n 1

特别地：在有序序列中，所有元素皆为轴点；反之依然

快速排序就是将所有元素逐个转换为轴点的过程

问题：如何交换？成本多高？

 

构造轴点

 

选取轴点候选作为培养对象，通常取序列的首元素m 

构造过程中用到lo与hi，将序列分为L、U、G三部分

L是前缀，任何一个元素都不超过轴点的候选，G是后缀，任何一个元素都不小于轴点的候选

处于二者之间的序列U，由大小未知的元素构成

初始状态U是整个序列，L和G都是空的

启动后，尝试交替的将lo和hi向内测移动，从而令它们彼此靠近

lo每移动一步，L就拓展一单位，hi和G也是，在这过程中，U的元素被加入到L或G中

最终，hi和lo指向同一个位置，将之前选定的轴点候选者放在该处，成为名副其实的轴点

 

不变性+单调性

 

 初始情况，L和G都是空的，pivot大于等于L小于等于G，自然满足

U 的首元素已经作为轴点候选被取出备份，可以认为是空闲的

一般情况：

假设lo空闲，左侧拓展子序列G，只要末元素_elem[hi]不小于候选轴点，就对hi递减一个单位

从而将原来的元素归入到G中，新的末元素依然满足这种条件，继续归入到G中，直到某个时刻末元素不再满足条件

将末元素hi转移至空闲的单元lo中，hi变为空闲的

进而考察_elem[lo]，拓展L，直到首元素lo在数值上不超过候选轴点

将lo转入到hi中

 

 实例

首元素6取做待培养的候选轴点，取出备份之后，对应的单元在逻辑上看作空闲的

此时，首先考察末元素也就是7，大于候选轴点6，归入到G

新的末元素1小于6，应归入到子序列L中，为此将1转移到空闲的lo处，即首元素位置

向右扩展，3小于6，再扩展，8大于6，

转移到hi位置，lo空闲

左侧5小于6，转移到lo，hi空闲

右侧2小于6，右侧5小于6

右侧9大于6，转到hi，lo空闲

左侧4小于6，转到lo

右侧的U只剩下一个元素，此处应放6，是轴点

 

 性能分析

 

 

 

 

 平均性能

 

 

 

a4 快速排序：变种

不变性：

 

 L和G在U左边

 

 

 单调性

 

 实现

 

 实例

 

 

b1 选取：众数

选取与中位数

 

 

众数

 

 必要条件

 

 

减而治之

 

 算法

 

 

 

 b3 选取：通用算法

尝试：蛮力

尝试：堆（A）

 

 

 

 

尝试：堆（B）

 

 

 

尝试：堆（C)

H：任取k个元素，组织为大顶堆 // O(k)

G：其余n-k个元素，组织为小顶堆 // O(n-k)

反复地：比较h和g // O(1)

    如有必要，交换之 // O(2*(logk+log(n-k)))

直到：h<=g // O(min(k, n-k))

 

 

 

quickSelect()

 

 

 

linearSelect()

 

 

 

复杂度

 

 

 

希尔排序

Shellsort

 

 

实例

 

 

 

 

 

 

 

call-by-rank

 

 

Insertionsort

 

 

 Shell's Sequence

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---恢复内容结束---