购物网站建设需求模板下载,站长音效,购买网站设计制作,校园网站如何建立要考数据结构了#xff0c;赶紧来复习一波排序算法 文章目录一、直接插入排序二、希尔排序一、直接插入排序
直接上主题 插排#xff0c;揪出一个数#xff0c;插入到原本已经有序的数组里面#xff0c;如数组有n个数据#xff0c;从0~n下标依次排列#xff0c;先从左往…要考数据结构了赶紧来复习一波排序算法
文章目录一、直接插入排序二、希尔排序一、直接插入排序
直接上主题 插排揪出一个数插入到原本已经有序的数组里面如数组有n个数据从0~n下标依次排列先从左往右依次排序每一个待排序它的左边都已经是有序的然后这个数揪出来插入它左边已经有序的数组中其实它需要先与它左边的相比较比左边的数小才插入进去如果这个数都比它左边的数要大了就不用再插入了就呆在原本位置不变再往右排重复这样操作直到将所有排好序。 其实就像体育课或者军训按高矮次序排列一样。 第一个可以先不动然后第二个与前面比较如果前面一个比他高。那么第一个就往后面走一位原先的第二位再与前面比较但是这会发现他前面已经没人了都比完了都没有发现比他矮的那么他就在第一个位置站着。这会轮到第三个他发现他比第二个要小,那么原来第二个位置上的人跑到第三个位置上然后原本第三个位置上的那个人再与第一个比较发现比第一个高这会他就站在第一个的后面他这一轮就结束了轮到第四个、第五个一直到一列排完。 可以发现每个人排序停止条件是要么比较完了都没有发现比他小的那么他就是最小的呆在第一位要么就是比较时发现有比他矮的那么他就站在比他矮的那个后面。当然体育课上排列自然不是这样排的都是看一眼哪些高哪些矮就先站好然后最后再排但是其实思想也是插入排序。 可以发现6个数字但是只比较了五趟因为第一个就是有序的所有不用比较 好了上代码了
#includestdio.hvoid Insertsort(int* arr, int sz)
{for (int i 0; i sz - 1; i){int end i;int tmp arr[end 1];//[0,end]有序end1位置的值插入[0,end]让[0,end1]有序while (end 0){if (arr[end] tmp)//tmp比他前面的小那么end就往左边走{arr[end 1] arr[end];end--;}//直到遇见比其小的tmp就在end后面了//这里结束条件有两个//第一它前面的所有都比它大那么它插在第一个//第二tmp在中间时遇见比其小的那么就插在比它小的后面也就是end后面else{break;}}arr[end 1] tmp;//在end后一位插入}
}int main()
{int a[] { 9,6,4,7,1,2 };int sz sizeof(a) / sizeof(a[0]);Insertsort(a, sz);for (int i 0; i sz; i){printf(%d , a[i]);}return 0;
}最好的情况就是原本就有序的其时间复杂度为O(n),因为要遍历一遍。它的时间复杂度为O(n^2),考虑最坏的那一种情况逆序要求我们正序输出 二、希尔排序 而希尔排序其实思想是基于直接插入排序上升华的,原理和直接插入排序差不多 思想先将数组进行预排序让数组接近有序最后再直接插入排序 预排序是如何排的分组排。 分多组间隔为gap的为一组假设gap最开始为数组长度 gap n因为gap越大数组中大的值能更快的到后面小的值能更快的到前面 但是在分组排的过程中gap不会一成不变的当gap1 时就是直接插入排序了因此我们将gap每次除以2或者除以3但是除3要使其1假设gap n6,gap gap/3 2,2/3!1,所有要加1保证最后一次一定为一因为最后进行直接插入排序 gap 4 gap 2 经过预排大的数更快的跳到后面小的数更快的跳到前面 注意gap越大越不接近有序gap越小越接近有序gap 1时就是直接插入排序 上代码 //希尔排序
#includestdio.hvoid Sheelsort(int* a, int sz)
{int gap sz;while (gap 1){gap / 2;//注意越界的情况//把间隔为gap的数据排序for (int i 0; i sz - gap; i){int end i;int tmp a[end gap];//将后一个数保存到tmp,其实和直接插入排序类似只不过这里是endgap,//因为要与间隔为gap比较//直接插入排序是与它后面一个比较这里是gap罢了while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;//往前跳跃gap,}else{break;}}a[end gap] tmp;//在end的gap位置放tmp,其实就是将直接插入排序的1换成了gap}}
}int main()
{int arr[] { 9,8,7,6,5,4,3,2,1 };int sz sizeof(arr) / sizeof(arr[0]);Sheelsort(arr, sz);for (int i 0; i sz; i){printf(%d , arr[i]);}return 0;
} 希尔时间复杂度 这个循环为lon^n次 这个循环近乎n次 所有总的近乎是nlon^n 时间复杂度也就是O(nlog^n), gap/3时,为nlon3^n
