第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)
{ 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）是堆
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)
{ 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）是堆
