宝安led行业网站建设,wordpress搭建公司网站,做网站付款会有凭证吗,氧os哪个网站做的最好目录
前言#xff1a;
插入排序 原理图
代码实现
分析总结
二分法插入排序
代码实现 前言#xff1a; 嗨嗨^_^#xff0c;米娜桑#xff0c;今天我们继续学习排序算法中的插入排序#xff0c;激不激动#xff0c;兴不兴奋呢#xff01;好了废话不多说#xff0c;…目录
前言
插入排序 原理图
代码实现
分析总结
二分法插入排序
代码实现 前言 嗨嗨^_^米娜桑今天我们继续学习排序算法中的插入排序激不激动兴不兴奋呢好了废话不多说下面请看正文
插入排序 插入排序一般也被称为直接插入排序。对于少量元素的排序它是一个有效的算法 。插入排序是一种最简单的排序方法它的基本思想是将一个记录插入到已经排好序的有序表中从而一个新的、记录数增1的有序表。在其实现过程使用双层循环外层循环对除了第一个元素之外的所有元素内层循环对当前元素前面有序表进行待插入位置查找并进行移动。 原理图 初始数组如下所示
第一次拿到第一个数字因为第一个数字不存在顺序无法进行比较所以不需要进行相关的操作 第二次拿到第二个数字 1 与前面的数字进行比较发现6比1大那么就进行数字交换如下图所示 第三次拿到数字9发现9比前面的两个数字都要大那么就保持位置不变继续往后看。 第四次拿到数字2此时发现2比9小比6小比1大那么就把2插入到1和6之间6和9依次向后移动一位。 第五次拿到数字4此时把数字4插入到2和6之间同样的6和9依次往后移动一位。 第六次拿到数字8此时8比9小那么就插入到9的前面即可9向后移动一位 第七次拿到12发现12比前面已排序好了的数字都要大那么位置不变。 第八次拿到10此时10比12小比9大那么就插入到9和12之间12向后移动一位。 看这样就完成了排序了
动态图展示 代码实现
#includestdio.h
#includestdlib.h
#includestring.h
#includetime.h//直接插入
void insert_sort(int* n, int length) {for (int i 0; i length; i) {int temp n[i];for (int j i - 1; j 0; j--) {if (n[j] temp) {n[j 1] n[j];n[j] temp;}}}}
int main() {int array[10];srand((unsigned)time(0));for (int i 0; i 10; i) {array[i] rand() % 20;}for (int i 0; i sizeof(array) / sizeof(int); i) {printf(%d , array[i]);}printf(\n排序后);insert_sort(array, sizeof(array) / sizeof(int));for (int i 0; i sizeof(array) / sizeof(int); i) {printf(%d , array[i]);}
}
//输出结果
//9 16 13 4 8 12 2 0 7 2
//排序后0 2 2 4 7 8 9 12 13 16
分析总结
时间复杂度 最好情况就是全部有序此时只需遍历一次最好的时间复杂度为O ( n )如果完全逆序的话那么时间复杂度就会变为O(n^2),直接翻倍。所以时间复杂度为O(n^2) 。 空间复杂度 这里没有去开辟空间空间是一个常量所以空间复杂度是On. 稳定性 遇到相同大小元素过程中依然是插入到相同元素的前边相对位置没有发生改变所以稳定性好。 二分法插入排序 二分法插入排序是对插入排序的代码优化整体的实质上还是插入排序时间复杂度依然是不会改变的On^2,当n较大时,总排序码比较次数比直接插入排序的最坏情况要好得多,但比其最好情况要差。同样的二分法插入排序是稳定的。 代码实现
#includestdio.h
#includestdlib.h
#includestring.h
#includetime.h
//二分法插入排序
void insert_bin_sort(int *n,int length) {int left, right, mid;for (int i 1; i length; i) {left 0;right i - 1;while (left right) {mid (left right) / 2;if (n[mid] n[i]) {right mid - 1;}else{left mid 1;}}int temp n[i];for (int j i; j left; j--) {n[j] n[j - 1];}n[left] temp;}
}
int main() {int array[10];srand((unsigned)time(0));for (int i 0; i 10; i) {array[i] rand() % 20;}for (int i 0; i sizeof(array) / sizeof(int); i) {printf(%d , array[i]);}printf(\n排序后);insert_bin_sort(array, sizeof(array) / sizeof(int));for (int i 0; i sizeof(array) / sizeof(int); i) {printf(%d , array[i]);}
}
//输出结果
//15 0 15 3 5 7 9 6 12 14
//排序后0 3 5 6 7 9 12 14 15 15
以上就是今天的全部内容了我们下一期再见
分享一张壁纸
