HASH GAME - Online Skill Game GET 300

　　2010年第10期计算机与现代化J 1SUANJ I YU XIANDAIHUA总第182期文章编号：1006-2475( 20LO) 10-0047-03一种新的基于哈希函数的排序算法王秋芬，邵艳玲( 南阳理工学院计算机科学与技术系，河南南阳473004)摘要：提出一种哈希函数分档的排序算法。根据数组下标递增的特点，针对任意分布整数，建立有效的哈希函数，通过反复映射完成排序。分析算法的时间和空间复杂度，实验验证算法的运行效率。算法分析和实验结果表明：算法的时间和空间复杂度均为0( n) ，在问题规模较大时。效率优势明显。关键词：哈希函数；排序；算法；复杂性中图分类号：TP302 文献标识码：Adoi ：10．3969／j ．i ssn．1006—...

　　2010年第10期计算机与现代化J 1SUANJ I YU XIANDAIHUA总第182期文章编号：1006-2475( 20LO) 10-0047-03一种新的基于哈希函数的排序算法王秋芬，邵艳玲( 南阳理工学院计算机科学与技术系，河南南阳473004)摘要：提出一种哈希函数分档的排序算法。根据数组下标递增的特点，针对任意分布整数，建立有效的哈希函数，通过反复映射完成排序。分析算法的时间和空间复杂度，实验验证算法的运行效率。算法分析和实验结果表明：算法的时间和空间复杂度均为0( n) ，在问题规模较大时。效率优势明显。关键词：哈希函数；排序；算法；复杂性中图分类号：TP302 文献标识码：Adoi ：10．3969／j ．i ssn．10062475．2010．10．012A New Sorti ngAl gori thmWANG Qi ufen，SHAO( DepartmentofComputerSci ence and Technol ogy，NanyangAbstract：The paper bri ngs forward a new sorti ng al gori thm basedsubscri pt progressi ve i ncrease，i testabl i shes effecti ve Hash functi onri ng by mappi ng repeatedl y．Ti meand spacecompl exi tyi sanal yzed，andri thm anal ysi s and experi mental resul ts show that the al gori thmsri thra Seffi ci encywhen the scal e of theprobl em i s l arge．Key words：Hash functi on；sort；al gori thm；compl exi ty0引 言排序是计算机程序设计中的重要操作，在系统软件和应用软件中应用频率很高，许多专家、学者一直在不断探索高效且辅助空间少的排序算法。远到基于比较和交换的排序算法，这类算法的最佳性能为0( nl 092n) 1，近至各类基于分档、分段、字节、位的线I，这类算法不再利用比较和交换，而是基于映射链接 2J 副的思想，有效结合其它算法，提高了算法的效率。但存在共同的问题：算法效率与待排序数据元素( 以下简称待排元素) 的分布有关。针对这一问题，提出采用哈希函数分档的排序算法。该算法与现有分档排序算法相比，在待排元素任意分布的情况下，效率明显提高。1算法描述算法首先确定待排元素的最大值a max和最小值ami n，并计算它们的差值AM和满足n1AM的最小整数x。让任一待排元素a与最小值的差值除以n。( kZ且0kx) 后取整，再对元素个数n取余，将其映射到011一l 的范围内进行排序。即：对所有待排元素，先将它与最小值的差值小于n的待排元素排序，再将与最小值的差值小于n2的待排元素排序，以此类推，循环操作x次，直到最后将小于i 11的待排元素排序。此时，排序结束。1．2哈希函数的确定根据算法的基本思想，设r1个待排元素组成的集收稿日期：2010-06-07基金项目：南阳理工学院青年基金资助项目( NYLGQN20070101)作者简介：王秋芬( 1978．) ，女，河南濮阳人，南阳理工学院计算机科学与技术系讲师，硕士，研究方向：计算机软件理论，算法理论；邵艳玲(1978-)，女，河南西平人，讲师，硕士，研究方向：计算机应用技术，流媒体技术。