数据结构之编写冒泡排序算法(4)

13 24 37 90 13 24 37 90 53 13 24 20 37 90 53 40

错误！未找到引用源。 13 24 RR 37 13 24 40 24 37 13 37 53 RL 90 24 13 37 53 90

24 13 37 40 53 RL 24 90 13 37 53 40 90 13 20 24 37 53 40 LR 20 90 13 37 53 24 40 90

错误！未找到引用源。

思路：实际上就是对二叉排序树的查找。具体算法参见“错误！未找到引用源。”二叉排序树的查找算法(递归和非递归算法)。

错误！未找到引用源。 结果：20，5，6。 分析：最坏情况下，二叉排序树的深度为n(结点个数)，最小深度等于完全二叉树的深度?logn??1。 平衡二叉排序树的最大深度和结点数的关系为Nh=Nh-1+Nh-2+1，N0=0，N1=1。

错误！未找到引用源。 结果：2，4，3。

分析：非空B-树中的根结点最少可以有2棵子树，其他非终端结点至少含有?m/2?=3棵子树。结点最多有m=5棵子树，m-1=4个关键字。

错误！未找到引用源。

思路：依次插入关键字建立哈希表。详细步骤参见“错误！未找到引用源。错误！未找到引用源。”。

0 1 2 3 4 5 6 7 8 9 10 11 12 141 12 681 191 201 852 91 231 1) ASL = (1+2+1+1+1+2+1+1)/8 =5/4=1.25

0 1 2 3 4 5 6 7 8 9 10 11 12 202 141 681 853 191 12 91 231 2) ASL = (2+1+1+3+1+2+1+1)/8 =3/2=1.5 3)

0 /\\ 1 2 /\\ 3 4 /\\ 5 /\\ 6 7 8 /\\ 9 10 11 /\\ 12 /\\

14 68 /\\ 1 /\\ 19 /\\ 20 9 /\\ 23 /\\ 85 /\\ ASL = (1+2+1+1+1+2+1+1)/8 =5/4=1.25

错误！未找到引用源。

1) 直接插入排序

(24), 86, 48, 56, 72, 36 (24, 86), 48, 56, 72, 36 (24, 48, 86), 56, 72, 36 (24, 48, 56, 86), 72, 36 (24, 48, 56, 72, 86), 36 (24, 36, 48, 56, 72, 86) 2) 希尔排序

24, 86, 48, 56, 72, 36 dk=3 24, 72, 36, 56, 86, 48 dk=2 24, 48, 36, 56, 86, 72 dk=1 24, 36, 48, 56, 72, 86 3) 起泡排序

24, 86, 48, 56, 72, 36 24, 48, 56, 72, 36,(86) 24, 48, 56, 36,(72, 86) 24, 48, 36,(56, 72, 86) 24, 36,(48, 56, 72, 86) 24,(36, 48, 56, 72, 86) 4) 快速排序

{24, 86, 48, 56, 72, 36}

{}24{86, 48, 56, 72, 36} {36, 48, 56, 72}86{} {}36{48, 56, 72} {}48{56, 72} {}56{72} (24, 36, 48, 56, 72, 86)

5) 简单选择排序

24, 86, 48, 56, 72, 36 (24), 86, 48, 56, 72, 36 (24, 36), 48, 56, 72, 86 (24, 36, 48), 56, 72, 86 (24, 36, 48, 56), 72, 86 (24, 36, 48, 56, 72), 86 6) 堆排序

24, 86, 48, 56, 72, 36

(86, 72, 48, 56, 24, 36) (建立堆) (72, 56, 48, 36, 24), 86 (56, 36, 48, 24), 72, 86 (48, 36, 24), 56, 72, 86 (36, 24), 48, 56, 72, 86 (24), 36, 48, 56, 72, 86 7) 归并排序

(24),(86),(48),(56),(72),(36) (24, 86), (48, 56), (36, 72) (24, 48, 56, 86), (36, 72) (24, 36, 48, 56, 72, 86) 8) 链式基数排序

(24, 86, 48, 56, 72, 36) 分配：

[0][1][2][3][4][5][6][7][8][9] 72 24 86 48 56 36

收集：72, 24, 86, 56, 36, 48 分配：

[0][1][2][3][4][5][6][7][8][9] 24 36 48 56 72 86 收集：(24, 36, 48, 56, 72, 86)

错误！未找到引用源。 分析：含有n个记录的序列排序可能的初始状态有n!个，所以描述n个记录排序过程的判定树必有n!个叶子，二叉树的高度h≥log2(n!)+1。该判定树上必定存在长度为log2(n!)的路径。所以借助比较的排序方法在最坏情况下的所需要比较次数至少为log2(n!)。时间复杂度为O(log2(n!)) = O(nlogn)。

百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库数据结构之编写冒泡排序算法(4)在线全文阅读。