第9章排序 要点 1、熟练掌握各种排序方法的排序过程; 2、掌握各种排序的算法(简单插入、交换、选择法,希尔排序,快速排序,堆排序) 3、哪些排序算法是稳定排序,哪些是不稳定排序 4、各排序算法的时空性能分析。 练习题: 、填空题 1、若有一组记录(50,40,95,20,15,70,60,45,80),在进行直接插入排序时,当把第7个记 录60插入到有序表时,为寻找插入位置需比较 次;在进行直接选择排序时,第4次交 换和选择后,未排序记录(即剩下的无序表)为 利用快速排序进行递归调用的深度最 大为 进行堆排序时的初始堆的记录次序为 2、对于堆排序和快速排序来说,若初始记录接近正序或反序,则益选用 排序;若初始记录无 序,则益选用 排序。 3、从未排序序列中依次取出元素与已排序序列中的元素作比较,将其放入已排序序列中的正确位置 上,此方法称为 排序:从未排序序列中挑选元素,并将其放入已排序序列的一端,此 方法称为 排序;依次将每两个相临的有序表合并成一个有序表的排序方法叫做 排序;当两个元素比较出现反序(逆序)时就相互交换位置的排序方法叫做 每次把 待排序的元素划分为左右两个子区间,其中左区间中元素的关键字均小于等于基准元素的关键字,右 区间中元素的关键字均大于等于基准元素关键字,则此排序方法叫做 参考解答: 50,60,70,80,95495,80,70,45,15,50,60,40,20 2、堆快速 、应用题 1、设待排序的记录用无头结点单链表作为存储结构,结点的类型名为1 inklist,为一结构体类型 包括指针域next,关键字域key和其它数据域,请写出选择排序算法: void selesort( linklist*head)/head为指向表头的指针 I linklist p, g, t, max, pre, new=NULL p=*head //p指向首元结点 while(p)//当链表中还有结点 pre=nax=p;//pre与t作为前后结点的指针,在中间的循环中联动 t=p>next;//先把p所指结点当作最大的结点 while(t){if(t->key>max-key)//在余下的链表中找一个最大的 lg=pre: max=t: I t=t->next if(max=p)//若最大结点为p所指,则将结点插入new链 (a=p->next; p->next=new: new=p; p=g: 1 /否则,将max所指结点插入new链 (a->next=max->next: max->next=new new=max *head=new;/排序后的链表 2、写出在含有n个元素的堆中增加一个元素,并调整为堆的算法。(设待堆中的元素存储在一个一维 数组中,数组元素为整型(即元素值就是关键字,且为整数)
1 第 9 章 排序 要点： 1、熟练掌握各种排序方法的排序过程； 2、掌握各种排序的算法（简单插入、交换、选择法，希尔排序，快速排序，堆排序）； 3、哪些排序算法是稳定排序，哪些是不稳定排序； 4、各排序算法的时空性能分析。 练习题： 一、填空题 1、若有一组记录（50，40，95，20，15，70，60，45，80），在进行直接插入排序时，当把第 7 个记 录 60 插入到有序表时，为寻找插入位置需比较 次；在进行直接选择排序时，第 4 次交 换和选择后，未排序记录（即剩下的无序表）为 ；利用快速排序进行递归调用的深度最 大为 ；进行堆排序时的初始堆的记录次序为 。 2、对于堆排序和快速排序来说，若初始记录接近正序或反序，则益选用 排序；若初始记录无 序，则益选用 排序。 3、从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列中的正确位置 上，此方法称为 排序；从未排序序列中挑选元素，并将其放入已排序序列的一端，此 方法称为 排序；依次将每两个相临的有序表合并成一个有序表的排序方法叫做 排序；当两个元素比较出现反序（逆序）时就相互交换位置的排序方法叫做 ；每次把 待排序的元素划分为左右两个子区间，其中左区间中元素的关键字均小于等于基准元素的关键字，右 区间中元素的关键字均大于等于基准元素关键字，则此排序方法叫做 。 参考解答： 1、3 50，60，70，80，95 4 95，80，70，45，15，50，60，40，20 2、堆 快速 二、应用题 1、设待排序的记录用无头结点单链表作为存储结构，结点的类型名为 linklist，为一结构体类型， 包括指针域 next，关键字域 key 和其它数据域，请写出选择排序算法： void selesort(linklist *head) //head 为指向表头的指针 { linklist p,q,t,max,pre,new=NULL; p=*head; //p 指向首元结点 while(p) //当链表中还有结点 { pre=max=p; //pre 与 t 作为前后结点的指针，在中间的循环中联动 t=p->next; //先把 p 所指结点当作最大的结点 while(t){ if(t->key>max->key) //在余下的链表中找一个最大的 {q=pre; max=t;} pre=t; t=t->next; } if(max==p) //若最大结点为 p 所指，则将结点插入 new 链 {q=p->next;p->next=new;new=p;p=q;} else //否则，将 max 所指结点插入 new 链 {q->next=max->next; max->next=new; new=max} } *head=new; //排序后的链表 } 2、写出在含有 n 个元素的堆中增加一个元素，并调整为堆的算法。（设待堆中的元素存储在一个一维 数组中，数组元素为整型（即元素值就是关键字，且为整数）
void heapinsert(int a[, int n, int x) I int i, k=n+1 while( I t=alil if(k%2&&a[k]<a[k-1])k if(t<alk]) else break 3、若待排序的元素序列为(48,89,56,35,43,83),写出利用快速排序的方法,以第一个元素为 基准得到的一次划分的结果。 (43,35,48,56,89) 4、判断以下序列是否为堆?,如果不是,则按筛选法把它调整为堆。 (1)(100,86,48,73,35,39,42,57,66,21) (2)(12,70,33,65,24,56,48,92,86,33); (3)(103,97,56,38,66,23,42,12,30,52,6,20) 4、(1)是堆 (2)不是堆,调整后为:(92,86,56,70,33,33,48,65,12,24) (3)是堆
2 void heapinsert(int a[],int n,int x) { int i,k=n+1; a[k]=x; i=k/2; while(i) { t=a[i]; if(k%2&&a[k]<a[k-1])k--; if(t<a[k]) { a[i]=a[k]; a[k]=t; k=i; i=i/2;} else break; } 3、若待排序的元素序列为（48，89，56，35，43，83），写出利用快速排序的方法，以第一个元素为 基准得到的一次划分的结果。 （43，35，48，56，89） 4、判断以下序列是否为堆？，如果不是，则按筛选法把它调整为堆。 （1）（100，86，48，73，35，39，42，57，66，21）； （2）（12，70，33，65，24，56，48，92，86，33）； （3）（103，97，56，38，66，23，42，12，30，52，6，20）。 4、（1）是堆 （2）不是堆，调整后为：（92，86，56，70，33，33，48，65，12，24） （3）是堆