for (j=i+1;j<=n;j++) //搜索关键字最小的记录位置 if (a[j].key
{ temp=a[i]; a[i]=a[index]; a[index]=temp; } } }
简单选择排序算法简单，但是速度较慢，并且是一种不稳定的排序方法，但在排序过程中只需要一个用来交换记录的暂存单元。 9.4.2 堆排序 1. 堆排序的基本思想
堆排序是另一种基于选择的排序方法。下面我们先介绍一下什么是堆？然后再介绍如何利用堆进行排序。
堆定义：由n个元素组成的序列{k1，k2，……，kn-1，kn}，当且仅当满足如下关系时，称之为堆。ki≤k2i 或 ki≥k2i 其中i=1,2,3,... , n/2。ki≤k2i+1 kI≥k2i+1
例如序列（47，35，27，26，18，7，13，19）满足：
k1 ≥ k2 k2≥ k4 k3 ≥ k6 k4 ≥ k8 k1 ≥ k3 k2 ≥ k5 k3 ≥ k7
即对任意ki （i=1,2,3,4）有： ki≥ k2iki≥ k2i+1 所以这个序列就是一个堆。
若将堆看成是一棵以k1为根的完全二叉树，则这棵完全二叉树中的每个非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此可以看出，若一棵完全二叉树是堆，则根结点一定是这n个结点中的最小者或最大者。下面给出两个堆的示例。 如何利用堆进行排序？
从堆的定义可以看出，若将堆用一棵完全二叉树表示，则根结点是当前堆中所有结点的最小者（或最大者）。堆排序的基本思想是：首先将待排序的记录序列构造一个堆，此时，选出了堆中所有记录的最小者或最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小（或次大）的记录，以此类推，直到堆中只有一个记录为止，每个记录出堆的顺序就是一个有序序列。
2. 堆排序算法
假设当前要进行筛选的结点编号为k，堆中最后一个结点的编号为m，且a[k+1]至a[m]之间的结点都已经满足堆的条件，则调整过程可以描述为： (1) 设置两个指针i和j：
i指向当前（要筛选）的结点：i=k; j指向当前结点的左孩子结点：j=2*i;
(2) 比较当前结点的左右孩子的关键字值，并用j指向关键字值较大的孩子结点。
if (j
if (a[i].key>a[j].key) break; //结束筛选操作
else { temp=a[i]; a[i]=a[j]; a[j]=temp; //交换结点内容 i=j;j=2*i; //准备继续筛选 }
可以将交换改进为：
if (a[i].key>a[j].key) break;
else { a[i]=a[j]; i=j; j=2*i; } 堆排序的筛选算法：
void sift (DataType a,int k,int m) { i=k;；j=2*i；temp=a[i]； while (j<=m) //
{ if ( j < m && a[j].key < a[j+1].key ) j++; if ( a[i].key > a[j] .key) break； else
{ a[i]=a[j] ；i=j；j=2*i； } }
a[i] = temp； }
堆排序的完整算法。
void heapsort (DataType a, int n) { h=n/2 ; //最后一个非终端结点的编号
for ( i=h ; i>=1; i--) //初建堆。从最后一个非终端结点至根结点 sift ( a, i, n ) ;
for ( i=n ; i>1 ; i-- ) //重复执行移走堆顶结点及重建堆的操作 { temp=a[1] ; a[1]=a[i]; a[i]=temp ; sift ( a , 1 , i-1 ); } }
在堆排序中，除建初堆以外，其余调整堆的过程最多需要比较树深次，因此，与简单选择排序相比时间效率提高了很多；另外，不管原始记录如何排列，堆排序的比较次数变化不大，所以说，堆排序对原始记录的排列状态并不敏感。
在堆排序算法中只需要一个暂存被筛选记录内容的单元和两个简单变量h和i，所以堆排序是一种速度快且省空间的排序方法。堆排序是一种不稳定的。
9.5 归并排序
1． 归并排序的基本思想
归并排序是一种另一类排序方法。所谓归并是指将两个或两个以上的有序表合并成一个新的有序表。归并排序的基本思想是将一个具有n个待排序记录的序列看成是n个长度为1的有序列，然后进行两两归并，得到「n/2 个长度为2的有序序列，再进行两两归并，得到「n/4 个长度为4的有序序列，如此重复，直至得到一个长度为n的有序序列为止。 2．归并排序算法
通常，我们将两个有序段合并成一个有序段的过程称为2-路归并。 2-路归并算法
假设记录序列被存储在一维数组a中，且a[s]~a[m] 和a[m+1]~a[t] 已经分别有序，现将它们合并为一个有序段，并存入数组a1中的a1[s]~a1[t]之间。 合并过程：
(1) 设置三个整型变量k、i、j，用来分别指向a1[s...t]中当前应该放置新记录的位置，a[s]~a[m]和a[m+1]~a[t]中当前正在处理的记录位置。初始值应该为： i=s; j=m+1; k=s;
(2) 比较两个有序段中当前记录的关键字，将关键字较小的记录放置a1[k]，并修改该记录所属有序段的指针及a1中的指针k。重复执行此过程直到其中的一个有序段内容全部移至a1中为止，此时需要将另一个有序段中的所有剩余记录移至a1中。其算法实现如下： while (i<=m &&j<=t)
{ if (a[i].key<=a[j].key) a1[k++]=a[i++]; else a1[k++]=a[j++]; }
if (i<=m) while (i<=m) a1[k++]=a[i++]; else while (j<=t) a1[k++]=a[j++];
2-路归并的完整算法：
void merge (DataType a,DataType a1,int s,int m,int t){
//a[s]~[m]和a[m+1]~a[t]已经分别有序，将它们归并至a1[s]~a1[t]中 k=s; i=s; j=m+1; while(i<=m && j<=t)
{ if (a[i].key<=a[j].key) a1[k++]=a[i++]; else a1[k++]=a[j++]; }
if (i<=m) //将剩余记录复制到数组a1中 while ( i<=m) a1[k++]=a[i++]; if (j<=t)
while (j<=t) a1[k++]=a[j++]; }
2. 归并排序的递归算法
归并排序方法可以用递归的形式描述，即首先将待排序的记录序列分为左右两个部分，并分别将这两个部分用归并方法进行排序，然后调用2-路归并算法，再将这两个有序段合并成一个含有全部记录的有序段。 递归算法：
void mergesort (DataType a,DataType a1,int s,int t) { if (s==t) a1[s]=a[s];
else { m= (s+t)/2;
mergesort ( a, a2, s, m); mergesort (a, a2, m+1, t); merge (a2, a1, s, m, t);
