2024年4月30日发(作者：)

电脑编程技巧与维护　

链式存储结构上选择排序算法的研究与实现　

岳秋菊，达文姣，瞿朝成。任志国　

（兰州城市学院信息工程学院，兰州７３００７０）　

摘要：线Ｉ陛表上进行的选择排序法是一种较简单的内部排序算法，计算机研发人员经常研究和讨论顺序表中选择　

排序算法的实现及其改进。讨论了选择排序在单链表上和静态链表上的算法及实现过程，分析了算法时间和空间复　

杂度。　

关键词：选择排序；存储结构；单链表；静态链表；算法分析　

Ｒｅｓｅａｒｃｈ　ａｎｄ　Ｒｅａｌｉｚａｔｉｏｎ　ｏｆ　Ｓｅｌｅｃｔｉｏｎ　Ｓｏｒｔ　Ａｌｇｏｒｉｔｈｍ　ｏｎ　

Ｌｉｎｋ　Ｓｔｏｒａｇｅ　Ｓｔｒｕｃｔｕｒｅ　

ＹＵＥ　Ｑｉｕｊｕ，ＤＡ　Ｗｅｎｊｉａｏ，Ｑｕ　Ｃｈａｏｃｈｅｎｇ，ＲＥＮ　Ｚｈｉｇｕｏ　

（Ｃｏｒｔｅｇｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ　ｏｆ　Ｌａｎｚｈｏｕ　Ｃｉｔｙ　Ｕｎｉｖｅｒｓｉｙ，Ｌａｔｎｚｈｏｕ　７３００７０）　

Ａｂｓｔｒａｃｔ：Ｓｅｌｅｃｔｉｏｎ　Ｓｏｒｔ　ｗｈｉｃｈ　ｐｒｏｃｅｅｄｓ　ｏｎ　ｌｉｎｅａｒ　ｌｉｓｔ　ｉｓ　ａ　ｋｉｎｄ　ｏｆ　Ｓｉｏｎｐｌｅ　ｉｎｎｅｒ　ｓｏｒｔ　ａｌｇｏｒｉｔｈｍｓ．Ｃｏｍｐｕｔｅｒ　ｗｏｒｋｅｒｓ　ａｌｗａｙｓ　

ｒｅｓｅａｒｃｈ　ａｎｄ　ｄｉｓｃｕｓｓ　ｔｈｅ　ｒｅａｌｉｚａｔｉｏｎ　ａｓ　ｗｅｌｌ　ａｓ　ｉｍｐｒｏｖｅｍｅｎｔ　ｏｎ　Ｓｅｌｅｃｔｉｏｎ　ｓｏｒｔ　Ａｌｇｏｒｉｔｈｏｎ　ｏｆ　ｌｉｎｋ　ｌｉｓｔ．Ｉｎ　ｔｈｉｓ　ａｒｔｉｃｌｅ　ｗｅ　ｄｉｓｃｕｓｓ　

ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｒｅａｌｉｚａｔｉｏｎ　ｐｒｏｃｅｅｄｅｄ　ｏｎ　ｓｉｎｇｌｅ—ｌｉｎｋ　ｌｉｓｔ　ａｎｄ　ｓｔａｔｉｃ—ｌｉｎｋ　ｌｉｓｔ．Ｆｉｎａｌｌｙ　ｗｅ　ａｎａｌｙｚｅ　ｔｈｅ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ｔｉｍｅ　ａｎｄ　

ｓｐａｃｅ　ｏｆ　ｔｈｅ．　

Ｋｅｙ　ｗｏｒｄｓ：Ｓｅｌｅｃｔｉｏｎ　Ｓｏｒｔ；Ｓｔｏｒａｇｅ　Ｓｔｒｕｃｔｕｒｅ；Ｓｉｎｇｌｅ－ｌｉｎｋ　ｌｉｓｔ；Ｓｔａｔｉｃ－ｌｉｎｋ　ｌｉｓｔ；Ａｎａｌｙｓｉｓ　ｏｆ　ａｌｇｏｒｉｔｈｍ　

ｌ前言　

