如何做简单网站首页,百度网站建设费用,手机商城网站免费建站,网站视听内容建设排序的概念及其运用
排序的概念 排序 #xff1a;所谓排序#xff0c;就是使一串记录#xff0c;按照其中的某个或某些关键字的大小#xff0c;递增或递减的排列起来的操作。 稳定性 #xff1a;假定在待排序的记录序列中#xff0c;存在多个具有相同的关键字的记录所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性 假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次 序保持不变即在原序列中 r[i]r[j] 且 r[i] 在 r[j] 之前而在排序后的序列中 r[i] 仍在 r[j] 之前则称这种排 序算法是稳定的否则称为不稳定的。 内部排序 数据元素全部放在内存中的排序。 外部排序 数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。 排序的运用 常见的排序 插入排序直接插入排序
先写直接插入排序。 直接插入排序是一种简单的插入排序法其基本思想是 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为 止得到一个新的有序序列 。 实际中我们玩扑克牌时就用了插入排序的思想 一下子写排序是不可取的排序这个部分先写单趟后写整体。
就比如说我有0~end个数据的下标我想把该数组外的end1下标的值插入到现有数据。end在哪里我不清楚这里只是假设这里单趟的核心思想就是把一个数往前面的有序区间插入。这里的0~end肯定是有序的。注意注意这里的end是什么我们并不知道。 这里已经有一个有序区间了。然后我把后一个值往前面插入。 2比5小所以5得往后挪动但是一挪动就会覆盖2所以得先把2存起来。将2保存在一个变量中。比5小挪动end减减比3小挪动end减减比1大就放到1的后面。假如要插入的不是2了而是0那我还是比1小1往后挪动我end减减然后把0插入在end的后面所以结束条件为end-1 总结无论哪一种情况都是放在end的后面。
//单趟插入排序
void InsertSort(int* a, int n)
{int end0;int tmp a[end 1];while (end 0){if (tmp a[end]){a[end 1] a[end];--end;}else{break;}}//这里切记end要加1否则会出问题因为我们之前移动后立马end减去1了。a[end 1] tmp;
} 上图是完成了一趟了
这个循环有两个出去的条件一个是你比end对应的值大于或者等于就break跳出还有end小于0就结束就是所有的值都比你目标值大就一直挪动挪到end等于-1就将目标值插入到end的后面。这就是一趟走的整体思路。
完成了一趟的数据后我们就开始写次数来完善程序。
这里我们把end给为0就想当然把0当成有序然后继续来走。
所以给的end的其实位置就是0.所以在循环里这里就给i。
end为0时即第一个数据有序end后的数据开始插入以此类推。
end的结束位置在数组最后位置的前一个。即有n个数据那么最后一个数据的下标为n-1再往前就是n-2 因为这里要经常打印数组所以这里就写一个相应的函数。
void PrintArray(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}
分析时间复杂度
写代码时要对其的思路逻辑清楚一点否则会出现问题。
一定要学会单趟套整体。
这个直接插入排序的时间复杂度为多少千万不要说两层循环n的平方。简单排序看层数是没问题的。但是排序这里看循环层数来判断n的平方是不对的。判断时间复杂度要看思想。
这个直接插入排序逆序的时候时间复杂度是最坏的。就是第一个数有序第二个数插入一次第三个数两次就是等差数列。就是得全部挪动一遍。所以也就是1~n-1也就是n的平方。 呃呃呃虽然这个程序是n的平方但是切记看思想来判断。
这是最坏情况我们再看一下最好情况即顺序。就是0n就是遍历了一遍。或者说接近有序这个最好情况再顺序有序或者接近有序时成立。
为什么最好是0n呢就是我给你一个数组你是不知道他是是否有序的。你不知道他是否有序。没有排序可以做到01最快的排序就是接近0n的。当然在一些比较局限的场景里可以做到0n。常见的排序n*logn就是最好的了。
交换排序冒泡排序
体现素养的小细节
写个冒泡呜呜遇到友人了。
BubbleSort.(命名要规范否则面试出大问题。
规范代码里面不要有拼音除非没有对应的单词。这个关乎面试官对你的代码素养。 冒泡排序 是一种交换思想如果前一个大于后一个就交换这样以来一轮之后最大的值就到最后了。然后再前一个根后一个交换把次大的值换到倒数第二个位置了。
我们还按照先写单趟再写整体。
这里先写一个交换函数因为之后可以复用。
//单趟冒泡排序
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}void BubbleSort(int* a, int n)
{for (int i 1; i n; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);}}
} 代码比的是细节。要控制住细节。如果你觉得细节控制的不是太好那一定是画图画少了。
这里for循环条件也可以给i为0这样接得写in-1了这样得控制尾部的结束条件了。当然怎么写都是可以的。
我们这样写的就是一前一后进行交换。
到这里第一次记冒好了第一次就确定了最大值所以第二趟就冒到n-1就行了。当1时冒泡就结束。所以一共冒泡n-1次就行。
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}void BubbleSort(int* a, int n)
{for (int j 0; j n - 1; j){for (int i 1; i n; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);}}}
} 这里第一层次数循环是到n-2结束第二层for循环进行每一次需要的趟数到小于n-n-2结束即小于2就结束也就是到1我们分析就是到1就继续正好0和1那里比较了然后就结束思路是这样的。
到这里冒泡就写好了但是其实还是可以优化的。
冒泡空间有可优化的空间就是顺序可能或者基本有序就不冒一趟没有发现数据交换就不用再继续走了这里给个标志。
void BubbleSort(int* a, int n)
{for (int j 0; j n - 1; j){int exchange 0;for (int i 1; i n; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);exchange 1;}}if (exchange 0)break;}
}
冒泡排序的时间复杂度是n的平方。这个时候的最坏的情况不是说逆序了逆序只是其中一种情况不一定是逆序很多情况都是n的平方。最好的顺序就是接近有序从而达到0n。
它和插入排序看起来没什么区别但其实不一样。 冒泡排序的特性总结 1. 冒泡排序是一种非常容易理解的排序 2. 时间复杂度 O(N^2) 3. 空间复杂度 O(1) 4. 稳定性稳定 对比直接插入排序和冒泡排序
// 测试排序的性能对比
void TestOP()
{srand(time(0));//开100000个空间const int N 100000;int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);int* a3 (int*)malloc(sizeof(int) * N);int* a4 (int*)malloc(sizeof(int) * N);int* a5 (int*)malloc(sizeof(int) * N);int* a6 (int*)malloc(sizeof(int) * N);//每个数组放一样的数for (int i 0; i N; i){a1[i] rand();a2[i] a1[i];a3[i] a1[i];a4[i] a1[i];a5[i] a1[i];a6[i] a1[i];}//计算时间int begin1 clock();InsertSort(a1, N);int end1 clock();int begin2 clock();BubbleSort(a2, N);int end2 clock();/*int begin3 clock();SelectSort(a3, N);int end3 clock();int begin4 clock();HeapSort(a4, N);int end4 clock();int begin5 clock();QuickSort(a5, 0, N - 1);int end5 clock();int begin6 clock();MergeSort(a6, N);int end6 clock();*/printf(InsertSort:%d\n, end1 - begin1);printf(BubbleSort:%d\n, end2 - begin2);/*printf(SelectSort:%d\n, end3 - begin3);printf(HeapSort:%d\n, end4 - begin4);printf(QuickSort:%d\n, end5 - begin5);printf(MergeSort:%d\n, end6 - begin6);*/free(a1);free(a2);/*free(a3);free(a4);free(a5);free(a6);*/
}
int main()
{/*int a[] { 5,4,3,2,1 };BubbleSort(a, sizeof(a) / sizeof(a[0]));PrintArray(a, sizeof(a) / sizeof(a[0]));*/TestOP();return 0;
}
malloc个多个数组产生一个随机值。然后将数组1赋值给别的数组就是说这6个数组的值都是一样的。
这里begin减去end就是排序所消耗的时间。
clock是电脑运行启动到调用这个函数是所消耗的毫秒数所以两个clock之差就是中间的排序消耗掉的时间。 这里进行测试时debug可能优化没有全开测性能用release。
下图是realease的。 跑十万个值进行的比较。
所以明显的感觉到这两个不一样。不能单看时间复杂度来看这里的问题。
时间复杂度用来算他是属于哪一个量级的。这两个属于同一个档次的排序。同一个学校是统一档次但出来的不同同学有不同。
所以不能单一时间复杂度来评估。
选择排序堆排序 堆排序 (Heapsort) 是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是 通过堆来进行选择数据。 需要注意的是排升序要建大堆排降序建小堆。 直接选择排序的特性总结 1. 堆排序使用堆来选数效率就高了很多。 2. 时间复杂度 O(N*logN) 3. 空间复杂度 O(1) 4. 稳定性不稳定 void HeapSort(int* a, int n)
{//a数组直接建堆 0(N)for (int i (n - 1 - 1) / 2; i 0; --i){AdjustDown(a, n, i);}//O(N*logN)int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);printf(%d , a[end]);--end;}printf(%d, a[0]);
}
int main()
{int a[] { 5,4,3,2,1 };HeapSort(a, sizeof(a) / sizeof(a[0]));//PrintArray(a, sizeof(a) / sizeof(a[0]));//TestOP();return 0;
} 排序和排序直接真的有差距啊。
插入和冒泡属于同一类但效率差很多的重要的点在插入具有很强的适应性。
冒泡不再冒的条件是很苛刻的就是不能有任何一个交换没有一个条件交换就是已经有序了这个条件是很难达成的。 插入的适应性在哪里呢只要由一个靠后的数据比前面数据都小那就挪动n次。但是这是非常极端的一般来说这个数据可能在偏中间一点的位置即只挪动了一半的数据就达到了目的。 这个堆冒泡是常态但对于插入排序来说他只要每个数据都要挪满时才会出现这种情况。但是对插入排序来说他的中间或许可能会局部有序他不需要一直挪。随机的场景更多的是局部有序。 时间复杂度不在同一个量级就没有可比性在同一个量级的也有差异。冒泡在随机数是都是比满。 插入排序希尔排序 希尔觉得插入排序非常的不错如果有序接近有序插入有序就非常nb了。它要改革直接插入排序。如果能把数据接近有序那就很快乐。
所以他分为两个步骤
预排序 目标接近有序
他觉得你挪动的太慢了。它想让挪动的快一些。也就是分组插入排序。目标大的更快换到后面的位置小的数更快换到前面的位置。
就是以gap为间距来一一分组。 希尔排序法又称缩小增量法。希尔排序法的基本思想是 先选定一个整数把待排序文件中所有记录分成个 组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工 作。当到达 1 时所有记录在统一组内排好序 。 希尔排序的特性总结 1. 希尔排序是对直接插入排序的优化。 2. 当 gap 1 时都是预排序目的是让数组更接近于有序。当 gap 1 时数组已经接近有序的了这样就 会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。 3. 希尔排序的时间复杂度不好计算因为 gap 的取值方法很多导致很难去计算因此在好些树中给出的 希尔排序的时间复杂度都不固定 《数据结构(C语言版)》--- 严蔚敏 《数据结构-用面相对象方法与C描述》--- 殷人昆 稳定性不稳定 预排序和原数组相比 他有序了一点但不是很多。
我们先写单趟。
我们接下来以下图这个数组为例开始排 //单次希尔排序
void ShellSort(int* a, int n)
{int gap 3;int end0;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;
}
比完5和2了然后比5和3时不是上述代码写的得先在上图再套一层才能写这里先继续写。
这里跟插入排序很像无非就是将加1换成了加gap。
刚才完成的只是把一个数往前插入如果我们要排一组数据那么该如何排。 for(int i0;in;igap) 上图这里再套一层循环。但是这里有问题如果i等于在5的位置时即进行了交换之后再加上gap来进入循环这个时候就越界了。 所以外层循环应该写为上图
这个时候就帮助我们帮红色这一组就排完了但是我们想排整体该如何呢间距为gap就有gap组。gap是几就有几组。所以再次套一层循环。
//一个gap进行的希尔排序
void ShellSort(int* a, int n)
{int gap 3;for (int i 0; i n-gap; i gap){int endi;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}
}
所以外层循环应该写为上图
这个时候就帮助我们帮红色这一组就排完了但是我们想排整体该如何呢间距为gap就有gap组。gap是几就有几组。所以再次套一层循环。
//完整的希尔排序
void ShellSort(int* a, int n)
{int gap 3;for (int j 0; j gap; j){for (int i 0; i n - gap; i gap){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}
总结一下希尔排序分为预排序他的目的是分组插入排序
预排序的目标是大的更快换到后面的位置小的数更快换到前面的位置。 到这里其实上图完整的希尔排序也可以简化为2层。
void ShellSort(int* a, int n)
{int gap 3;/*for (int j 0; j gap; j){for (int i 0; i n - gap; i gap){*/for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}/* }}*/
}希尔排序是初始的是什么呢是一组排完排另一组。是排完红色再排绿色再排紫色。
一组一组排。
但是按照上图来说先比较换了2和5然后不一整组一整组比较而是最外层的i。这个方法是gap组数据交替完成分组插入排序。
gap大于1就是预排等于1就是快速排序。gap越大数据跳的越快大的更快到前面为止小的更快到后面但是越不接近有序。
gap越小数据跳的越慢但是越接近有序gap1就是插入后就是有序。 继续深入
这里还有人怎么给呢到这里就已经变为怎么给gap了。 这样就能控制gap了我第一次间距给上50gap大不接近有序没关系啊我gap在缩小我除以2最后一趟一定是1. 这里希尔排序每一组都在接近有序。
呜呜呜呜开始这个排序让你爱答不理最后让我高攀不起。呜呜呜呜 有人觉得除3更好但是除3不能保证最后余数为1. 代码能力是练出来的。需要消化的数据才是有含量的。 若有收获就点个赞吧
