做网站编辑要会什么,道路建设网站,长沙建站宝网络科技有限公司,网站页面设计工具我们来实现上述排序
一.插入排序.
当插入第i(i1)个元素时#xff0c;前面的array[0],array[1],.,array[i-1]已经排好序#xff0c;此时用array[i的排序码与array[i-1]array[i-2].的排序码顺序进行比较#xff0c;找到插入位置即将arrayU插入#xff0c;原来位置上的元…
我们来实现上述排序
一.插入排序.
当插入第i(i1)个元素时前面的array[0],array[1],.,array[i-1]已经排好序此时用array[i的排序码与array[i-1]array[i-2].的排序码顺序进行比较找到插入位置即将arrayU插入原来位置上的元素顺序后移.
CSDN这个链接有我之前写的直接插入排序
今天我们来实现广义上的插入排序
我直接写出来会在里面写注释
void Insertsort(int* arr, int n)//arr数组n元素个数
{//我们用升序排列for (int i 0; i n-1; i)//循环n次{int end i;//将i的值赋给end方便将其数值改变而不影响循环int tmp arr[end 1];//由于升序我们要提前保存要排序的数//这里默认前i个数是已排好的即endwhile (end 0){if (arr[end] tmp)//arr[end]与arr[end1]比较{arr[end 1] arr[end];//满足条件赋值end--;//继续向前排列}else{break;//不满足条件退出循环}}arr[end 1] tmp;//将保存的数值赋给留出的位置}
}
我们排一个数组试试
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
void Insertsort(int* arr, int n)//arr数组n元素个数
{//我们用升序排列for (int i 0; i n-1; i)//循环n次{int end i;//将i的值赋给end方便将其数值改变而不影响循环int tmp arr[end 1];//由于升序我们要提前保存要排序的数//这里默认前i个数是已排好的即endwhile (end 0){if (arr[end] tmp)//arr[end]与arr[end1]比较{arr[end 1] arr[end];//满足条件赋值end--;//继续向前排列}else{break;//不满足条件退出循环}}arr[end 1] tmp;//将保存的数值赋给留出的位置}
}
void Print(int* arr, int n)
{for (int i 0; i n; i){printf(%d , arr[i]);}
}
int main()
{int arr[] { 2,4,6,8,0,1,3,5,7,9 };int sz sizeof(arr) / sizeof(arr[0]);Insertsort(arr, sz);Print(arr, sz);}
结果 当然我们也可以用降序来排
void Insertsort(int* arr, int n)//arr数组n元素个数
{//我们用升序排列for (int i 0; i n-1; i)//循环n次{int end i;//将i的值赋给end方便将其数值改变而不影响循环int tmp arr[end 1];//由于升序我们要提前保存要排序的数//这里默认前i个数是已排好的即endwhile (end 0){if (arr[end] tmp)//arr[end]与arr[end1]比较,改变,符号即可{arr[end 1] arr[end];//满足条件赋值end--;//继续向前排列}else{break;//不满足条件退出循环}}arr[end 1] tmp;//将保存的数值赋给留出的位置}
}
上题数组的结果用降序排列 我们接下来看看其时间复杂度
我们只考虑最坏的情况
假设 n1:外层1次内层1次 n2:外层2次内层最坏2次 n3:外层3次内层最坏3次 nn:外层n次内层最坏n次
因此时间复杂度为O(N*N)O(N^2); 二.插入排序进阶----希尔排序.
又叫递减增量排序算法。
思想先将整个待排元素序列分割成若干个子序列由相隔某个“增量”的元素组成的分别进行直接插入排序然后依次缩减增量再进行排序待整个序列中的元素基本有序增量足够小时再对全体元素进行一次直接插入排序
希尔排序主要分两步1.预排序 2.插入排序
预排序:分组排间隔为gap是一组。
假设gap 5 对组间隔为gap的预排序gap由大变小gap越大大的数可以越快的到后面,小的数可以越快的到前面gap越大预排完越不接近有序 gap越小越接近有序gap 1时就是直接插入排序
我们直接实现在插入排序上改
void Shellsort(int* arr, int n)
{int gap n;//将n的值赋值一份给gap便于后续对gap给值划分while (gap 1){//法一gap/2为单位gap gap / 2;//gap的值以二分之一不断划分最后得到gap1进行插入排序//gap/3为单位//gap gap / 3 1;//gap的值以三分之一不断划分最后加1得到gap1进行插入排序//gap1时进行预排序//gap1时进行插入排序for (int i 0; i n - gap; i)//in-gap:把间隔为gap的多组数据同时排{//下面操作和插入排序大体相同但注意不再时加减1而是以gap为单位int end i;int tmp arr[end gap];while (end 0){if (arr[end] tmp){arr[end gap] arr[end];end - gap;}else{break;}}arr[end gap] tmp;}}
}
继续实现上面那个数组的排序
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
void Shellsort(int* arr, int n)
{int gap n;//将n的值赋值一份给gap便于后续对gap给值划分while (gap 1){//法一gap/2为单位gap gap / 2;//gap的值以二分之一不断划分最后得到gap1进行插入排序//gap/3为单位//gap gap / 3 1;//gap的值以三分之一不断划分最后加1得到gap1进行插入排序//gap1时进行预排序//gap1时进行插入排序for (int i 0; i n - gap; i)//in-gap:把间隔为gap的多组数据同时排{//下面操作和插入排序大体相同但注意不再时加减1而是以gap为单位int end i;int tmp arr[end gap];while (end 0){if (arr[end] tmp){arr[end gap] arr[end];end - gap;}else{break;}}arr[end gap] tmp;}}
}
void Print(int* arr, int n)
{for (int i 0; i n; i){printf(%d , arr[i]);}
}
int main()
{int arr[] { 2,4,6,8,0,1,3,5,7,9 };int sz sizeof(arr) / sizeof(arr[0]);Shellsort(arr, sz);Print(arr, sz);}
结果 上面这是升序的相信降序的大家都会了。没错和插入排序改变之处相同。
接下来我们讨论其时间复杂度
gap gap / 2;// logN
//gap gap / 3 1;// 1og3N 以3为底数的对数
for (int i 0; i n - gap; i)
{// gap 1时都是预排序 接近有序// gap 1时就是直接插入排序 有序// gap很大时下面预排序时间复杂度0(N)// // gap很小时数组已经很接近有序了这时差不多也是(N)int end i;int tmp arr[end gap];while (end 0){if (arr[end] tmp){arr[end gap] arr[end];end - gap;}else{break;}}arr[end gap] tmp;
}
因此其时间复杂度为O(N*logN)平均的时间复杂度是0(N*1.3)
读者可能会想这个希尔排序是三层循环而插入排序才两层循环不可能出现其算法更优越啊
但实际上确实是希尔排序快而且快了不止一点。 假设用10万个数据我们对比发现希尔排序要少排非常多次。
InsertSort:1616ms ShellSort:12ms
这是一个相同数据检测出来两者的时间差距可见两者的差距有多大希尔牛逼 希尔排序缺点
希尔排序并不只是相邻元素的比较有许多跳跃式的比较难免会出现相同元素之间的相对位置发生变化所以希尔排序是不稳定的算法。 最后我会不间断的更新其他排序希望大家多多支持
