数据结构 |
您所在的位置：网站首页 › 数据结构中排序 › 数据结构 |
|
前言
插入排序具体有三种：直接插入排序、折半插入排序、希尔排序，陪女朋友复习数据结构，做个小总结吧。 直接插入排序这个是插入排序中最简单的一个，算法原理直接用实例来介绍： 假设原始数组是：3 1 4 2 6 2 1 6 7 将数组分成两个区域，一个是有序区域一个是无序区域，最开始初始化有序区域（用黄色表示）为第一个数，无需区域为剩下部分。 第一次：3 1 4 2 6 2 1 6 7 将无序区域第一个数与有序区域作比较，判断该数适合插入的位置，这里就是1 和 3做比较，发现1应该插入3的前面 第二次：1 3 4 2 6 2 1 6 7 同理将4和 1 3 作比较确定插入位置 第三次：1 3 4 2 6 2 1 6 7 下面几次同理 第四次：1 2 3 4 6 2 1 6 7 第五次：1 2 3 4 6 2 1 6 7 第六次：1 2 2 3 4 6 1 6 7 第七次：1 1 2 2 3 4 6 6 7 第八次：1 1 2 2 3 4 6 6 7 第九次：1 1 2 2 3 4 6 6 7 直接插入排序算法稳定性分析可以看到在直接插入排序中，我们判断插入在某个元素前面的条件是小于该值（注意不能等于），这样就不会破坏数组中两个相同数的前后位置关系，也就是说直接插入排序算法是一个稳定的算法 直接插入排序代码 void insertSort(int a[], int n) { int temp, j, k; for (int i = 1; i = 0; j--) { if (a[j] j; k--) { a[k + 1] = a[k]; } //插入 a[k + 1] = temp; } } } 算法时间复杂度分析第一部分：程序最复杂的第一部分应该是查找插入位置，也就是： if (a[j] |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |