网站建设灯,网站用什么切版,360建筑网是什么,网站建设实训 课程标准【八大经典排序算法】#xff1a;直接插入排序、希尔排序实现 --- 性能大比拼#xff01;#xff01;#xff01; 一、 直接插入排序1.1 插入排序原理1.2 代码实现1.3 直接插入排序特点总结 二、希尔排序 ( 缩小增量排序 )2.1 希尔排序原理2.2 代码实现2.3 希尔排序特点… 【八大经典排序算法】直接插入排序、希尔排序实现 --- 性能大比拼 一、 直接插入排序1.1 插入排序原理1.2 代码实现1.3 直接插入排序特点总结 二、希尔排序 ( 缩小增量排序 )2.1 希尔排序原理2.2 代码实现2.3 希尔排序特点总结 三、直接插入排序和希尔排序性能大比拼 !!!3.1 如何对比性能准备工作3.2 如何实现创建数据比较快慢代码、结果分析 一、 直接插入排序
1.1 插入排序原理
直接插入排序是一种简单的插入排序法其基本原理是 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。 而实际中我们玩扑克牌时就用了插入排序的思想 1.2 代码实现
【代码思路】直接插入排序还是比较简单的。我们将第一个元素当作一个有序序列然后从第二个元素开始将其作为当前插入的元素并与已排序部分的元素进行比较找到合适的插入位置。然后不断重复上述操作直到所有元素都被插入到已排序部分。 当插入第i(i1)个元素时前面的a[0], a[1], …, a[i-1]已经排好序此时用a[i]的排序码与a[i-1],a[i-2],…的排序码顺序进行比较找到插入位置即将a[i]插入原来位置上的元素顺序后移。
void InsertSort(int* a, int n)//排升序
{for (int i 0; i n-1; i){int end i;//tmp记录待插入元素因为插入数据时需要挪动数据会被覆盖int tmp a[end1];//[0,end]有序将tmp插入到合适位置while (end 0){if (a[end] tmp){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
}1.3 直接插入排序特点总结
元素集合越接近有序直接插入排序算法的时间效率越高。时间复杂度O(N^2)。并且是时间复杂度为 N^2的所有算法中最快的排序。空间复杂度O(1)它是一种稳定的排序算法。 二、希尔排序 ( 缩小增量排序 )
逆序有序的数组进行插入排序时时间复杂度为O ( n^2 )此时效率最低。
顺序有序的数组进行插入排序时时间复杂度为O ( n )此时效率最高。
我们发现当被排序的对象越接近有序时插入排序的效率越高那我们是否有办法将数组变成接近有序后再用插入排序此时希尔大佬就发现了这个排序算法并命名为希尔排序 2.1 希尔排序原理
希尔排序法又称缩小增量法。为了提高插入排序效率希尔给出了这样一个办法 将原有大量数据进行分组分割成若干个子序列此时每个子序列待排序的个数就减少了。然后对这些子序列分别进行插入排序目的在于使较小的数据基本在前面较大的数据基本在后面而不大不小的数据则位于中间从而达到排序基本有序的目的。当整个序列基本有序时最后在全体进行一次插入排序即可。 2.2 代码实现
【代码思路】首先确定希尔排序的间距gap可以根据不同的方法选择不同的间距。根据选择的间距将待排序的数组分割成若干个子序列使用插入排序对每个子序列进行排序。逐步减小间距重复第二步直到间距为1。此时整个数组被分割成了一个子序列即原始的待排序序列。最后对原始的待排序序列进行插入排序最终得到有序数组。这里博主建议gapn(数据个数/ 3,在不断更新gap) void ShellSort(int* a, int n)
{//1. gap1 预排序//2. gap1 插入排序int gap n;while (gap 1){gap gap / 3 1;//多组并排for (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;}}
}2.3 希尔排序特点总结
希尔排序是对直接插入排序的优化。当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些树中给出的希尔排序的时间复杂度都不固定 《数据结构(C语言版)》— 严蔚敏 《数据结构-用面相对象方法与C描述》— 殷人昆 因为此处的gap是按照Knuth提出的方式取值的而且Knuth进行了大量的试验统计我们暂时就按照O(n^1.25) ~ O(1.6 * n^1.25)。 三、直接插入排序和希尔排序性能大比拼 !!!
希尔排序虽然看起来比较普通但实际性能可以和快排以及堆排序达到一个量级
3.1 如何对比性能准备工作
要对比两算法性能首先创建一个包含大量元素的随机数组这个数组将用于测试两个排序算法的效率。并且要确保测试数据集的大小足够大以便能够准确测量算法的效率。在分别对两个排序算法在相同的测试数据集上进行排序并记录每个算法排序所花费的时间。最后将两个排序算法的排序时间进行比较即可。 Tips ①在对比两个排序算法的效率时需要确保使用相同的编程语言和相同的测试数据集。 ②编译器切换到Release模式。 至于原因就得提到Release的特点了。 Release模式可以优化代码的性能和执行速度减少调试信息的冗余并提高程序的运行效率。在对比两个算法时这些优化和调试信息并不是必需的。 3.2 如何实现
创建数据
首先为两个为两个待排序数组创建足够大的存储空间然后调用rand()随机生成数据。为保证两待排数组中的数据一样将随机生成的数据依次赋值给两数组。
比较快慢
要比较两则运行时间可以调用clock()函数就可以轻松得到算法执行时间了 CPlusPlus:clock() clock()计算的是程序运行开始到执行此函数的运行时间单位ms
代码、结果分析
void TestOP()
{srand((unsigned int)time(NULL));//博主受限电脑配置数据只能建10000个。//各位可适当扩大数据两则差距更明显const int N 100000;int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);for (int i 0; i N; i){a1[i] rand();a2[i] a1[i];}int begin1 clock();InsertSort(a1, N);int end1 clock();int begin2 clock();ShellSort(a2, N);int end2 clock();printf(InsertSort:%d\n, end1 - begin1);printf(ShellSort:%d\n, end2 - begin2);free(a1);free(a2);
}运行结构 上述结果我们直观发现希尔排序性能远远大于直接插入排序。 可能有部分学者还是感受不出来你可以将数据个数扩大到百万看看就知道了。
