数据结构 |
您所在的位置：网站首页 › 空间复杂度分析方法包括哪些 › 数据结构 |
数据结构
|
前言
插入排序具体有三种：直接插入排序、折半插入排序、希尔排序，陪女朋友复习数据结构，做个小总结吧。 直接插入排序这个是插入排序中最简单的一个，算法原理直接用实例来介绍： 假设原始数组是：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 if (a[j] a[k + 1] = a[k]; } //插入 a[k + 1] = temp; } } } 算法时间复杂度分析第一部分：程序最复杂的第一部分应该是查找插入位置，也就是： if (a[j] //为a[i]在前面的a[0...i-1]有序区间中找一个合适的位置 int left = 0, right = 0; for (int p = 0; p int m = (left + right) / 2; if (a[m] > a[i]) right = m - 1; else left = m + 1; } } j = right; printf("%d\n", right + 1); //如找到了一个合适的位置 if (j != i - 1) { //将比a[i]大的数据向后移 int temp = a[i]; for (k = i - 1; k > j; k--) a[k + 1] = a[k]; //将a[i]放到正确位置上 a[k + 1] = temp; } } } 折半插入排序算法稳定性分析折半插入的话稳定性也很好分析，会影响稳定性的地方就是查找插入有序区域位置的这个地方，那么和直接插入排序一样，只要判断插入某个位置前是小于该值（不可等于）就不会破坏稳定性。 折半插入排序时间复杂度分析其实吧，他的时间复杂度很好分析的，折半查找的时间复杂度是O(log2n)，然后折半查找的外层执行时n次，所以整个程序第一部分查找插入位置的时间复杂度是O(nlog2n)。 然后程序第二部分的数据挪动上是没有变化的，所以时间复杂度是O(n^2). 所以整个程序的时间复杂度是O(n^2)。 折半插入排序总结稳定性：稳定 时间复杂度：O(n^2) 希尔排序对于直接插入排序我们知道，主要影响时间复杂度的是数据的挪动，那我们就可以得出结论，如果原始数组是一个比较小的数组或者原始数组它的有序性非常高，那么他的算法速度就会非常的快，因此希尔排序也就是利用了这种思想。 一个很长的数组，我们可以将其分组处理这里我们也直接用例子说明： 第一次以步长为数组长一半分组 第一次：3 7 4 2 6 2 1 6，步长 8 / 2 = 4 分组结果： 第二次步长为上一次步长一半 第二次：3 2 1 2 6 7 4 6，步长为4 / 2 = 2 分组结果： 第三次步长为上一次步长一半 第三次：1 2 3 2 4 6 6 7，步长为2 / 2 = 1 分组结果： |
每个分组进行插入排序： 3 2 1 2 6 7 4 6 这时要注意了，两个2的前后位置发生了变化，说明这个算法不稳定。
每个分组进行插入排序： 1 2 3 2 4 6 6 7
每个分组进行插入排序： 1 2 2 3 4 6 6 7【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |