直接插入排序。 #include <iostream> #define MAXSIZE 1000 using namespace std; typedef struct { int key; char *otherinfo; }ElemType; typedef struct { ElemType *r; int length; }SqList; void InsertSort(SqList &L) { int i,j; for(i=2;i<=
时间: 2024-03-31 13:33:12 浏览: 219
直接插入排序 选择排序 堆排序 归并排序 快速排序 冒泡排序等
5星 · 资源好评率100%
L.length;i++) { //从第二个元素开始插入排序 if(L.r[i].key<L.r[i-1].key) { L.r[0]=L.r[i]; //哨兵 L.r[i]=L.r[i-1]; for(j=i-2;L.r[0].key<L.r[j].key;j--) { //从后往前比较 L.r[j+1]=L.r[j]; //记录后移 } L.r[j+1]=L.r[0]; //插入到正确位置 } } }
以上是直接插入排序的 C++ 代码实现,使用了哨兵来简化代码。对于一个长度为n的序列,平均时间复杂度为O(n^2),最坏时间复杂度为O(n^2),空间复杂度为O(1)。
阅读全文