上海门户网站论坛,wordpress的代码在哪里修改,顶尖网站设计,wordpress my vistors现在#xff0c;我们学习了之前数据结构的部分内容#xff0c;即将进入一个重要的领域#xff1a;排序#xff0c;这是一个看起来简单#xff0c;但是想要理清其中逻辑并不简单的内容#xff0c;让我们一起加油把#xff01;
排序的概念及其运用
排序的概念 排序…现在我们学习了之前数据结构的部分内容即将进入一个重要的领域排序这是一个看起来简单但是想要理清其中逻辑并不简单的内容让我们一起加油把
排序的概念及其运用
排序的概念 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 内部排序数据元素全部放在内存中的排序。 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 排序运用 商品排序 院校排名 除了这些还有其他的一些地方也会用到排序总之我们的生活中处处都存在着排序所以学习好排序的使用对于我们后续学习是十分重要的
常见排序算法 而我们今天讲的重点就是插入排序其中包含着的就是直接插入排序和希尔排序而希尔排序事实上就是直接插入排序的升级版
插入排序 基本思想 直接插入排序是一种简单的插入排序法其基本思想是 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 。 直接插入排序 当插入第i(i1)个元素时前面的array[0],array[1],…,array[i-1]已经排好序此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较找到插入位置即将array[i]插入原来位置上的元素顺序后移 直接插入排序的特性总结 元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定 我们首先给一个例子为大家讲解一下其中的原理 int a[ ]{6 9 1 2 5}; 假设此时我们要排序的是1那么我们用end1作为插入排序元素的下标end则是前面已经排好顺序的一段范围为[0,end]。此时我们用一个变量记录住1的值然后往前比对。我们发现1比9小所以end1下标的位置变为9然后end–1比6小6又被赋值到了原本9的位置上最后再把1赋值到下标0的位置上一次排序就成功了。 写成代码是这个样子的 int end;
int tmpa[end1];
while(end0){if(tmpa[end]){a[end1]a[end];end--;}else{break;}
}a[end1]tmp;为什么while循环的结束条件是end0呢拿上面的举例一开始end1的下标为2也就是end为1end- -之后变成了0而第二次end- -之后直接变成了-1退出循环。此时end10也就是数组的第一个元素最小的元素刚好就是1 但很明显这样的话这个函数只能比较一次怎么样才可以实现多次比较呢这个时候就需要在外面嵌套一个for循环然后从0开始一个一个比对直到n-2如果是n-1end1就是n就超过数组的下标了会越界 所以最终的直接插入排序是这样写的
//插入排序前一段有序在后方插入一个并再次排序
//[0,end] end1大概就这个意思
//时间复杂度O(N^2)
//最好的情况O(N)就算有序也得遍历一遍
void InsertSort(int* a,int n) {for (int i 0; i n - 1; i) {int end i;int tmp a[end 1];while (end 0) {if (tmp a[end]) {a[end 1] a[end];end--;}else {break;//终止循环}}a[end 1] tmp;}
}希尔排序缩小增量排序 希尔排序Shell’s Sort是插入排序的一种更高效的改进版本也称为缩小增量排序。它的基本思想是先将整个待排序的记录序列分割成为若干子序列由相隔某个“增量”的记录组成的分别进行直接插入排序然后依次缩减增量再进行排序待整个序列中的记录“基本有序”时再对全体记录进行一次直接插入排序。 希尔排序的增量序列的选择是一个数学难题通常选取这个常用的增量序列t1n/2titi-1/2直到ti1为止。其中n为待排序序列的长度。按照增量序列的个数k对序列进行k趟排序。每趟排序根据对应的增量ti将待排序列分割成若干长度为m的子序列分别对各子表进行直接插入排序。仅增量因子为1时整个序列作为一个表来处理表长度即为整个序列的长度。 只看概念会觉得晦涩难懂还是先给大家举一个例子看看 假设有这么一个数组我们要对其进行希尔排序通常会分成两个步骤 1.预排序首先将其分为几个组然后针对每个分组进行插入排序 2.预排序之后此时数据已经趋于有序我们再对其整体进行直接插入排序
在这里的话我们假设间隔3个为一组那么9630就是一组852是一组741是一组而我们对每个组进行插入排序之后顺序就分别变成0369258147而放在整体中的话就是0 2 1 3 5 4 6 8 7 9可以看出次序比起一开始的逆序已经好了很多如果将这一次排序写成代码就是这个样子的 int gap3;//jn-gap是因为防止越界//内层的for循环只可以提供一组的排序而外部for循环使每一个组都排序//i0,i1,i2三个组都可以排序for(int i0;igap;i){for(int ji;jn-gap;jgap){int endj;int tmpa[endgap];while(end0){if(tmpa[end]){a[endgap]a[end];end-gap;}else{break;}} a[endgap]tmp;}}但是很明显这样子的话只比较排序了一次但我们需要的是在保证最后一次比较是gap1的情况下前面的预排序也要到位。但首先我们先把预排序的函数再修改一下让它不用分组排序而是多组并排。
int gap3;
for(int i0;in-gap;i){int endi;int tmpa[endgap];while(end0){if(tmpa[end]){a[endgap]a[end];end-gap;}else{break;}}a[endgap]tmp;
} 这样子的话就不是一个一个组的排而是从第一个元素开始按照其组别来排顺序相对于分组比较多组并排明显更简洁
完成这些之后我们就可以着手开始实现真正的希尔排序了
void ShellSort(int* a,int n){int gapn;//gap1时是预排序目的接近有序//gap1时就是直接插入排序目的有序while(gap1){gapgap/2;//让其预排序之后最终gap1进行最终的直接插入排序//gap越大大的值更快调到后面小的值可以更快的调到前面越不接近有序gap越小跳得越慢但是越接近有序。//gapgap/31;也可以效率更高时间复杂度更低一个是log2N一个是log3Nfor(int i0;in-gap;i){int endi;int tmpa[endgap];while(end0){if(tmpa[end]){a[endtmp]a[end];end-gap;}else{break;}}a[endgap]tmp;}}那么大家一定很好奇这么复杂的希尔排序它的时间复杂度相较直接插入排序相比是否有进步它的使用效率是否高于直接插入排序接下来我就为大家来展示一下它们的差别。
int main() {int size 10000;int arr[10000];// 使用时间种子初始化伪随机数生成器srand(time(0));// 填充数组for (int i 0; i size; i) {arr[i] rand() % 1000; // 生成0到999之间的随机数}clock_t start, end;double cpu_time_used;// 测试插入排序的执行时间start clock();InsertSort(arr, size);end clock();cpu_time_used ((double)(end - start)) / CLOCKS_PER_SEC;printf(InsertSort took %f seconds to execute \n, cpu_time_used);// 测试希尔排序的执行时间start clock();ShellSort(arr, size);end clock();cpu_time_used ((double)(end - start)) / CLOCKS_PER_SEC;printf(ShellSort took %f seconds to execute \n, cpu_time_used);return 0;
}可以看出在初始化10000个随机数的数组中直接插入排序和希尔排序之间的效率差了几十倍而如果数据更多可能差的还会更多。
在最坏情况下(完全逆序希尔排序的时间复杂度是O(n^2)这与直接插入排序的时间复杂度相同但是在一般情况下其平均时间复杂度要优于O(n ^2)。希尔排序时间复杂度的优劣程度取决于间隔序列的选取不同的间隔序列的希尔排序的时间复杂度也会有所不同。
在实际使用中通常使用增量序列为n/2,kk/2,…1的希尔排序在平均情况下其时间复杂度大约介于O(n^1.3)和O(n ^2)之间这使得希尔排序在中等规模数据时具有较好的性能。
其实我们自己也可以简单分析一下以最坏情况来看 gap很大时gapn/31此时我们忽略1 。这一趟每组3个移动次数第二个最多移动1次第三个最多移动2次合计为3而总计有3/n组累计移动的次数是12) * 3/nn 而下一轮预排序gapn/9每组9个移动次数123…836总计n/9组累计移动次数4n但这是最坏的情况下做出的判断在经历过第一次排序之后已经比刚才更接近有序不会所有的元素都要排序所以次数必定是小于4n的而后面的预排序也是与这个一样的所以我们并不确定其时间复杂度只能算出一个大概的区间具体情况只能跟当前排序的数据元素相关需要经过大量分析才能得出结论。
以上就是排序的第一讲插入排序下一节我们将会讲解选择排序欢迎大家关注后续文章
