温州企业建站程序,个人网站取什么域名好,网站建设风险管理,短视频素材大全个人主页#xff1a;Lei宝啊
愿所有美好如期而遇 前言#xff1a; 这两个排序在思路上有些相似#xff0c;所以有人觉得插入排序和希尔排序差别不大#xff0c;事实上#xff0c;他们之间的差别不小#xff0c;插入排序只是希尔排序的最后一步。 目录
前言#xff1a;…个人主页Lei宝啊
愿所有美好如期而遇 前言 这两个排序在思路上有些相似所以有人觉得插入排序和希尔排序差别不大事实上他们之间的差别不小插入排序只是希尔排序的最后一步。 目录
前言
插入排序
思路
图解
代码
希尔排序
思路
图解
代码 插入排序
思路
当我们有了一个有序的数组arr假设为升序现在向里面插入一个新数据。
我们假设这个数组有n个元素最后一个元素的下标我们记作end那么要插入的这个数下标为end1,并用tmp记下这个数的大小。
接下来如果tmp小于arr[end],那么arr[end1] arr[end]; end--, 如果tmp大于等于arr[end],那么break; arr[end1] tmp;
重复上述操作直到end 0或者break跳出 那么面对一个无序的数组我们可以将第一个元素当做有序第二个元素为新插入元素依次类推排序
图解 代码
void InsertSort(int* arr, int n)
{//i n - 2时temp arr[n - 1];for (int i 0; i n - 1; i){int end i;int temp arr[end 1];//此处画个图end小于0跳出循环while (end 0){if (temp arr[end]){//插入的值比end小end值向后移动一位arr[end 1] arr[end];end--;}else{break;}}//写在循环外的原因是如果while循环不是break出来的//会导致第一个元素值重复插入的值最后未插入进去arr[end 1] temp;}} 希尔排序
思路
希尔排序比插入排序多的就是预排序而预排序的目的就是让大的数据/小的数据更快的被排到后面去因为越接近有序的数据使用插入排序时时间复杂度越接近O(N),而我们的希尔排序最后一步等同于插入排序
图解
以代码一为例 代码
两个代码没有什么差别只是一个是一组一组排一个是并排。
代码一
void ShellSort(int* arr, int n)
{int gap n;while (gap 1){//多组预排序最后接近有序时插入排序gap / 2;//完成一趟预排序for (int j 0; j gap; j){//完成一组预排序for (int i j; i n - gap; i gap){//走一组中的一个位置的预排序int end i;int temp arr[end gap];while (end 0){if (temp arr[end]){arr[end gap] arr[end];end - gap;}else{break;}}arr[end gap] temp;}}}}
代码二
void ShellSort(int* arr, int n)
{int gap n;while (gap 1){//多组预排序最后接近有序时插入排序gap / 2;//等同于上面的希尔排序,不是分组排了而是并排for (int i 0; i n - gap; i){//走一组中的一个位置的预排序int end i;int temp arr[end gap];while (end 0){if (temp arr[end]){arr[end gap] arr[end];end - gap;}else{break;}}arr[end gap] temp;} }
}