选择排序是一种较简单的选择类排序算法。在文献［１－４】　

中讨论了其在顺序表上的实现过程。选择排序在链表上的基　

本思想是从记录的无序子序列中“选择”关键字最小或最大　

ｅｌｅｍｔｙｐｅ　ｔ；　

ｆｏｒ（ｐ＝ｈｅａｄ－＞ｎｅｘｔ；ｐ－＞ｎｅｘｔ！＝ＮＵＬＬ；ｐ＝ｐ－＞ｎｅｘｔ）　

，，ｐ从链头遍历到链尾　

｛　

ｆｏｒ（ｍｉｎ＝ｐ，ｑ－－ｐ一＞ｎｅｘｔ；ｑ？＝ＮＵＬＬ；ｑ＝ｑ－＞ｎｅｘｔ）　

的记录，并将它加入到有序子序列的后面，以此方法增加记　

录的有序子序列的长度。含有ｎ个记录线性表需要进行ｎ一１　

趟排序；每一趟选择在剩余的记录中最小（大）的记录，然后　

将该元素交换到相应位置，重复直至全部排序完毕。　

在排序的研究上近几年来也有一些新的方法和结果产生，　

参见文献［６—９］。在顺序表上选择排序的实现较简单，在链表　

上的排序思想基本和顺序表上的相似。文中未提及的概念及　

术语参见文献［１】与文献［２］。　

，，ｐ，ｑ始终是前序和后继关系　

｛　

ｉｆ（ｑ－＞ｄａｔａ＜ｍｉｎ－＞ｄａｔａ）价己住最小元素的位置　

｛　

）　

ｉｆ（ｍｉｎ！＝ｐ）　

ｍｉｎ＝ｑ；　）　

鸺最小元素交换到链的最前面完成选择排序　

｛ｔ－ｐ一＞ｄａｔａ；　

ｐ－＞ｄａｔａ＝ｍｉｎ－＞ｄａｔａ；　

ｍｉｎ－＞ｄａｔａ＝ｔ；　

２选择排序算法在单链表上实现　

为了能够更加清楚地描述选择排序在链式结构上的实现，　

定义链表的节点的链式结构：　

ｙｐｅｄｅｆ　ｉｔｎｔ　ｅｌｅｍｔｙｐｅ；　

ｓｔｒｕｃｔ　ｎｏｄｅ　

｝　

｝　

）　

３选择排序算法在静态链表上实现　

为了描述插入排序在静态链表上的排序过程，定义静态　

链表的结构：　

ｆ　ｅｌｅｍｔｙｐｅ　ｄａｔａ；，／数据域　

ｓｔｒｕｃｔ　ｎｏｄｅ＊ｎｅｘｔ；Ｈ￣ｄ针域　

ｌ　ｌｉｎｋｌｉｓｔ；／／￥￣表名　

＃ｄｅｆｉｎｅ　Ｎ　５０／／Ｎ为链表可能达到的最大长度　

ｔｙｐｅｄｅｆ　ｉｎｔ　ｅｌｅｍｔｙｐｅ；　

ｔｙｐｅｄｅｆ　ｓｔｕｃｔ　ｎｏｄｅ　ｒ

算法思想描述：在选择排序中，将所有元素进行从链头　

扫描到链尾。在扫描过程中记住最小元素的位置。将最小元　

素交换到最前面完成一次排序过程，这样重复进行扫描交换，　

最后变为有序序列。算法实现下：　

ｖｏｉｄ　Ｓｅｌｅｃｔｓｏｒｔ（１ｉｎｋｌｉｓｔ　ｈｅａｄ）　

ｆ　ｅｌｅｍｔｙｐｅ　ｄａｔａ；／／数据域　

ｉｎｔ　ｎｅｘｔ；／／￣针域　

｝ｓｌｉｎｋｌｉｓｔ；　

／／单链表上的选择排序算法　

｛　

ｌｉｎｋｌｉｓｔ　ｐ’　ＩＩｌｉｎ，　ｑ；　

作者简介：岳秋菊（１９７７一），女，讲师，硕士，研究方向：　

应用数学与算法。　

