数据结构 第十章

算法评价(参考)
时间复杂度
若待排序记录按关键字从小到大排列(正序) 关键字比较次数： 记录移动次数：0 若待排序记录按关键字从大到小排列(逆序)
1 n 1
i 2
n
(n 2)(n 1) 2 i 2 n (n 4)(n 1) 记录移动次数： (i 1) 2 i 2
时间复杂度：O(nlogn)
10.3 快速排序分析
快速排序在最好情形下(左、右子区间的长度
大致相等)，则结点数n与二叉树深度h应满足 log2n<h<log2n+1，所以总的比较次数不会超 过(n+1)log2n。因此，快速排序的最好时间复 杂度应为O(nlog2n)。理论上已经证明，快速 排序的平均时间复杂度也为O(nlog2n)。 在最坏情况下(逆序或正序)，时间复杂度为 O(n2) 空间复杂度：O(logn)
10.3 交换排序 冒泡排序 排序过程
将第一个记录的关键字与第二个记录的关
键字进行比较，若为逆序r[1].key>r[2].key， 则交换；然后比较第二个记录与第三个记 录；依次类推，直至第n-1个记录和第n个 记录比较为止——第一趟冒泡排序，结果 关键字最大的记录被安置在最后一个记录 上 对前n-1个记录进行第二趟冒泡排序，结果 使关键字次大的记录被安置在第n-1个记录 位置 重复上述过程，直到“在一趟排序过程中 没有进行过交换记录的操作”为止

假设含 n 个记录的序列为 { R1 ,R2 ,…,Rn } 其相应的关键字序列为 { K1，K2，…，Kn } 需确定1，2，…，n的一种排列 p1，p2，…，pn 使关键字满足非递减（或非递增）关系 Kp1≤Kp2≤…≤Kpn 即使初始的的序列成为一个按关键字有序的 序列 { Rp1，Rp2，…，Rpn} 这样一种操作称为排序。

0
1
2
3
4
5
6
7
8
i=5
MAXINT 49 2 3
MAXINT 49 6 3 MAXINT 49 6 3 MAXINT 49 6 8
38 1
38 1 38 1 38 1
65 97 5 0
65 5 65 5 65 5 97 0 97 0 97 0
76 4
76 4 76 4 76 4
13
27
49
i=6



最坏情况下,待排记录按关键字非递增有序 排列（逆序）时，第 i 趟时第 i＋1 个对象 必须与前面 i 个对象都做排序码比较, 并且 每做1次比较就要做1次数据移动。总比较 次 数 为 (n+2)(n-1)/2 次 ， 总 移 动 次 数 为 (n+4)(n-1)/2。 在平均情况下的排序码比较次数和对象移 动次数约为 n2/4。因此，直接插入排序的 时间复杂度为 O(n2)。 直接插入排序是一种稳定的排序方法。
折半插入排序 (Binary Insertsort)
基本思想 既然每个要插入记录之前的纪录 已经按关键字有序排列，在查找插入位 臵时就没有必要逐个关键字比较，可以 使用折半查找来实现。由此进行的插入 排序称之为折半插入排序。
折半插入排序的算法
void BInsertSort (SqList &L){ for (i=2;i<=L.length;++i){ L.r[0]=L.r[i]; low=1;high=i-1; //查找范围由1到i-1 while(low<=high){ m=(low+high)/2; if LT(L.r[0].key,L.r[m].key) high=m-1; else low=m+1; }//while 折半查找 for (j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; //折半查找结束后high+1位臵即为插入位臵 L.r[high+1]=L.r[0]; }//for }//BInsertSort

折半插入排序是一个稳定的排序方法。 折半插入排序只适合于顺序存储的排序表。
17
10.2.3表插入排序 （直接插入排序应用于用静态链表存储的排序表） 直接插入排序、折半插入排序均要大量移动记录，时间
开销大。若不移动记录完成排序，需要改变存储结构，进行 表插入排序。
表插入排序：用单链表做排序表的存储结构，通过改变 链接指针，实现关键码有序的过程。
0
12
34
5
6
7
8
MAXINT
49
38
65
97
76
13
27
49
(a)
6
8
1
5
0
4
7
2
3
0
12
34
5
6
7
8
MAXINT 13
27
38
49
49
65
76
97
(b)
1
2
3
4
5
6
7
8
0
23
重排记录方法：按链表顺序扫描各结点，将逻辑上的第i 个数据元素调整到数组的第i个分量上。
问题：调整前的第i个纪录可能在数组的第j个分量上，
[ 10 18 20 36 60 ] 25 30 18 12 56
其中，前5个记录组成的子序列是有序的，这时要将第6 个记录插入到前5个记录组成的有序子序列中去，得到一个含 有6个记录的新有序序列。完成这个插入首先需要找到插入位 置：20<25<36，因此25应插入到记录20和记录36之间，从 而得到以下新序列：
与顺序存储的排序表所不同的是：直接插入排序要移动 记录，而表插入排序是修改链接指针。
18

数据结构
第十章 内部排序
主要讨论的问题:几个基本概念;插入类排序;交换 类排序;选择类排序;归并排序;基数排序. .几个基本概念 .排序:将一个记录的任意序列重新排列成一个 按关键字有序的序列. .稳定排序:若待排序的记录中存在两个或两个以 上的主关键字相等的记录,排序前的序列中Ri在Rj 的前面,若在排序后Ri仍在Rj的前面,则称所用的排 序方法是稳定的,否则,称所用的排序方法是不稳 定的.
16
21
最小者 16 交换25,16
i=2
08
16
49
25*
25
最小者 21 21 交换49,21
28
i=3
08 0
16
1
21 2
25* 3 25*
25 4 25
最小者 25* 49 无交换
5
i=4
08
16
21
最小者 25 49 无交换
结果
08
16
21
25*
25
49
各趟排序后的结果
29
i =1时选择排序的过程
21 0
25 1
49 2
25* 3
16
4
08 5
21 0
25 1
49 2
25* 3
16 4
08 5
25 temp
i=2
21
25
49
25*
16
49 08
0
1
2
3
4
5
temp
6
i=3
21 0
25 1
49 2
25* 3
16
4
08 5
25*
i=4
21 0