9.4 选择排序

南山隐士 2022年07月31日 43 0

要求能叙述堆、小根堆、大根堆等有关概念和定义,理解堆性质及堆与完全二叉树的关系,掌握直接选择排序和堆排序的基本思想和算法实现。针对给定的输入实例,写出堆排序的排序过程。

选择排序的基本思想是:第一趟是从n个记录中选取关键字最小的记录作为排序后序列的第一个记录,第i趟是在前面i-1个记录已有序的情况下从余下的n-(i-1)个记录中选取关键字最小的记录作为有序序列中的第i 个记录。经过n-1趟选择完成排序。

1.直接选择排序

(1)直接选择排序的步骤

直接选择排序(Simple Selection Sort)是最简单直观的选择排序算法,它的基本操作是顺序比较。设待排序的记录存储在数组元素a[1]~a[n]中,算法的步骤为:第一趟选择是用a[1]顺次与它后面的记录a[2]~a[n]比较,得到n个记录中关键字最小的记录所在的下标k1,把a[1]与a[k1]交换。第i趟选择用a[i]顺次与a[i+1]~a[n]比较,得到记录中关键字最小的记录所在的下标ki,把a[i]与a[ki]交换……,直到i=n-1为止。

(2)直接选择排序的算法实现

【算法9-5】直接选择排序算法

void selsort(NODE a[],int n)

/对a[1],a[2],...,a[n]中的记录进行直接选择排序/

