算法导论之插入排序

插入排序

　　输入: n 个数的一个序列 <a₁, a₂, ..., a_n> 。

　　输出: 输入序列的一个排列 <a_1^', a_2^', ..., a_n^'> , 满足 a_{1^{' ≤}} a_2^'≤...≤ an^'。

 1 INSERTION-SORT(A)
 2   
 3 for j = 2 to A.length
 4     key = A[j]
 5     // Insert A[j] into the sorted sequence A[1..j - 1]
 6     i = j - 1
 7     while i > 0 and A[i] > key
 8         A[i + 1] = A[i]
 9         i = i - 1
10     A[i + 1] = key

下面是用 C 语言对以上算法的实现：

 1 // 以下代码参考《大话数据结构》 
 2 // 对顺序表进行直接插入排序 
 3 
 4 void InsertSort (SqList *L){
 5     int i, j;
 6     for (j = 2; i <= L -> length; i++){
 7         L -> r[0] = L -> r[j];
 8         // 需将L->r[i] 插入到有序子表
 9         i = j - 1;
10         while (i  > 0 &&  L -> r[i] > L -> r[0]){
11             L->r[i + 1] = L -> r[i];
12             i = i - 1;
13         }
14         L -> r[i + 1] = L -> r[0]
15     }
16 }

声明：

　　　　最近入手算法导论第三版，大Yi巴狼特地写此系列博客以激励自己每天学习一点算法知识。仅供自己参考学习，若您能从中

　　获得帮助，大Yi巴狼也会为自己的成果感到很高兴, 毕竟本人水平有限, 如有本系列文档中有些错误对您造成不便，本人再次特地

　　说声抱歉。