企业网站建设可行性分析表,网页编辑软件 破解版,网页制作模板关于我们,vi设计论文1.插入排序 由上面的动图可以知道插入排序的逻辑就是从第一个元素开始往后遍历#xff0c;如果找到比前一个元素小的#xff08;或者大的#xff09;就往前排#xff0c;所以插入排序的每一次遍历都会保证前面的数据是有序的#xff0c;接下类用代码进行讲解。 我们这里传… 1.插入排序 由上面的动图可以知道插入排序的逻辑就是从第一个元素开始往后遍历如果找到比前一个元素小的或者大的就往前排所以插入排序的每一次遍历都会保证前面的数据是有序的接下类用代码进行讲解。 我们这里传两个参数一个是数组一个是数组元素的个数。 排序接口我们采用大事化小的想法来进行讲解 我们先来思考单趟遍历要达成的目标。我们每次遍历的主角其实就是我们要操纵的那一个元素比如我们要排第四个元素按照插入排序的逻辑前三个元素我们是已经有序了所以我们接下来的操作就是将我们的主角元素跟前面的元素进行比较如果元素比前面的小我们就跟前面的交换我们这里实现升序排序以此循环往复直到遇到比它还小的元素我们就终止循环所以我们就可以理解里面这层while循环的意思了循环结束的时候不要忘记把元素放到停止循环的end下标位置上有的同学可能一时间没有理解到为什么最后下标的位置是end1其实这是因为在结束while循环之前我们的end是减一过的所以才要给他加回去。 然后我们的for循环就是控制我们的主角啦就是控制后面的每一个元素跟前面已经排序好的元素进行比较。 插入排序最坏的时间复杂度On^2 最好的情况就是这个数组已经有序的时候时间复杂度为O(n) 2.希尔排序 上诉动态演示就是希尔排序大家看到这个演示的时候肯定会两眼一黑看不懂它是如何进行排序的希尔排序的逻辑是有点复杂但是我相信在我讲了它的实现思路之后对希尔排序也会有一个比较清晰的理解。 希尔排序可以相当于插入排序的pro版本这是因为它的逻辑虽然比插入排序复杂但是却是建立在插入排序之上插入排序的核心思想是遍历每一个元素去跟前面已经排好序的元素进行比较希尔排序有一个预排序的过程就是说通过给定一个gap变量名来控制一个间距使下标为end的元素跟endgap来比较这个预排序就是使一个无序数组接近有序数组在预排序完成之后再用插入排序使数组有序。其实到这里大家就会发现如果用这里的思想去理解插入排序的话插入排序实际上就是gap为1的情况嘛。 我们用代码来加深理解。 这是希尔排序的代码我们可以看到gap的初始值设置的是数组的长度那下面的while循环时什么意思呢我们先来理解最里层的while循环最里层的while循环是不是有一种很眼熟的感觉?它就是我们的插入排序的思想只不过插入排序是间隔为一进行比较希尔排序是间隔为gap进行比较我们再看外面这层for循环这层for循环控制的就是end的下标跟插入排序也非常的相似只不过这里的for循环结束的条件是n-gap因为既让我们当前下标的元素要跟后一个相比那总不能让endgap的下标超出界限吧。 最后再来看最外层的while循环它的作用就是控制gap的值。我们这里得要知道gap越大这一趟预排序就越不能做到很有序的程度但好处就是耗时短gap的值越小就是相反的情况但是不要忘记了一个数组越有序插入排序处理得就越快希尔排序也是一样的所以为了达到理想的时间复杂度我们的做法就是将gap的值由大到小。 接下来来说说gap的值如何来设置gap的值该如何来设置是没有一个统一的说法的但是有一个大佬想出的一个比较好的方法是用数组长度来充当第一次的gap值每一次循环完就将gap的值/31这是为了避免上一个gap为二的时候下一次gap直接变为0了。 所以我们的希尔排序最后一趟就是我们的插入排序只不过这个时候数组已经非常接近有序了。 我们的希尔排序最坏的情况下时间复杂度是O(n^2),平均是O(n^1.3)。
