网站备案代理公司,极端页面 装修wordpress 主题,深圳场站建设发展有限公司,有什么网站专门做美食的吗文章目录 前言直接插入排序基本思想特性总结代码实现 希尔排序算法思想特性总结代码实现 前言
本博客插入排序动图和希尔排序视频参考大佬java技术爱好者#xff0c;如有侵权#xff0c;请联系删除。
直接插入排序
基本思想
直接插入排序是一种简单的插入排序法#xff… 文章目录 前言直接插入排序基本思想特性总结代码实现 希尔排序算法思想特性总结代码实现 前言
本博客插入排序动图和希尔排序视频参考大佬java技术爱好者如有侵权请联系删除。
直接插入排序
基本思想
直接插入排序是一种简单的插入排序法其基本思想是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。 实际中我们玩扑克牌时就用了插入排序的思想 当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移。
特性总结
直接插入排序的特性总结
元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定
代码实现
#includestdio.h//直接插入排序
//时间复杂度最好为O(N) -- 顺序有序,最坏为O(N^2) -- 逆序,空间复杂度为O(1)
void insertSort(int* a, int n)
{for (int i 1; i n; i){int end i - 1, tmp a[i];//单趟排序,[0,end]有序插入tmpwhile (end 0)//从后向前比较{if (a[end] tmp)a[end 1] a[end--];else break;}a[end 1] tmp;//两种情况a[end]tmp以及tmp最小}for (int i 0; i n; i){printf(%d , a[i]);}
}int main()
{int arr[] { 1,2,-9,-6,8,9,4,3,0 };insertSort(arr, sizeof(arr) / sizeof(int));return 0;
}希尔排序
算法思想
希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数gap把待排序文件中所有记录分成个组所有距离为gap的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当gap1完成最后的直接插入排序时所有记录在统一组内排好序。 希尔排序动图 特性总结
希尔排序的特性总结
希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些书中给出的希尔排序的时间复杂度都不固定 《数据结构(C语言版)》— 严蔚敏 《数据结构-用面相对象方法与C描述》— 殷人昆 因为本人的gap是按照Knuth提出的方式取值的而且Knuth进行了大量的试验统计我们暂时就按照O(N1.25)到O(1.6*N1.25)来算。稳定性不稳定
代码实现
#includestdio.h//void shellSort(int* a, int n)
//{
// //1.预排序 -- 接近有序
// int gap 3;
// for (int i 0; i gap; i)//优化写法,效率相同
// {
// for (int j i; j n - gap; j gap)
// {
// int end j;
// int tmp a[end gap];//记录需要插入的值
// while (end 0)
// {
// if (a[end] tmp)
// {
// a[end gap] a[end];
// end - gap;
// }
// else break;
// }
// a[end gap] tmp;
// }
// }
//}void printArr(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void shellSort(int* a, int n)//希尔排序
{//1.预排序 -- 接近有序//2.gap 1 直接插入排序int gap n;while (gap 1){gap gap / 3 1;//1可以保证最后一次一定是1for (int j 0; j n - gap; j){int end j;int tmp a[end gap];//记录需要插入的值while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}else break;}a[end gap] tmp;}}
}int main()
{int arr[] { 7,1,9,8,0,3,2,5,4,6,10,-1 };printArr(arr, sizeof(arr) / sizeof(int));shellSort(arr, sizeof(arr) / sizeof(int));printArr(arr, sizeof(arr) / sizeof(int));return 0;
}
