自己创造网站平台,做整个网站静态页面多少钱,高校网站建设 调查,网站服务器租用价格一般多少钱?这次#xff0c;我们来讲数据结构的排序的直接插入。 一#xff1a;排序的思想#xff1a;把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中#xff0c;直到所有的记录插入完为止#xff0c;得到一个新的有序序列 相当于#xff0c;我们打牌如上图…这次我们来讲数据结构的排序的直接插入。 一排序的思想把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 相当于我们打牌如上图时我们一般都会使用直接插入排序的方法。 即在3和9直接插入对吧。 同样我们这里的直接排序也是按这种方法来思考。 那么我们先来上它的动图来方便我们更清楚。 步骤讲解升序 1.一开始的时候当第一个的时候它肯定是有序的所以我们从第二个数开始插入并比较。 2.先把第二个数用临时变量存起来再去比较如果它比前面对比数还要小就将前面对比数挪到后面临时变量再去跟更前面的数依次比较。 3.如果临时变量大于对比那个数就插入到对比数的后面。 4.循环数据向前插入进去直到全部的数都插到正确的位置。 void InsertSort(int* a, int n)
{//整个for (int i 1; i n; i){//单一个int end i - 1;int temp a[i];while (end 0){if (a[end] temp) //如果对比数大于存入临时的就对比数往后挪{a[end 1] a[end];end--;}else //如果对比数小于存入临时的就跳出循环{break;}}a[end 1] temp; //在对比数的后面插入数}} 直接插入排序的特性总结 1. 元素集合越接近有序直接插入排序算法的时间效率越高 就比如是 你每次插入是都比前面那个数大那么你是不是就不需要挪动数据了 假设你有n个数据按照上面的情况你执行的次数就是n-1,这样效率是不是就高了。 此时的最好时间复杂度O(N)。 2. 那么最坏的情况呢 就是逆序。这样你每次插入的时侯都是要跟前面的对比数挪动 此时的 时间复杂度O(N^2)。 3. 空间复杂度O(1)它是一种稳定的排序算法 4. 稳定性稳定 优化排序---希尔排序
上面我们已经知道插入排序的时间复杂度O(N^2).
那么有什么办法使他们的效率更高一点呢
这里大佬们提出了希尔排序的方法。 思路 1.用间隔为gap的变量分别对每组数插入 2.预排序它的目标就是接近有序 3.最后再直接插入 这样的方法会大大提高效率。
比如说你看按照下面的话分组 这一趟排序完是不是就看起来比没有排时变有序了。 这样一趟趟地回来到gap1时就只需挪隔壁的数字比较所以大大提高了直接插入的效率。 比较
我们知道上面直接排序
直接插入完全逆序时 它比较执行的次数123……n-1次 根据等差数列的公式n^2/2-n/2; 那么我们使用希尔排序用gap分组
gapgap/4时 分成两部分 那么它的次数12……n/2-112……n/2-1 那么计算得到n^2/4-n/2; 相比你看是不是就提高了效率。 gapgap/2 假设为n则分成3部分 执行的次数123……n-1*3 计算得 n^2/6-n/2; 类比得当我们分的部分越多执行的次数会减少。 有以下规律 当分成部分k执行次数 1/k*n^2/2-n/2 当gap越小跳得越慢越有序当gap越大跳得越慢越无序。 那么我们发现当gap很小时它的次数本来是n^2/2-n/2但是我们考虑到之前我们已经经过预排序了已经很接近有序了所以按照最好的情况来算。 总结 希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。 希尔排序的特性总结 1. 希尔排序是对直接插入排序的优化。 2. 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。 3. 希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的希尔排序的时间复杂度都不固定 根据大佬们的推算一般都是gap(gap/31常用 int gap n;while (gap 1){gap gap / 3 1;for (int i 0; i gap; i){for (int i 0; i n - gap; i gap){//单个int end i;int temp a[i gap];while (end 0){if (a[end] temp){a[end gap] a[end];end - gap;}else{break;}}a[end gap] temp;}}}}
好了选择排序和希尔排序就写完了。
最后学路漫漫永无止境一点一点进步吧
