 多路树查找－外部查找(B树)【源代码】多路树查找－外部查找(B树)【下载及演示说明】双向链表演示程序【下载及演示说明】循环链表演示程序【下载及演示说明】链表【讲解】动态存储分配之边界标识法演示程序【下载及演示说明】动态存储分配之边界标识法【讲解】首次适应算法和最佳适应算法【讲解】动态存储分配之边界标识法【源代码】振荡排序算法【讲解】振荡排序演示程序【下载及演示说明】树和二叉树相互转化【讲解】深度优先搜索【下载及演示说明】深度优先搜索【源代码】朴素字符串匹配演示程序【下载及演示说明】当前1/4页 首页 上一页 下一页 尾页 | |
算法讲堂 |
|
本栏目所有文章由本站组织业内技术专家原创而成，用汇编语言向学习者讲解经典问题的编程思想和编程方法。 本栏目所有文章的版权归本站所有，转载请注明出处为汇编网<www.asmedu.net> 。 现本栏目的内容处于不断添加中，请随时关注。 |
|
| 算法讲堂－》计数排序【讲解】 |
|
算法介绍：
计数排序法是一种简单的排序方法，这种排序算法对一个待排序的数组进行排序，并将排序结果放到另一个新的数组中。计数排序算法针对待排序数组中的每个记录，扫描待排序的数组一趟，统计待排序数组中有多少个记录的值比该记录的值小。假设针对某一个记录，统计出的计数值为c,那么，这个记录在新的有序数组中的合适的存放位置即为c。 假设有三个数组： 数组 A：待排序数组（非空，数据个数n） 数组 B：排序后的数组 数组 count：纪录A中某个数据在表B中的位置，初始值为0 对于A中某个数据Xi（0<=i<n），与表中各个数据Xj（0<=i<n）进行比较，记录下比Xi小的值的个数到count[i]。但是，我们发现，数据与自身的比较是多余的，而且当Xi与Xj比较后，就没有必要再比较Xj和Xi了。在此基础上我们对之前的操作方式进行一些变化。我们对A中的数据Xi与Xj进行比较，所不同的是Xj的j的范围为 i<j<=n ，即每个Xi只和其后的数据进行比较。在比较过程中，如果Xi > Xj ，则count[i] = count[i]+1；否则，count[j]=count[j]+1 。当算法完毕的时候，count数组中就记录了A中的各个数据在B中的实际位置。算法过程如下所示： n 0 1 2 3 /*数组的索引位置*/ A 21 32 17 21 /*数组中的数据*/ C [0] [0] [0] [0] /*count的初始值*/ 算法开始i=0，j取值{1 ，2，3}。 （1）X0<X1 ，所以count[1]+1 n 0 1 2 3 /*数组的索引位置*/ A 21 32 17 21 /*数组中的数据*/ C [0] [1] [0] [0] /*count的值*/ （2）X0>X2 ，所以count[0]+1 n 0 1 2 3 /*数组的索引位置*/ A 21 32 17 21 /*数组中的数据*/ C [1] [1] [0] [0] /*count的值*/ （3）X0=X3 ，所以count[3]+1 n 0 1 2 3 /*数组的索引位置*/ A 21 32 17 21 /*数组中的数据*/ C [1] [1] [0] [1] /*count的值*/ 接下来i=1 ，j取值{2，3} ……. 如此继续直至算法完毕，则 n 0 1 2 3 /*数组的索引位置*/ A 21 32 17 21 /*数组中的数据*/ C [1] [3] [0] [2] /*count的初始值*/ 接下来的要做的只是按count中的值将A中的数据放到B中相应的位置上了，即 B[count[i]] = A[i]，则数组B中数据为 B [17] [21] [21] [32] 至此计数排序算法完成。 在上述过程中，我们看到，对于待排序数组中的相同数据，在排序后其先后顺序保持不变，也就是说以上原理的排序算法是一个稳定的排序算法。 算法复杂度： 上述计数排序算法包含两重循环，假设数组A中的数据个数为n，那么在程序执行过程中，第二层循环控制变量j的执行次数随着第一层循环控制变量i的变化依次为n-1 ， n-2，n-3，…….，0 ，这是一个差值为1的n项等差数列，所以第二层循环的执行次数为(n-1+0)*n/2,即n*（n-1）/2，所以该算法的时间复杂度为O（n2）。 学习建议及练习任务： 按照上述计数排序的原理，实现一个计数降序排序，要求排序的算法是稳定的。 [07/09/25] |