排序sort

所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确切定义如下：

• 输入：n个记录R1，R2，…，Rn，其相应的关键字分别为K1，K2，…，Kn。
• 输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内部排序(简称内排序)；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。

当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。

在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。

排序算法性能评价

• 所需的辅助空间:若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间是O(1).
• 执行时间:关键字之间的比较次数和记录的移动次数。执行时间依赖于问题的规模，还可能依赖输入实例中数据的状态。

   1 typedef int key_type;
   2 typedef struct{ //记录类型
   3     key_type key; //关键字项
   4     info_type otherinfo; //其它数据项，类型InfoType依赖于具体应用而定义
   5 }record_type;
   6 typedef record_type elem_type;
   7 typedef struct  {
   8     elem_type  elem[MAXSIZE];
   9     int size;
  10 }seq_list;

1. 插入排序

假设待排序的记录存放在数组R[0..n-1]中。初始时，R[0]自成1个有序区，无序区为R[1..n-1]。从i=1起直至i=n-1为止，依次将R[i]插入当前的有序区R[0..i-1]中，生成含n个记录的有序区。

   1 void insert_sort(seq_list *r) {
   2     int i, j;
   3     for(i = 1; i<r->size; i++) {
   4         elem_type e = r->elem[i];
   5         for( j = i-1; j >= 0; j--) {
   6             if(r->elem[j].key < r->elem[i].key)
   7                 break;
   8             r->elem[j+1] = r->elem[j]; 
   9         }
  10         r->elem[j+1] = e;
  11     }
  12 }