#include <stdio.h>
#define MAXSIZE 30
typedef int KeyType;
typedef int otherType;
typedef struct{
KeyType key;
otherType other;
}RecordType;
void straightInsertSort(RecordType R[],int n){
int i,j;
RecordType temp;
//第一个元素是有序的
i = 2;
for(i=2;i<=n;i++){
temp = R[i];
for(j = i - 1;temp.key < R[j].key;j--)
R[j+1] =R[j];
R[j+1] = temp;
}
}
int main(){
RecordType R[MAXSIZE];
int n = 5;
int i;
for(i=1;i<=n;i++){
R[i].key = 22 - 2 * i;
}
straightInsertSort(R,5);
for(i=1;i<=n;i++){
printf("%d ",R[i].key);
}
return 0;
}
算法解析:
核心代码段:
RecordType temp;
//第一个元素是有序的
i = 2;
for(i=2;i<=n;i++){
temp = R[i];
for(j = i - 1;temp.key < R[j].key;j--)
R[j+1] =R[j];
R[j+1] = temp;
}
实例描述:
待排序数列:46 58 15 45 90 18 10 62
算法核心:取得数列的第a[i]个元素当成temp,已知有序的前i-1个元素的子数列,从后向前和子序列的值进行比较,若temp的key值不小于子序列的第j个元素的key值时,此趟插入结束,把temp放在子序列的第j+1个位置上。
直接插入的关键在于两步:
1 和有序子序列比较,而且是从后往前,若temp的key值小,则往前走,并将比较过的元素向后挪一个位置。
2 当temp的key值不小于当前比较的元素key值时,比较结束,把temp放在子序列的第j+1个位置上(因为j--仍在起作用)。
直接插入排序是稳定排序,时间复杂度为O(n^2),空间复杂度为O(1)
分享到:
相关推荐
直接插入排序算法。 2.简单选择排序。 3.希尔排序。 4.归并排序。5.快速排序。分别对交换次数,比较次数,移动次数,时长,时间复杂度进行性能比较。给出十万到百万级数据量的统计结果。以c语言控制台画出的表格形式...
编写直接插入排序、希尔排序、冒泡排序、快速排序、选择排序。
各种排序方法,直接插入 拆半插入 表插入 哈希排序 起泡排序 快速排序 堆排序 归并排序 基数排序等各种排序的方法和对比分析。很有参考价值啊!
8.2.1 直接插入排序 209 8.2.2 折半插入排序 211 8.2.3 希尔排序 212 8.3 交换排序 214 8.3.1 冒泡排序 215 8.3.2 快速排序 216 8.4 选择排序 219 8.4.1 简单选择排序 219 8.4.2 堆排序 221 8.5 ...
直接插入排序(Insert_sort) 表插入排序(内含插入(Ins_Tsort) 重排(Arrange)两个算法) 起泡排序(BubbleSort) 简单选择排序(SelectSort) (2)复杂排序法 堆排序(HeapSort) 快速排序(QuickSort) ...
9.2.1 直接插入排序 9.2.2 折半插入排序 9.2.3 希尔排序 9.3 交换排序 9.3.1 冒泡排序 9.3.2 快速排序 9.4 选择排序 9.4.1 简单选择排序 9.4.2 堆排序 9.5 归并排序 9.6 基数排序 9.7 内部排序总结 9.8...
*5.6 C++处理字符串的方法——字符串类与字符串变量 5.6.1 字符串变量的定义和引用 5.6.2 字符串变量的运算 5.6.3 字符串数组 5.6.4 字符串运算举例 习题 第6章 指针 6.1 指针的概念 6.2 变量与指针 6.2.1 定义...
2. 直接插入排序 63 3. 折半插入排序 64 4. 希尔排序(缩小增量排序) 64 5. 起泡排序 65 6. 快速排序 66 7. 简单选择排序 67 8. 堆排序 68 9. 归并排序 71 10. 基数排序 72 11. 各种排序方法比较 73
可我找不到任何方法来声明这样的函数——感觉我需要一个返回指针的函数,返回的指针指向的又是返回指针的函数……,如此往复,以至无穷。 12 数组大小 13 1.23 能否声明和传入数组大小一致的局部数组,或者由...
2.4 直接插入排序 2.5 选择排序 2.6 冒泡排序 2.7 希尔排序 2.8 快速排序 第3章 常用的算法思想 3.1 什么是算法 3.2 算法的分类表示及测评 3.2.1 算法的分类 3.2.2 算法的表示 3.2.3 算法性能的测评 3.3 穷举法思想...
可我找不到任何方法来声明这样的函数——感觉我需要一个返回指针的函数,返回的指针指向的又是返回指针的函数……,如此往复,以至无穷。 数组大小 1.23 能否声明和传入数组大小一致的局部数组,或者由其他参数...
*5.6 C++处理字符串的方法——字符串类与字符串变量 5.6.1 字符串变量的定义和引用 5.6.2 字符串变量的运算 5.6.3 字符串数组 5.6.4 字符串运算举例 习题 第6章 指针 6.1 指针的概念 6.2 变量与指针 6.2.1 定义...
13.1.1 直接路径插入 360 13.1.2 多表插入 363 13.1.3 条件插入 364 13.1.4 DML错误日志 364 13.2 UPDATE 371 13.3 DELETE 376 13.4 MERGE 380 13.4.1 语法和用法 380 13.4.2 性能比较 383 13.5 小结 385 ...
9.8 直接基类和间接基类 9.9 在派生类中使用构造函数和析构函数 9.10 将派生类对象隐式转换为基类对象 9.11 关于继承的软件工程 9.12 复合与继承的比较 9.13 对象的“使用”关系和“知道”关系 9.14 实例研究...
9.8 直接基类和间接基类 9.9 在派生类中使用构造函数和析构函数 9.10 将派生类对象隐式转换为基类对象 9.11 关于继承的软件工程 9.12 复合与继承的比较 9.13 对象的“使用”关系和“知道”关系 9.14 实例研究...
简单来说是本身可视为电子化的文件柜——存储电子文件的处所,用户可以对文件中的数据运行新增、截取、更新、删除等操作。 常见的数据模型 1. 层次结构模型: 层次结构模型实质上是一种有根结点的定向有序树,IMS...