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

空间复杂度(考虑递归调用的最大深度)在平均情况下为O(logn)，在最坏情况下为O(n)。 快速排序是不稳定的。

简单选择排序

思路

第i趟排序过程是在剩余的待排记录中选一个最小（大）的，放在第i个位置。

27一句话，“在待排记录中选取最小的，交换到合适位置，重复n-1次”。

例：{52 49 80 36 14 58 61}简单选择排序。

程序 void

{

for for

if

if

}

}

分析

2时间复杂度O(n)，耗费在比较记录上，比较次数始终为n(n-1)/2，移动次数最小为0，最

大3(n-1)，即

n-1次交换。

注意：简单选择排序是不稳定的。反例：(101，102，9) ? (9，102，10

1)。

堆排序

堆及其特点

堆，小顶堆，大顶堆。

序列{K1,K2, ..., Kn}满足Ki≤K2i，Ki≤K2i+1，称为小顶堆；若满足Ki≥K2i，Ki≥K2i+1，称为大顶堆，其中i=1, 2, ..., n/2。

特点：小顶堆的堆顶(第一个元素)为最小元素，大顶堆的堆顶为最大元素。

判断序列是否构成堆

方法：用Ki作为编号为i的结点，画一棵完全二叉树，比较双亲和孩子容

易判断是否构成堆。

例：判断序列(12,36,24,85,47,30,53,91)是否构成堆。

27 不准确的说法，只为便于理解和记忆，不要在正式场合引用。

根据上图判断，该序列构成小顶堆。 建立堆

一句话，“‘小堆’变‘大堆’，从?n/2?变到1”。第?n/2?个是最后一个分支结点。 例：把(24,85,47,53,30,91,12,36)调整成小顶堆。

堆排序 思路：

28

例：(24,85,47,53,30,91,12,36)进行堆排序。

28

不准确的说法，只为便于理解和记忆，不要在正式场合引用。

整个排序步骤如下：

24 85 47 53 30 91 12 36 91 85 47 53 30 24 12 36

堆排序是不稳定的。时间复杂度是O(nlogn)。 归并排序

思路

归并，两个或多个有序表合并成一个有序表。归并排序。二叉排序树的建立

例：对{24, 85, 47, 53, 30, 91}归并排序。

(24(85(47(53(30(91(24 85) (47 53) (30 91) (24 47 53 85) (30 91) (24 30 47 53 85 91)

自底向上归并排序

(24(85(47(53(30(91(24 85) (47(30 53) (91(24 47 85) (30 53 91) (24 30 47 53 85 91)

归并排序

程序

归并排序：

void MergeSort ( T a[], int low, int high )

{

if ( low>=high ) return;

else {

mid = (low+high)/2;

MergeSort ( a, low, mid );

MergeSort ( a, mid+1, high );

Merge ( a, low, mid, high );

}

}

自底向上的归并排序：

void MergeSort ( T a[], int n )

{

t = 1;

while ( t<n ) {

s = t; t = s*2;

for ( i=0; i+t<=n; i+=t )

Merge ( a, i, i+s-1, i+t-1 );

if ( i+s<n )

Merge ( a, i, i+s-1, n-1 );

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