顺序表算法

顺序表算法

【顺序表算法】设顺序表 A，元素的个数是 n，没有重复。如果 A 中前 k 个元
素有序，后 n-k 个元素有序，设计一个算法使得整个顺序表有序，要求算法的空
间复杂度为 O(1)

#include 
#include
#define ElemType int 
#define Status int
#define MaxSize 20
//顺序表数据结构
typedef struct
{ElemType data[MaxSize];int length, listsize;
}SeqList;//插入元素
void ListInsert(SeqList & L, int i, ElemType e)
{for (int j = L.length - 1; j >= i; j--)L.data[j + 1] = L.data[j];++L.length;L.data[i] = e;
}//删除元素
void Delete(SeqList & L, int i)
{for (int j = i; j <= L.length; j++)L.data[j] = L.data[j + 1];--L.length;
}//输出函数
void PrintList(SeqList & L)
{printf("顺序表整体有序化：\n");//printf("\n");for (int i = 0; i < L.length + 1; i++){printf("%d", L.data[i]);}
}//排序函数,这里是对已知顺序表进行排序操作
void Sort(SeqList & La)
{int flag = 0;for (int i = 0; i < 4; i++){int Lb2 = La.data[6 + i];//printf("输出得到的Lb2 的值：%d\n", Lb2);for (int j = flag; j < La.length; j++){if (Lb2 < La.data[j]){ListInsert(La, j, Lb2);//printf("ok\n");break;}flag = j;//printf("输出flag的值：%d\n", flag);continue;}//printf("删除的是：%d\n", La.data[7 + i]);Delete(La, 7 + i);//PrintList(La);printf("\n");}PrintList(La);
}
//整体有序化，找到一个数的插入位置并插入后然后再删除
void SortAll(SeqList & La)
{int flag = 0;int Lb1 = La.data[5];if (Lb1 < La.data[0]){ListInsert(La, 0, Lb1);Delete(La, 6);//PrintList(La);//printf("\n");Sort(La);}
}int main()
{SeqList La = { {1,2,4,7,8,0,3,5,6,9 },10 };SortAll(La);return 0;
}

运行结果示例：

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！