收稿日期：２０１１—０７—１８　

／／ｍｉｎ存放最小元素的地址；Ｐ，ｑ分别为前序，后继的关系　

与　

ＳＯＦＩＷＡＲＥ　ＤＥＶＥＬ０ＰＭＥＮＴ　ＡＮＤ　ＤＥＳＩＧＮ　

在静态单链表中，进行选择排序，具体操作为：链表指　

针指向头结点后的第一个元素，首先选出链表中最小的元素，　

软件开发与设计　

的设计思想和实现过程基本相同，而且实现过程也非常相似。　

４算法分析　

在线性表上的选择排序，最好情况下的时间复杂度是Ｏ　

（ｎ），最差和平均情况下的时间复杂度是Ｏ（　，辅助空间为　

将它和链表中的第１个元素交换。链表指针往后指向第二个　

元素的位置，然后从剩余的ｎ一１个节点中选择次小的元素，　

将它和链表中的第２个元素交换。直到待选择位置到倒数第２　

个节点为止，剩下的最后一个节点就是数据元素最大的节点。　

Ｏ（１），算法不稳定、在单链表和静态链表上的直接插入排序　

的时间复杂度，稳定性与在顺序表上完全相同。从实现过程　

和算法的分析，可以很明显的发现两种算法的设计思想和实　

现过程相似。链式结构上每个数据元素占用一个节点，而不　

算法实现描述如下：　

ｖｏｉｄ　Ｓｅｌｅｃｔｓｏｒｔ（ｓｌｉｎｋｌｉｓｔ　Ｓ［Ｎ１）　

，／静态链表上的选择排序算法　

｛　

会有多余的结点存在，所以数据所占的存储空间　良费较少。　

链式结构上的排序只改变链的指向，而不会改变数据元素所　

占节点的位置，即不会移动数据元素，从而节省了移动数据　

ｉｎｔ　ｐ，ｍｉｎ，ｑ；／／ｍｉｎ存放最小元素的地址；Ｐ，ｑ分别为前序，　

，，后继的关系　

ｅｌｅｍｔｙｐｅ　ｔ；　

元素所带来的运算工作量，提高了效率。　

ｆｏｒ（ｐ＝ｓ［ｈｅａｄ】．ｎｅｘｔ；ｓ［Ｐ］．ｎｅｘｔ！一１；ｐ＝ｓ［ｐ］．ｎｅｘｔ）　

从链头遍历到链尾　

ｆ　

ｏｒ（ｆｍｉｎ＝ｐ，ｑ＝ｓ【Ｐ】．ｎｅｘｔ；ｑ！＝一１；ｑ＝ｓ［ｑ］．ｎｅｘｔ）　

参考文献　

［１】严蔚敏，吴伟民．数据结构［Ｍ］．清华大学出版社，１９９７．　

［２】耿国华．数据结构（ｃ语言版）【Ｍ】．西安：西安电子科　

技大学出版社，２００２．　

［３】Ｒｏｂｅｔｒ　Ｌ．Ｋｒｕｓｅ，Ａｌｅｘａｎｄｅｒ　Ｊ．Ｒｙｂａ．Ｄａｔａ　Ｓｔｒｕｃｔｕｒｅｓ　ａｎｄ　Ｐｒｏｇｒａｍ　

，，ｐ，ｑ始终是前序和后继关系　

｛　

ｉｆ（ｓ【ｑ］．ｄａｔａ＜ｓ【ＩＩｌｉｎ］．ｄａｔａ）　

肌己住最小元素的位置　

｛　ｍｉｎ＝ｑ；　｝　

Ｄｅｓｉｇｎ　ｉｎ　Ｃ＋＋［Ｍ】．Ｐｅａｒｓｏｎ　Ｅｄｕｃａｔｉｏｎ，ＵＳＡ，２００１．　

）　

ｉｆ（ｍｉｎ！＝ｐ）　

［４］傅清祥，王晓东．算法与数据结构［Ｍ］．北京：电子工业　

出版社，１９９８．　