{

int i,j,k;

NODE temp;

for(i=1;i<=n-1;i++) /共进行n-1趟选择/

{

k=i;                  /*k用作记录第i趟中最小关键字值记录的下标*/

for(j=i+1;j<=n;j++)        /*顺序与后面记录的关键字比较*/

  if(a[j].key

if(i!=k)               /*把第i趟选择的最小关键字值的记录与第i个记录对换*/

{

  temp=a[i];

  a[i]=a[k];

  a[k]=temp;

}

}

}

直接选择排序算法与冒泡法排序算法相比,减少了记录间的交换次数,但其时间复杂度仍为O(n2),它是一个稳定排序。

2.堆排序

堆排序(Heap Sort)是利用称为“堆”的结构所具有的性质,从堆中逐次得到待排序记录中关键字最小(最大)的记录,来完成排序。

(1)堆的定义及性质

1 堆的定义

堆的定义如下:一个由n个记录的线性序列(R1,R2,…,Rn),其相应的关键字序列为(K1,K2,…,Kn),若满足如下条件:

则上述线性序列称之为堆。

本节只讨论满足上面左式的堆,即小根堆。

2 堆与特殊性质的完全二叉树的对应

若用一维数组存放堆,并把它看成是一棵完全二叉树的顺序存储表示,这样一个堆就对应一棵完全二叉树,树中任一个非叶子结点所对应的记录的关键字均不大于(小于等于)其左、右孩子结点对应记录的关键字的值。

例如,满足堆条件的关键字序列为{14,40,30,50,80,65,50,100 },它对应的完全二叉树如图9 -3所示。


图9‑­­­3 堆的二叉树表示

显然,14<40,14<30;40<50,40<80;30<65,30<50;50<100,符合堆的定义,因而针对一棵完全二叉树,通过判断该二叉树中任意一个非叶结点所对应记录的关键字是否均小于其左、右孩子结点对应记录的关键字的值,来判断它是否为堆。

3 堆的性质

对于小根堆,具有如下性质:

a.根结点是完全二叉树所有结点对应的记录中关键字最小的。

b.树中任何一棵子树也对应一个子堆。

(2)堆排序的基本思想

对一组待排序的有n个记录的记录序列,按照它们的关键字的大小构造一个堆,输出堆顶记录,对剩余的n-1个记录序列再调整为一个新堆,输出堆顶记录……直到输出第n 个记录。

通过以上分析可以把堆排序归纳为以下两种操作:

1.如何将一个无序的记录序列构造成一个初始堆。

2.如何将一个堆逐次取走堆顶元素(记录)后,将剩余记录重新调整成为一个新堆。

(3)筛选算法及算法步骤

筛选算法:在一棵完全二叉树中,若根结点的左右子树都分别对应一个堆, 通过一系列自顶向下的调整步骤,使该二叉树对应一个堆。自顶向下的调整过程称为筛选。筛选算法也可针对完全二叉中的某一棵子树。

算法步骤如下:

1.设一个无序的记录序列已建成一个堆,设堆中有n个记录,输出堆顶元素,以堆中最后一个记录取代。n-1个记录已不是堆,但左右子树仍为堆。

2.堆顶记录的关键字与左、右子树根结点记录关键字的较小者比较,若大于较小者,堆顶记录与较小者交换。

3.交换后,若破坏了左或右子堆,则对相应子树进行上述同样处理,直到建成n-1个记录的堆。

4.对n-1个记录的堆,重复上述①、②、③的操作,直至输出全部记录,得到n个记录由小到大的有序序列。

图9-4是输出堆顶元素后调整并构造新堆的过程。


图9‑­­­4 输出堆顶元素后并调整成新堆的过程

(4)利用筛选法建立堆

利用“筛选”过程,很容易完成对一个无序的记录序列建成一个堆,建堆过程可以归结为一个自下至顶建立子堆,子堆由小到大的反复“筛选”过程。

具体做法是:

1.把将要排序的序列看成一棵完全二叉树。

2.从最后一个非叶结点(序号 k=n/2)开始,依次取结点k,k-1,…,直到第一个结点,逐次以每一个结点作为它的左,右子堆的根结点进行“筛选”,就完成了建堆的过程。

例如关键字序列{40,80,65,100,14,30,55,50}如图9-5所示。


图9-5 建堆过程

(5)筛选算法及堆排序算法

【算法9-6】 筛选算法

void heapshift(NODE a[],int i,int n)

/设记录序列存放在a[1],...a[n]中,其中a[i],...a[n]中存放的记录除a[i]外,其它记录的关键字的序列满足堆的条件,对a[i]进行筛选,使a[i],...,a[n]中的记录的关键字序列成为堆/

{

NODE temp;int j;

temp=a[i]; /保存待筛选的根结点/

j=2*i ; /根结点的左儿子的下标(序号)/

while(j<=n) /最多调整到最后一个非叶结点/

{

if(j+1<=n&&a[j].key>a[j+1].key)

  j++;          /*若存在右儿子,则使j指向左右儿子中记录关键字较小者*/

if(temp.key>a[j].key)

{

  a[i]=a[j];      /*把较小的子结点的记录调整到它的父结点的位置*/

  i=j;          /*i是被调整了的子树的根的下标,准备对子树进行筛选*/

  j=2*i;         /*j是子树根结点的左儿子的下标*/

}

else

  break;         /*已经满足堆的条件,筛选结束*/

}

a[i]=temp; /原根结点的记录筛选到位/

}

【算法9-7】 堆排序

void heapsort(NODE a[],int n)

/对存放在a[1]--a[n]中的序列进行堆排序/

{

int i;

NODE temp;

for(i=n/2;i>=1;i--)

heapshift(a,i,n);           /*从最后一个非叶结点开始从后向前筛选建堆*/

for(i=n;i>1;i--)

{

temp=a[1];a[1]=a[i];a[i]=temp;  /*将最小值与当前筛选序列的最后一个元素互换*/

heapshift(a,1,i-1);         /*在a[1]-a[i-1]之间继续筛选*/

}

}

堆排序的时间复杂度为O(log2n)是一种不稳定的排序方法.算法中堆顶元素依次放到数组元素a[n],a[n-1],…,a[1],按记录关键字由大到小排好序,不需要为输出的记录另外开辟存储空间。

想一想:如果只要求得到一个关键字序列中前k个最小元素的的排序序列,最好采用什么排序方法,为什么?

解题分析:

采用堆排序最合适。因为在其他方法中,一般都要等到最后才能确定各元素的位置,但对于堆排序,在未结束全部排序前,可以有部分排序结果。当输出对顶元素后,可将剩余元素再调整成堆。因此要想得到前面长度为k的部分序列,一般采用堆排序。

Last Updated: 2022/07/31 23:27:22
9.5 归并排序 9.3 交换排序