网站建设?首选百川互动,完成网站开发需要什么样技术,wordpress 公告插件,网站功能需求用什么做#x1f497; #x1f497; 博客:小怡同学 #x1f497; #x1f497; 个人简介:编程小萌新 #x1f497; #x1f497; 如果博客对大家有用的话#xff0c;请点赞关注再收藏 #x1f31e; 什么是插入排序 有一个已经有序的数据序列#xff0c;要求在这个已经排好的数… 博客:小怡同学 个人简介:编程小萌新 如果博客对大家有用的话请点赞关注再收藏 什么是插入排序 有一个已经有序的数据序列要求在这个已经排好的数据序列中插入一个数但要求插入后此数据序列仍然有序这个时候就要用到一种新的排序方法–插入排序法 好比可以用打牌时对摸起的牌根据牌的点数来对其进行插入排列来描述。 实现思想 当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移。 例如 有一个有序区间选其中一个数插入其中这个数依次比较如果匹配失败则换到下一个数比较。 插入排序的时间复杂度 时间复杂度是O(n^2) 在最坏情况下逆序需要每个数轮流插入 根据等差数列 123…n-1 所以时间复杂度是O(n^2) 在最好情况下只需要轮一遍 所以时间复杂度为O(n^2) 插入排序的稳定性 稳定性意思是两个元素之间的相对位置没有改变 如 44 与 44 相等 44在左 44在右插入排序之后 44 仍在左 44 仍在右这两个元素的相对位置没有改变。 代码实现
#include stdio.h
void InsertSort(int* arr, int n)
{for (int i 0; i n - 1; i){int end i;int tmp arr[end 1];while (end 0){if (tmp arr[end]){arr[end 1] arr[end];end--;}else{break;}}arr[end 1] tmp;}}int main()
{int arr[] { 1,2,4,5,6,7,8,9,3 };int n (sizeof(arr) / sizeof(arr[0]));InsertSort(arr, n);for (int i 0; i n; i){printf(%d , arr[i]);}return 0;
}插入排序的优化——希尔排序
什么是希尔排序 希尔排序又称缩小增量排序它通过比较相距一定间隔的元素来进行各趟比较所用的距离随着算法的进行而减小直到只比较相邻元素的最后一趟排序为止。 通俗大意是:把原本一组的数组间断性分为几个数组在对已经分完的数组进行插入排序。 希尔排序的时间复杂度及稳定性 因为希尔排序的时间复杂度不好计算因为gap的取值 方法很多导致很难去计算。 时间复杂度;O(logNN)或者Olog3NN 稳定性不稳定 实现思想 先进行预排序让数组接近有序等到与排序之后 数组大多是有序的状态大致上是有序数组可进行插入排序。 void ShellSort(int* arr, int n)
{int gap n;while (gap 1){gap gap / 3 1;//gap1时是预排列 gap1时相当有序排列for (int i 0; i n - gap; i gap)//把间隔为gap的元素进行插入排序{int end i;int tmp arr[end gap];while (end 0){if (tmp arr[end]){arr[end gap] arr[end];end - gap;}else{break;}}arr[end gap] tmp;}}
}int main()
{int arr[] { 1,2,4,5,6,7,8,9,3 };int n (sizeof(arr) / sizeof(arr[0]));InsertSort(arr, n);for (int i 0; i n; i){printf(%d , arr[i]);}return 0;
}
