内部排序——选择排序

大家好，想要了解完整内部排序，可以看看我的上两篇文章

3.选择排序

选择排序分为：简单选择排序和堆排序。简单选择排序经过改进有了堆排序。

• 简单选择排序

选择排序是每一趟在 n -i+1(i= 1,2,3...n-1) 个记录中选择关键字最小的记录化作为有序序列中第 i 个记录。其中最简单的是简单选择排序。

算法：

void SelectSort(SqList &L ) {

for (i =1; i<L.length; ++i) {

j =SelectMinkey(L,i );

if (i ! = j) L.r[i] <-> L.r[i];

}// SelectSort

• 堆排序

堆：又称堆树，它是一棵特殊的完全二叉树，其中堆排序分为大堆和小堆。

小堆：树中每个结点关键字必须小于左右孩子关键字（叶子结点除外）。

大堆：树中每个结点关键字必须大于左右孩子关键字（叶子结点除外）。

例如给定关键字集合（49 38 65 97 76 13 27 49）按顺序输入构成一棵完全二叉树。

算法：

type SqList HeapType; //堆采用顺序表存储表示

void HeapAdjust (HeapType &H, int s,int m) {

rc =H.r[s] ;

for (j = 2*s; j<=m ;j* =2) {

//沿 key 较大的孩子结点向下筛选

if (j<m && LT(H.r[i].key,H.r[j+1].key)) ++j;

//j 为 key 较大的记录的下标

if(!LT( rc.key, H.r[j].key)) break;

//rc 应插入在位置 s 上

H.r[s]=H.r[i];s=j;

}

H.r[s] = rc;

}// HeapAdjust

void HeapSort (HeapType & H ) {

for (i=H.length/2; i>0;--i)

HeapAdjust(H, i,H.length);

for (i= H.length; i>1 ; --i ){

H.r[1] ← H.r[i] ;

printf(H.r[i]);

HeapAdjust( H, 1, i-1);

} //HeapSort

总结

选择排序中经常用的是堆排序，堆排序速度快，时间复杂度小，但不稳定。