文章目录
- 直接插入排序
-
- 1. 基本思想
- 2. 例子
- 3. 复杂度分析
- 4. 稳定性分析
- 5. 测试函数
- 6. 头文件部分
- 7. 实现
- 8. 测试案例
-
- main函数
- 输出结果
直接插入排序
顾名思义 直接插入排序 肯定是 插入排序
1. 基本思想
相信大家都玩过扑克牌
我们抽到一张牌的时候,都是将它插入到当前手牌的合适位置
直接插入排序也是这样的思想:
将待排序序列分成两个序列,前⾯的序列保持有序,依次选取后⾯的序列的元素,在前⾯的序列中进⾏插⼊
初始时，有序序列的⻓度为1
2. 例子
给定一个序列 [6,1,9,5,8]
3. 复杂度分析
最好情况: 在排序之前元素已经是有序了,每次只需要与前面的有序元素序列的最后一个元素进行比较,
若有n个元素则比较次数为n-1,元素的移动次数为0
时间复杂度为:O(n)
最坏情况: 即第i趟时第i个元素要和前面i个元素必须与前⾯i个元素都做排序的⽐较，并且每做⼀次就
就要做⼀次数据移动，此时的时间复杂度为O(n^2),所以直接插⼊排序的时间复杂度为O(n^2)
4. 稳定性分析
插⼊排序是在⼀个已经有序的⼩序列的基础上,⼀次插⼊⼀个元素
如果碰⻅⼀个和插⼊元素相等的，那么将会把待插⼊元素放在相等元素的后⾯
所以，相等元素的相对的前后顺序没有改变，即插⼊排序是稳定排序
5. 测试函数
这些是我找到的测试算法时间的函数 看懂即可
以后写的排序相关算法也会用这些内容
typedef int keyType;
typedef struct
{
keyType key;// 查找表中每个数据元素的关键值
void *data;// 数据的其他区域
}Element;
typedef struct
{
Element *data;// 存放查找表中数据元素的首地址
int length;// 查找表的元素个数
}SortTable;
enum sortStatus{success, failed};
void swapElement(Element *a, Element *b);// 交换元素a和元素b
SortTable *generateRandomArray(int n, int low, int high);// 产生随机数范围[low,high]
SortTable *generateLinearArray(int n, int swapTimes);// 参数顺序空间，随机交换swapTimes次 轻微乱序 整体接近有序
SortTable *copySortTable(SortTable *old);// 拷贝和old一样值的排序表
void releaseSortTable(SortTable *table); //释放表
// 排序算法函数的别名
typedef void (*sortHandler)(SortTable *);
// 测试sortName的排序算法
void testSort(const char *sortName, sortHandler sort, SortTable *table);
/* 交换a和b的元素值 */
void swapElement(Element *a, Element *b)
{
Element tmp;
memcpy(&tmp, a, sizeof(Element));
memcpy(a, b, sizeof(Element));
memcpy(b, &tmp, sizeof(Element));
}
/* 产生n个随机数的排序表，值的范围是[low, high] */
SortTable *generateRandomArray(int n, int low, int high)
{
SortTable *table = malloc(sizeof(SortTable));
if (table == NULL) {
fprintf(stderr, "sort table malloc failed!\\n");
return NULL;
}
table->length = n;
table->data = (Element *) malloc(sizeof(Element) * n);
if (table->data == NULL) {
fprintf(stderr, "element malloc failed!\\n");
free(table);
return NULL;
}
srand(time(NULL) + 1);
for (int i = 0; i < n; ++i) {
table->data[i].key = (rand() % (high – low + 1)) + low;
table->data[i].data = NULL;
}
return table;
}
/* 产生n个随机交换swapTimes次的有序顺序表 */ //轻微乱序 整体接近有序
SortTable *generateLinearArray(int n, int swapTimes)
{
SortTable *table = malloc(sizeof(SortTable));
if (table == NULL) {
fprintf(stderr, "sort table malloc failed!\\n");
return NULL;
}
table->data = malloc(sizeof(Element) * n);
if (table->data == NULL) {
fprintf(stderr, "data malloc failed!\\n");
free(table);
return NULL;
}
table->length = n;
for (int i = 0; i < n; ++i) {
table->data[i].key = i;
table->data[i].data = NULL;
}
// 在已经有序的排序表中，交换swapTimes次
srand(time(NULL) + 2);
for (int i = 0; i < swapTimes; ++i) {
int pos1 = rand() % n;
int pos2 = rand() % n;
swapElement(&table->data[pos1], &table->data[pos2]);
}
return table;
}
/* 拷贝一个排序表，使用同样的数据进行不同排序算法的测试 */
SortTable *copySortTable(SortTable *old)
{
SortTable *table = (SortTable *) malloc(sizeof(SortTable));
table->length = old->length;
table->data = malloc(sizeof(Element) * old->length);
for (int i = 0; i < old->length; ++i) {
table->data[i].key = old->data[i].key;
table->data[i].data = old->data[i].data;
}
return table;
}
/* 释放table */
void releaseSortTable(SortTable *table)
{
if (table) {
if (table->data) {
free(table->data);
}
free(table);
}
}
// 检查排序表里的数据，是否是从小到大排序
static enum sortStatus checkData(const SortTable *table)
{
for (int i = 0; i < table->length – 1; ++i) {
if (table->data[i].key > table->data[i + 1].key) {
printf("Check Sort Data Failed: %d : %d\\n", table->data[i].key, table->data[i + 1].key);
return failed;
}
}
return success;
}
/* 测试sortName的排序算法，算法通过sort传递函数名，数据以table传入 */
void testSort(const char *sortName, sortHandler sort, SortTable *table)
{
clock_t start = clock();
sort(table);
clock_t end = clock();
if (checkData(table) == failed) {
printf("%s failed!\\n", sortName);
return;
}
printf("%s cost time: %fs.\\n", sortName, (double) (end – start) / CLOCKS_PER_SEC);
}
6. 头文件部分
void insertSort(SortTable *table);
7. 实现
void insertSort(SortTable* table)
{
for (int i = 1;i < table->length;++i)
{
if (table->data[i].key < table->data[i – 1].key)
{
//用j辅助索引来找到待插入元素该放的位置
int j = i – 1;
Element tmp = table->data[i]; //这里备份是因为16行往后移的时候 会把i的值占掉
//从[0…i-1]
//找到有序区小于要插入的
while (j >=0 && table->data[j].key>tmp.key) //如果j<0就是有序区全遍历完了
{
//有序区中的 大于要插入 往后移 为后续插入腾位置
table->data[j + 1] = table->data[j];
j—;
}
//找到了 插入
table->data[j + 1] = tmp;
}
}
}
8. 测试案例
main函数
void test01()
{
int n = 10000;
// table1: n个随机数的排序表，值的范围是[0, 5000]
// table2: n个随机交换10次的有序顺序表 轻微乱序 整体接近有序
// table3: 拷贝table1中的内容
SortTable* table1 = generateRandomArray(n, 0, 0 + 5000);
SortTable* table2 = generateLinearArray(n, 10);
SortTable* table3 = copySortTable(table1);
//测试
testSort("insertSort", insertSort, table1);
testSort("Linearinsert", insertSort, table2);
testSort("shellSort", shellSort, table3); //这个是希尔排序 我们下节再写
//释放表
releaseSortTable(table1);
releaseSortTable(table2);
releaseSortTable(table3);
}
int main()
{
test01();
return 0;
}
输出结果
insertSort cost time: 0.547000s.
Linearinsert cost time: 0.001000s.
shellSort cost time: 0.002000s.
insertSort cost time: 0.580000s.
Linearinsert cost time: 0.002000s.
shellSort cost time: 0.003000s.
insertSort cost time: 0.548000s.
Linearinsert cost time: 0.002000s.
shellSort cost time: 0.002000s.
//多次测试所得耗时数值不会完全相同 会受很多因素影响
//这里就贴个三组数据
//感兴趣可以自己测试下
嘻嘻嘻嘻 直接插入排序部分到此结束😆😆
(有错误欢迎指出) (疑问也是)❤️❤️😍😍💖💖
下期更新希尔排序
