二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(29)

}

}

附：Merge()，将有序序列a[low..mid]和a[mid+1..high]归并到a[low..high]。 void Merge ( T a[], int low, int mid, int high )

{

// 归并到b[]

i = low; j = mid+1; k = low;

while ( i<=mid and j<=high ) {

if ( a[i]<=a[j] ) { b[k] = a[i]; i++; }

else { b[k] = a[j]; j++; }

k++;

}

// 归并剩余元素

while ( i<=mid ) b[k++] = a[i++];

while ( j<=high ) b[k++] = a[j++];

// 从b[]复制回a[]

a[low..high] = b[low..high];

}

分析

时间复杂度O(nlogn)。需要空间多，空间复杂度O(n)。归并排序是稳定的排序。

基数排序

思路

多关键字排序

最高位优先（MSD），最低位优先（）。

链式基数排序

链式基数排序采用“分配”和“收集”策略。

例：{503，087，512，061，908，170，897，275，653}

分析：数字0~9共10种情况，rd=10。

每个关键字都有3位数字，d=3。

共有9个记录，n=9。

先“收集”成一个链表，

按最低位（个位）“分配”到10个链表中（0号~9号）：

[0] [1] [2] [3]

170 061 512 503

653 [4] [5] 275 [6] [7] [8] 087 908 897 [9]

按个位顺序“收集”成一个链表：

( 170, 061, 512, 503, 653, 275, 087, 897, 908 )

再按第2位数字（十位）“分配”到10个链表中：

[0] [1] 503 512

908 [2] [3] [4] [5] [6] [7] 653 061 170 275 [8] [9] 897

“收集”成一个链表：

( 503, 908, 512, 653, 061, 170, 275, 897 )

按第3位数字（百位）“分配”到10个链表中：

[0] [1] [2] 061 170 275

[3] [4] [5] [6] 503 653 512 [7] [8] [9] 897 908

“收集”成一个链表：

( 061, 170, 275, 503, 512, 653, 897, 908 )

完成排序。

分析

对n个数据进行基数排序，每个数据基数为rd，有d位数字。那么，一趟分配和收集用时n+rd(分配用n，收集用rd)，共需d趟，总的时间复杂度为O(d(n+rd))。

基数排序是稳定的排序算法。

各种排序方法比较

基于关键字比较的排序方法，在最坏情况下所能达到的最好的时间复杂度是O(nlogn)。

《数据结构》复习大纲

一、单选题

栈和队列的共同特点是()。 A.只允许在端点处插入和删除元素 B.都是先进后出C.都是先进先出 D.没有共同点

用链接方式存储的队列，在进行插入运算时( ).

A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改

以下数据结构中哪一个是非线性结构？( )

A. 队列B. 栈C. 线性表D. 二叉树

树最适合用来表示()。

A.有序数据元素B.无序数据元素

C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 二叉树的第k层的结点数最多为( ).

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-29.html