直接插入排序CC++代码实现

举例：

算法属性：

时间复杂度为O(n^2) 空间复杂度为O(1) 稳定排序。 当初始记录无序，n较大时，此算法时间复杂度较高，不宜采用。

代码如下：

#include<stdio.h> #define MAXSIZE 20 typedef int KeyType; typedef int InfoType; //记录类型 typedef struct { KeyType key; InfoType otherinfo; }RedType; //顺序表类型 typedef struct { RedType r[MAXSIZE + 1]; //r[0]闲置或作哨兵 int length; //顺序表长度 }SqList; //直接插入排序 void InsertSort(SqList &L) { int i, j; for (i = 2; i <= L.length; ++i) { L.r[0] = L.r[i]; j = i - 1; while (L.r[0].key < L.r[j].key) //向后移动 { L.r[j + 1] = L.r[j]; j--; } L.r[j + 1] = L.r[0]; } } //打印排序结果 void println(SqList L) { for (int i = 1; i <= L.length; i++) { printf("%d, ", L.r[i].key); } printf("\n"); } int main() { SqList L; L.r[1].key = 5; L.r[2].key = 8; L.r[3].key = 1; L.r[4].key = 4; L.r[5].key = 3; L.length = 5; InsertSort(L); println(L); }

运行结果：