［５】Ｓｈｅｌｌ　Ｄ　Ｌ．Ａ　ｈｉｇｈ—ｓｐｅｅｄ　ｓｏｒｔｉｎｇ　ｐｒｏｃｅｄｕｒｅ［Ｊ］．Ｃｏｍｍｕｎｉｃａ－　

ｔｉｏｎｓ　ｏｆ　ｔｈｅ　ＡＣＭ，１９５９．　

∥斗辱最小元素交换到链的最前面完成选择排序　

｛ｔ＝ｓ［ｑ】．ｄａａ；ｔ　

Ｓ【ｑ】．ｄａｔａ＝ｓ【ｍｉｎｉ．ｄａｔａ；　

Ｓ【ｍｉｎ］．ｄａｔａ＝ｔ；　

［６］任志国，蔡小龙，等．插入排序算法的双链表模拟［Ｊ］．　

电脑编程与维护，２０１０，（３）：８－９．　

１　

）　

｝　

［７］达文姣，任志国，等．链式结构上排序算法的研究［Ｊ］．　

电脑编程与维护，２０１１，（３）：１－２．　

在线性表上的选择排序，最好情况下的时间复杂度是Ｏ　

（ｎ），最差和平均情况下的时间复杂度是Ｏ（ｎ２），辅助空间为　

Ｏ（１），算法一般不稳定。在单链表和静态链表上的选择排序　

的时间复杂度、空间复杂度、稳定性与在线性表上完全相同。　

所以从实现过程和算法的分析，可以很明显地发现两种算法　

【８】祁建宏，任志国，等．单链表中双插入排序算法研究【Ｊ］．　

电脑编程与维护，２０１１，ｆ２）：２６—２７．　

［９】达文姣，任志国，等．静态链表上排序算法的研究［Ｊ］．　

自动化与仪器仪表，２０１１，（２）：８０—８１．　

（上接第９页）　

［７】Ｄａｗｅｉ　Ｓｕｎ，Ｇｕｉｒａｎ　Ｃｈａｎｇ，Ｃｈｕａｎ　Ｗａｎｇ，Ｙｕ　Ｘｉｏｎｇ，Ｘｉｎｇｗｅｉ　

Ｗａｎｇ，Ｅｆｉｃｉｆｅｎｔ　Ｎａｓｈ　Ｅｑｕｉｌｉｂｒｉｕｍ　Ｂａｓｅｄ　Ｃｌｏｕｄ　Ｒｅｓｏｕｒｃｅ　

ｏｆ　Ｖｏｌｕｎｔｅｅｒ　Ｃｏｍｐｕｔｉｎｇ　Ｗｉｔｈ　Ｌｅｎｇｔｈｙ　Ｃｌｉｍａｔｅ　Ｍｏｄｅｌ　

Ｓｉｍｕｌａｔｉｏｎｓ［Ｊ】，Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｈｅ　ｔＦｉｒｓｔ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅ－　

ｒｅｎｃｅ　ｏｎ　ｅ—Ｓｃｉｅｎｃｅ　ａｎｄ　Ｇｒｉｄ　Ｃｏｍｐｕｔｉｎｇ．２００５：８—１５．　

Ａｌｌｏｃａｔｉｏｎ　ｂｙ　Ｕｓｉｎｇ　ａ　Ｃｏｎｔｉｎｕｏｕｓ　Ｄｏｕｂｌｅ　Ａｕｃｔｉｏｎ［Ｊ］２０１０　

Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　Ｏｎ　Ｃｏｍｐｕｔｅｒ　Ｄｅｓｉｇｎ　Ａｎｄ　Ａｐｐｌｉａｔｉ—　

【１　１］Ｓ　Ｌａｒｓｏｎ，Ｃ　Ｓｎｏｗ，Ｍ　Ｓｈｉｒｔｓ，ｅｔ１．Ｆｏａｌｄｉｎｇ＠Ｈｏｍｅ　ａｎｄ　Ｇｅｎｏｍｅ　

＠Ｈｏｍｅ：Ｕｓｉｎｇ　ｄｉｓｔｒｉｂｕｔｅｄ　ｃｏｍｐｕｔｉｎｇ　ｔｏ　ｔａｃｋｌｅ　ｐｒｅｖｉｏｕｓｌｙ　

