第10章-内部排序

第 2 遍选择 16 56 48 85 89 21 47

21 第 3 遍选择 16 19 48 85 89 56 47

47 第 4 遍选择 16 19 21 85 89 56 48

第 5 遍选择 16 19 21 47 89 56 85 48

第 6 遍选择 16 19 21 47 48 89 85 56

第 7 遍选择 16 19 21 47 48 56 89 85

图 3.7 简单选择排序例

? 简单选择排序在最坏情况下需要比较 n(n-1)/2 次

selesort (int p, int n ) {

int i，j， k, d；

for ( i=1；i<=n；i=i+1 ) {

k =i；

for ( j=i+1；j <=n；j =j+1 )

if( p[j]

if( k!= i ){

p[0] = p[i]； p[i]=p[k]； p[k]= p[0]；

} } }

? 快速排序的基本思想如下 :

通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序 。

从线性表中选取一个元素, 设为 T 。然后将线性表后面小于 T 的元素移到前面 , 而前面大于 T 的元素移到后面 , 结果就将线性表分成了两部分 ( 称为两个子表 ),T 插入到其分界线的位置处。这个过程称为线性表的分割。通过对线性表的一次分割, 就以 T 为分界线, 将线性表分成了前后两个子表, 且前面子表中的所有元素均不大于 T, 而后面子表中的所有元素均不小于 T。

? 这个过程如教材P275 图 10.7 所示。

初始关键字 49 38 65 97 76 13 27 49 一次划分后 { 27 38 13 } 49 { 76 97 65 49 } 分别进行快速排序 { 13 } 27 { 38 } 结束 结束 { 49 65 } 76 { 97 }

结束

49 { 65 }

结束

有序序列 { 13 27 38 49 49 65 76 97 }

Pivotkey

初始关键字 49 38 65 97 76 13 27 49 I j

进行1次交换后 27 38 65 97 76 13 49

进行2次交换后 27 38 97 76 13 65 49

进行3次交换后 27 38 13 76 97 65 49

进行4次交换后 27 38 13 76 97 65 49

完成一趟排序 27 38 13 49 76 97 65 49

Int partitiong ( int R[ ], int low, int high ) {

R[0]=R[ low ]; Pivotkey= R[ low]; While( low< high ){

While(low< high && R[high]>= Pivotkey ) high=high-1; R[ low]= R[ high];

While(low< high && R[low]<= Pivotkey ) low= low -1; R[ high]= R[ low]; }

R[low] = R[0]; }

Void QSort ( int R[ ],int low, int high ) {

if( low < high ){

p=partitiong ( R, low, high ); QSort ( R,low , p-1 ); QSort ( R, p+1, low );

} }

10.4.3 堆排序

堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。

堆的定义如下：n个元素的序列{k1，k2，…，kn}仅当满足下关系时，称之为堆。

Ki ≤ K2i 或 ki ≤ K2i+1