十大经典排序算法及比较与分析 ( 动画演示 ) ( 可视化工具 ) |
您所在的位置：网站首页 › ppt如何对动画排序进行修改 › 十大经典排序算法及比较与分析 ( 动画演示 ) ( 可视化工具 ) |
十大经典排序算法及比较与分析 ( 动画演示 ) ( 可视化工具 )
|
可视化工具及动画展示：旧金山大学 (usfca)|数据结构可视化工具 排序算法概念及描述：1.0 十大经典排序算法（文章部分内容引用自改文章） 参考：邓俊辉 的数据结构 本文未对排序算法概念进行详细说明，只是提供已经验证过的代码及对算法核心进行简要说明 常用八种排序算法： 插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序 · 全部代码（github） C#版本 0X00 前言排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： 线性对数阶 (O(nlog2n)) （ log2n 是以2为底数的n的对数）排序： 快速排序、堆排序和归并排序； O(n1+§)) 排序 ( § 是介于 0 和 1 之间的常数 )： 希尔排序 线性阶 (O(n)) 排序： 基数排序，此外还有桶、箱排序。 关于稳定性 稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。 不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。 名词解释： n：数据规模k："桶"的个数In-place：占用常数内存，不占用额外内存Out-place：占用额外内存稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同 0X01 冒泡排序(起泡排序)可视化工具及动画演示 /// /// 冒泡排序（A版本） /// 从后往前扫描待排序序列，如果前一个元素比后一个元素大，就交换它们两个，对每一对相邻元素作同样的工作；这样，第一次扫描待排序的序列会找到一个最小值并将其放置在第一位，第二次扫描待排序的序列会找到一个第二小的值并将其放置在第二位，第三次扫描待排序的序列会找到一个第三小的值并将其放置在第三位，以此类推，直到将所有元素排序完毕；排序的过程就像泡泡不断的往上冒，总是小的泡泡在最上面，大的泡泡在最下面。 /// 时间复杂度： /// 双层循环次数：内循环次数 i=0(n-1),i=1(n-2),i=2(n-3),...,i=n-3(2),i=n-2(1)为等差数列，总次数=n*(0+n-1)/2=n*(n-1)/2 /// 假设每次比较都需要交换，执行内循环一次时复杂度为2（比较一次+交换一次），所以复杂度=2*n(n-1)/2=n(n-1) /// 当n非常大时，多项式以幂次方最大的为标准所以复杂度O=n(n-1)=O(n*n) /// /// void BubbleSort(int[] A) { int n = A.Length; for (int i = 0; i tmp; j--) //内循环使用冒泡方式对前面有序序列进行插入 { A[j] = A[j - 1]; } A[j] = tmp; } } 0X04 希尔排序基于插入排序 参考学习：https://baijiahao.baidu.com/s?id=1644158198885715432&wfr=spider&for=pc 可视化工具及动画演示 /// /// 希尔排序 /// 先取一个小于n的整数d1作为第一个增量，把数组元素分组，所有距离为d1的倍数的记录放在同一个组中，先在各组内进行直接插入排序；然后，取第二个增量d2> 1; int start1 = start; int end1 = mid; int start2 = mid + 1; int end2 = end; MergeSort(A, reg, start1, end1); MergeSort(A, reg, start2, end2); int k = start; //首先两个子序列分别是有序的，这里对两个子序列合并，挑选两个子序列中最小的放入reg临时序列中，直到两个子序列中一个子序列被完全放入后结束，然后将另一个子序列复制到reg临时序列中，最后临时序列是合并后的有序序列了，复制会A中 while (start1 |
关于时间复杂度 平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。【本文地址】
今日新闻 |
推荐新闻 |