快速稳定表选择排序算法研究

摘要：

为改进直接选择排序算法的不稳定性及对数据的不敏感性,笔者研究了表选择排序算法.该算法约定用静态链表存储待排数据,先创建有序链表,再根据链接信息将数据顺序存储.此算法不仅保证排序算法的稳定性,也使时间复杂性由原来的O(n2/2)在最好和平均情况下分别降到O(n)和O(n2/4)(最坏情况不变),另外还保证后续其他操作也同样具备顺序存储的优点.从排序稳定性、数据比较次数和移动次数三方面来看,本文中提出的排序算法在简单排序算法中是最优的.

关键词：直接选择排序、稳定性、数据敏感性、静态链表、算法分析

所属期刊栏目：40

分类号：TP301.6;TP311.1(计算技术、计算机技术)

资助基金：教育部产学合作协同育人资助项目201702112019;校研究生教育教改基金资助项目070-150031

在线出版日期：2018-12-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：487-495