8.2.2 Shell排序 算法分析



不稳定 空间代价：O(1) 时间代价：O(n2) 选择适当的增量序列，可使时间代价接近O(n) 增量序列的选择 增量每次除以2递减，时间代价为O(n2) 增量序列为{2k-1，2k -1 -1，…，7，3，1} 时，时 间代价为O(n3/2) 选取其他增量序列还可能更进一步减少时间代价
8.2.2 Shell排序

直接插入排序的两个性质：
在最好情况（序列本身已是有序的）下时间代 价为Θ(n) 对于短序列，直接插入排序比较有效


Shell排序有效地利用了直接插入排序的这两 个性质 。
8.2.2 Shell排序

算法思想：

先将序列转化为若干小序列，在这些小序列内进行插 入排序； 逐渐扩大小序列的规模，而减少小序列个数，使得待 排序序列逐渐处于更有序的状态， 最后对整个序列进行扫尾直接插入排序，从而完成排 序。

8.2.1 直接插入排序[算法8.1]
template <class Record> void InsertSorter(Record Array[ ]， int n ){ //直接插入排序，n个待排记录存于Array Record TempRecord; //临时变量……… S(n) =O(1) int i , j; for ( i=1; i<n; i++){ TempRecord =Array[ i ]; //待插入记录 j =i-1; //j指有序表表尾 while ( j >= 0 && TempRecord < Array[ j ]){ //比较 Array[ j+1 ] =Array[ j ]; //若待插值小，移动 j =j-1; } //下标左移，继续比 Array[ j+1] = TempRecord; } }; //待插就位j+1
8.3.1 直接选择排序[算法8.3]

堆定义 (p120 ch5.5.1) :

8.3.2 堆排序
n个元素的序列{k1,k2,...kn},满足以下关系时,称堆 k i <= k 2i or k i >= k 2i k i <= k 2i+1 k i >= k 2i+1 i=1,2,..n/2 最小堆 最大堆 存储结构：序列存储在一维数组 用“完全二叉树” 图示用“一维数组存储”的堆
直接插入排序举例



初始:R(49),R(38),R(65),R(97),R(76),R(13),R(27),R(49) 有序表:R(49) 第2趟:R(38),R(49),... 第3趟:R(38),R(49),R(65),... 第4趟:R(38),R(49),R(65),R(97),... 第5趟:R(38),R(49),R(65),R(76),R(97),… 第6趟:R(13),R(38),R(49),R(65),R(76),R(97),… 第7趟:R(13),R(27),R(38),R(49),R(65),R(76),R(97),. 第8趟:R(13),R(27),R(38),R(49),R(49),R(65),R(76),R(97)
直接插入排序算法分析
1.空间:一个辅助空间(TempRecord临时存放待插记录) 2.时间:2层循环，外层n-1趟，内层次数与输入数据有关 最好(正序)：O(n) 如1 3 5 7 9

每趟比较1次,共比较n-1次,当前记录入出临时变量，移动2(n-1)次

最坏(逆序)： O(n2)

如 ( 9) 7 5 3 1
堆排序算法分析 不稳定 T(n)=Θ(nlog n) 建堆：Θ(n) 删除堆顶:Θ(log n) S(n)=Θ(1)
一次建堆 ,n次删除堆顶
8.4 交换排序 p204
基本思想: 两两比较,发现错位则交换,直至没错位 8.4.1 冒泡排序



“正序”序列 ：待排序序列正好符合排序要求
“逆序” 序列 ：把待排序序列逆转过来，正好符 合排序要求 “稳定的”(stable)排序算法 ：如果存在多个具有 相同排序码的记录，经过排序后这些记录的相对 次序仍然保持不变 。



ቤተ መጻሕፍቲ ባይዱ


插入排序 直接插入排序 Shell排序(Shell sort) 交换排序 冒泡排序(Bubble sort) 快速排序(Quicksort) 选择排序 直接选择排序(Selection sort) 堆排序(Heapsort) 归并排序(Mergesort) 分配排序(Binsort) 桶排序 基数排序 索引排序
第i趟
( 7 9 ) 第2趟结果


外层第i趟： 从第i-1到第0个，比较i次 移动 i+2次(第i-1到第0个,临时变量入出各一次)
i=2..n,共进行n-1趟 共比较 i=1n-1 i = (n+2)(n-1)/2次, 移动 i=in-1（ i+2）= (n+4)(n-1)/2次



平均
7
[算法8.2]“增量每次/2递减”的Shell排序 2/2
template <class Record> ModInsertSort(Record Array[ ],int n, int delta) { // 对子序列中第i个记录排序 for (int i=delta; i<n; i+=delta) for (int j= i; j >=delta; j-=delta){ //j>=delta才继续 if ( Array[ j] < Array[j-delta])) //错位 swap(Array, j, j-delta); //交换,继续 else break; //正序,不必再比,退出内层for } }
排序的目的就是将R中的记录按照特定的顺序重新排列， 形成一个新的有序序列R’= {r’1, r’2, …，r’n}



相应排序码为k’ ={k’1, k’2, …，k’n}
其中k’1≤k’2≤…≤k’n或k’1≥k’2≥…≥k’n ,前者称为不减序， 后者称为不增序。
8.1基本概念

内排序(Internal Sorting)：整个排序过程中所有的 记录都可以直接存放在内存中 外排序(External Sorting)：内存无法容纳所有记 录，排序过程中还需要访问外存


关键码(Key)：唯一确定记录的一个或多个域
排序码(Sort Key)：作为排序运算依据的一个或多个域 序列(Sequence)：由待排记录组成的集合 排序(Sorting) — 将序列中的记录按照排序码特定的顺序 排列起来，即排序码域的值具有不减(或不增)的顺序




给定序列R ={r1, r2, …，rn}其排序码为k ={k1, k2, …，kn}

8.1 基本概念 8.2 插入排序
直接插入排序 Shell排序

第8章 内排序

8.3 选择排序
直接选择排序 堆排序


8.4交换排序
冒泡排序 快速排序




8.5 归并排序 8.6 分配排序和索引排序 8.7 排序算法的时间代价
8.1基本概念 p194
记录(Record)：结点，进行排序的基本单位
增量d递减
[算法8.2]“增量每次/2递减”的Shell排序 1/2 template <class Record > 0 1 2 3 4 5 6
void ShellSort( Record Array[ ], int n){ { int i, delta; for ( delta=n/2; delta>0; delta/=2) //分别对delta个子序列排序 for (int i =0; i <delta; i++) ModInsSort(&Array[i], n-i, delta); } n=8 外层for delta=4 内层for i=0..3 第1次ModInsSort(A[0],8,4) A[0]A[4] 第2次ModInsSort(A[1],7,4) A[1]A[5] 第3次ModInsSort(A[2],6,4) A[2]A[6] 第4次ModInsSort(A[3],5,4) A[3]A[7] 外层for delta=2 内层for i=0..1 第1次ModInsSort(A[0],8,2) A[2]比A[0],A[4]比[2],A[6]比A[4] 第2次ModInsSort(A[1],7,2) A[3]比A[1],A[5]比A[3],A[7]比A[5]
排序算法的分类
排序算法的衡量标准

时间代价：记录的总比较和总移动次数

一次swap交换导致3次移动

时间代价分3种：
最小时间代价 最大时间代价 平均时间代价


空间代价
8.2 插入排序(Insert Sorting)


算法思想： 逐个处理待排记录，每个新记录都要与 前面那些已排好序的记录进行比较，然 后插入到适当的位置，得到一个新的、 记录数增 1的有序表。 8.2.1 直接插入排序 8.2.2 Shell排序

比较：


直接选择排序：直接从剩余记录中线性查找最小记录 堆排序：利用堆结构保持记录相对大小信息，效率更高

堆排序步骤： 建立最大堆 首尾交换(最大存最后)，堆元素个数-1，对根筛选， 重复直至堆剩1个元素
1.初始建堆结果