ｏｎｓ，２０１０：Ｖ１—９４一Ｖ１－９９．　

［８］Ｄ．Ｐ．Ａｎｄｅｒｓｏｎ．“ＢＯＩＮＣ：Ａ　Ｓｙｓｔｅｍ　ｆｏｒ　Ｐｕｂｌｉｃ—Ｒｅｓｏｕｒｃｅ　

Ｃｏｍｐｕｔｉｎｇ　ａｎｄ　Ｓｔｏｒａｇｅ”．５ｔｈ　ＩＥＥＥ／ＡＣＭ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　

ｉｎｔｒａｃ－ｔａｂｌｅ　ｐｒｏｂｌｅｍｓ　ｉｎ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｂｉｏｌｏｇｙ［Ｊ］．Ｃｏｍｐｕｔａ—　

ｔｉｏｎａｌ　Ｇｅｎｏｍｉｃｓ，２００２：６３４－６５４．　

Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｇｒｉｄ　Ｃｏｍｐｕｔｉｎｇ，Ｎｏｖ．８　２００４，Ｐｉｔｔｓｂｕｒｇｈ，ＰＡ．　

３６５—３７２．　

［１２】Ｄａｖｉｄ　Ｐ．Ａｎｄｅｒｓｏｎ，Ｅｒｉｃ　Ｋｏｒｐｅｌａ，Ｒｏｍ　Ｗａｌｔｏｎ．Ｈｉｇｈ—Ｐｅｒｆｂ卜　

ｍａｎｃｅ　Ｔａｓｋ　Ｄｉｓｔｉｒｂｕｔｉｏｎ　ｆｏｒ　Ｖｏｌｕｎｔｅｅｒ　Ｃｏｍｐｕｔｉｎｇ【Ｊ］，　

Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｆｉｒｓｔ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　ｅ—Ｓｃｉｅｎｃｅ　

ａｎｄ　Ｇｒｉｄ　Ｃｏｍｐｕｔｉｎｇ，２００５：１９６－２０３．　

［９】Ｄ．Ｐ．Ａｎｄｅｒｓｏｎ，Ｊ．Ｃｏｂｂ，Ｅ．Ｋｏｒｐｅｌａ，Ｍ．Ｌｅｂｏｆｓｋｙ，Ｄ．Ｗｅｒｔｈｉｍｅｒ．　

ＳＥＴＩ＠ｈｏｍｅ：Ａｎ　Ｅｘｐｅｒｉｍｅｎｔ　ｉｎ　Ｐｕｂｌｉｃ—Ｒｅｓｏｕｒｃｅ　Ｃｏｍｐｕｔｉｎｇ”．　

Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　ｏｆ　ｔｈｅ　ＡＣＭ，４５（１　１），Ｎｏｖｅｍｂｅｒ　２００２：５６—　

６１．　

【１３】Ｄａｖｉｄ　Ｐ．Ａｎｄｅｒｓｏｎ，Ｃａｄ　Ｃｈｒｉｓｔｅｎｓｅｎ，Ｂｒｕｃｅ　Ａｌｉｅｎ．Ｄｅｓｉｇｎｉｎｇ　

ａ　Ｒｕｎｔｉｍｅ　Ｓｙｓｔｅｍ　ｆｏｒ　Ｖｏｌｕｎｔｅｅｒ　Ｃｏｍｐｕｔｉｎｇ【Ｊ】Ｐｒｏｃｅｅｄｉｎｇｓ　

ｏｆ　ｔｈｅ　２００６　ＡＣＭ／ＩＥＥＥ　ＳＣ１０６　Ｃｏｎｆｅｒｅｎｃｅ，２００６：１２６—１３５．　

『１０】Ｃａｄ　Ｃｈｒｉｓｔｅｎｓｅｎ，Ｔｏｌｕ　Ａｉｎａ，Ｄａｖｉｄ　Ｓｔａｉｎｆｏｒｔｈ．Ｔｈｅ　Ｃｈａｌｌｅｎｇｅ