版本2和3间的区别

排序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. 插入排序

1.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 }

例：49，38，65，97，76，13，27，49

时间复杂度：最好情况（正序）O(n)，最坏情况（逆序）O(n²)，平均情况O(n²)

空间复杂度O(1)

稳定性：稳定

1.2. 希尔排序

2. 交换排序

基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。

2.1. 冒泡排序

将被排序的记录数组R[0..n-1]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组 R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

例：49 38 65 97 76 13 27

   1 void bubble_sort(seq_list *r) { 
   2     int i, j;
   3     int swap_flag;
   4     for(i = r->size; i > 1; i--) {
   5         swap_flag = 0;
   6         for(j = 0; j < i-1; j++)
   7             if(r->elem[j].key > r->elem[j+1].key){
   8                 elem_type temp =r->elem[j+1];
   9                 r->elem[j+1] = r->elem[j];
  10                 r->elem[j]=temp;
  11                 swap_flag = 1;
  12             }
  13         if(swap_flag == 0)
  14             return;
  15     }
  16 }

时间复杂度：最好情况（正序）O(n)，最坏情况逆序O(n²)，平均情况O(n²)

空间复杂度：O(1)

稳定性：稳定

3. 选择排序

选择排序(Selection Sort)的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。

3.1. 简单选择排序

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

例子：49、38、65、97、76、13、27

-  ⇤ ← 于2006-05-22 21:54:56修订的的版本2 → 
  大小: 3542
  编辑: czk
  备注:
+   ← 于2006-05-22 22:12:16修订的的版本3 → ⇥
  大小: 4349
  编辑: czk
  备注:
-删除的内容标记成这样。
+加入的内容标记成这样。
 行号 88:
+时间复杂度：最好情况（正序）O(n)，最坏情况逆序O(n^2^)，平均情况O(n^2^)

空间复杂度：O(1)

稳定性：稳定

== 选择排序 ==

选择排序(Selection Sort)的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。

=== 简单选择排序 ===
{{{#!cplusplus
void SelectSort(seq_list *r) {
   int i, j, k;
   for(i=0; i < r->size-1; i++){
      k = i;
      for(j = i+1; j<r->size;j++)
         if(r->elem[j].key < r->elem[k].key)
            k = j; 
      if(k!=i) { 
         elem_type temp = r->elem[i];
         r->elem[i] = r->elem[k];
         r->elem[k] = temp; 
      }
   } 
}
}}}
例子：49、38、65、97、76、13、27

"排序"版本比较