排序算法(插入排序和希尔排序)

文章目录前言一、直接插入排序二、希尔排序1.希尔排序的理解2.希尔排序的实现总结前言关于排序对于一个C语言新手来说大多会使用冒泡排序和使用库函数qsort但在以后的学习中这些排序往往不能满足我们的需求今天我们来探讨一下排序算法中的插入排序和希尔排序一、直接插入排序所谓直接插入排序就是将一个无序序列向有序序列中插入排序举个形象的例子就如我们在打牌中进行整理牌的操作第一张牌一定有序往下的第2张第3张......依次插入最终形成有序序列代码解释这里代码外层for循环用于更新end的值有序序列的末尾当end位于下标n-1的位置时表明数组此时排序完成因此in-1。内层while循环将无序序列依次与有序序列进行比较大的放前小的放后。时间复杂度分析最好的情况对于有序序列时间复杂度为O(N)最坏的情况对于降序的序列时间复杂度为O(N^2)空间复杂度分析O(1)稳定性分析当出现重复数据时重复数据间的相对位置不会发生变化这种排序就稳定否则不稳定对于插入排序稳定二、希尔排序1.希尔排序的理解对于希尔排序其实是对插入排序的优化比如前面所说的当数据为降序时时间复杂度为O(N^2)那能不能优化呢希尔给出了答案。先将数据进行预排序所谓预排序指的是将一个数组分割成多组对每一组数据进行排序即小的在前面大的在后面当所有组完成排序后再对这个大数组进行直接插入排序得到的是有序序列1分割数组的意义减少数据个数以及元素间的距离排序更快2预排序的意义将一个无序数组通过分组进行预排序当预排序完成后即该数组接近有序此时再用直接插入法时间复杂度接近O(N)2.希尔排序的实现代码的理解和感悟这里的gap是既是组数也是每组中的元素个数关于为什么gap每次都除3加1其实这并没有严格规定gap除的越大分的组数越多每组中的元素个数也就越少但是gap必须满足两点要求1gap必须每次递减。2gap最终递减到1当gap1也就是对整个数组进行插入排序。在这里我个人认为对每一组的元素进行排序算法很是巧妙不是将每一组数据分开排序而是通过for循环依次访问了每一组的元素时间复杂度分析希尔排序的时间复杂度取决于gap的值而gap没有明确规定很难算出时间复杂度但是在国内的严蔚敏老师的《C语言数据结构》中指出通过大量的实验时间复杂度约为O(N^1.3)当gap是折半增量的情况下最坏的时间复杂度为O(N^2)。空间复杂度O1稳定性不稳定每组中相同元素在预排序过程中相对位置可能会发生改变。总结插入排序是将无序的数据插入有序序列中。希尔排序是对插入排序的优化但仍然存在时间复杂度为O(N^2)的情况。