试述基于C语言排序算法改善和应用

摘 要：介绍了程序语言中排序的原理及应用，阐述了基于C语言的三种主要排序策略，提出了每种排序策略的改善，计算出改善后算法的时间复杂度，编写了每种排序策略程序设计的主要语句，通过实例应用，对每种排序策略的算法改善前后进行对比，证明了改善后算法的优越性。
关键词：C语言；排序；改善；应用
：A
1 引言
我们日常生活中经常会碰到一些需要按顺序排列的情况，诸如大小、高矮等，这些一般都是排列对象数量较小、凭人力在有限的时间内能够完成的任务。本文讨论的排序基于C语言排序的算法改善与应用论文资料由论文网www.udooo.com提供,转载请保留地址.是面向计算机程序处理的，是计算机程序设计中经常需要进行的一类操作，可以定义为：将一组杂乱无序的记录或数据元素通过一定的策略重新排列为按某个关键字的有序序列[1]。
在计算机程序设计中所使用的排序按所访问的存储器不同可以分为内部排序和外部排序；按相同关键字处理策略的不同可以分为稳定排序和不稳定排序；按计算机需要进行运算的时间复杂度和空间复杂度的大小，可以分为好、平均、差等类别，其时间复杂度和空间复杂度越小代表排序算法占用计算机资源越少，该排序策略就越好[2]。
基于C语言的排序一般有七种：选择排序，插入排序，起泡排序，快速排序，堆排序，归并排序，基数排序，其中最主要的是选择法、插入法、起泡法三种，本文主要就以上三种策略进行讨论。

2 三种排序及其改善策略简述

2.1 选择排序

基本策略：在待排序数据元素中持续选择最大（最小）的元素放在新序列的第一位、第二位……，直到所有数据全部选择完毕。用语言描述排序过程为：第一次从原序列中选择最大的数，放在第一位，第二次从剩下的序列中选择最大的数放在第二位，以此类推，最后将最小的数放在最后一位，从而完成排序[3]。
这种排序存在一个理由：没有考虑原序列的初始排序情况，即使原来的序列元素已经按从大到小排列，程序也必须执行次比较，时间复杂度为，如果原序列元素庞大，就会占用许多系统资源，造成不必要的浪费。
改善策略：在待排列序列中将数据元素两两比对，大者上升，上升的数据元素再次两两比对，大者上升，直到结束。排序过程为：在一棵二叉树上，从底层开始，将数据元素两两比较，选择较大的一个上升，再次将第二层的数据元素进行两两比较，选择较大的一个上升，直到选出最大的一个，放在二叉树顶层，然后将这个最大数所在结点全部清空，再从最底层进行两两比较，依次循环，选出最小的一个，完成排序过程，改善的选择排序又叫树形选择排序或者锦标赛排列。
这种排序策略每选择一个较大元素需要进行比较，其时间复杂度为，相对原来的基本策略，可以节约系统资源。
本算法的主要语句：

2.2 插入排序

基本策略：将待排序的数据元素插入到已经排序的数据序列中，得到一个新的序列，直到所有待排序的元素全部插入完毕。递增排序过程为：首先将待排序序列的第一个元素看作有序序列，将第二个元素拿来与之比较，比其大则插在其后面，反之插在前面；其次再将得到的新序列看作有序序列，将第三个元素拿来从前向后比较，插到比自身大的元素之前，依次插入，直到最后一次元素插入完毕，完成排序过程[4]。
直接插入排序策略每插入一个元素都要从新序列的首部开始，其时间复杂度为，随着待排序元素的增加，其占用的时间和空间就越多，增加系统负担。
改善策略：将待排序的元素插入到已排序的序列中，不是从头开始比较，而是从中间开始比较，确定应该插入在前一半还是后一半中，再从这一半的中间比较，确定更小的一半，最终找到合适的位置插入。
本算法的主要语句：
改善的插入排序又叫折半排序，其空间占用不变，但在时间上减少了元素相互比较的次数，但没有减少元素的移动次数，其时间复杂度仍为。

2.3 起泡排序

基本策略：起泡排序的核心思想是“比较+交换”，两两比较，逆序交换，直到全部比较并交换完毕。递增排序过程为：将前二个元素比较，如果第一个大，则将二个数交换，再进行第二个第三个元素的比较，逆序交换，直到最大的数沉到最后；然后再次从头开始，将前二个元素比较，重复过程，直到第二大的元素沉到倒数第二个位置，如此循环，完成排序过程[5]。
起泡排序的平均时间复杂度为。如果原序列为正序序列，循环比较还是要进行到底，需要N-1次比较，如果待排序元素庞大，会产生不必要的浪费。
改善策略：以标准元素为中心，按大小前后列队，再将前后队伍以此策略按大小列队，最终完成排序。排序过程为：选择待排序序列第一个元素作标准，将其他元素与其比较，小的列前面，大的列后面，然后分别在前后部分内部按上述策略列队，最终完成所有元素的递增排序，改善后的起泡排序可以叫列队排序。
本算法主要语句如下：
If （low>high）{
Pivotloc=partition（L，low，high）；
Qsort（L，low，pivotloc-1）；
Qsort（L， pivotloc+1，high）；}
改善后的排序策略在最坏的情况下时间复杂度为，但在待排序序列为完全正序的情况下，其最好的时间复杂度为。

3 排序策略实例应用

3.1 二叉树选择排序

设有{65，54，78，99，86，27，42，67}序列需要排序，用二叉树选择排序法，第一遍比较选出最大的数99，如图1所示，第二遍比较选出次大的数79，如图2所示，依次比较，最终得到排序结果{16，30，41，52，53，68，79，99}。
图1 二叉树选择排序第一遍比较
图2 二叉树选择排序第二遍比较

3.2 折半插入排序

设有一个有序序列{54，65，78，86，99}，插入一个数27，与其中间元素78比较，确定更小的范围{54，65，78}，再次与其中间元素65比较，确定{54，65}，再确定合适插入的位置，得到{27，54，65，78，86，99}，如此循环，将所有元素插入完毕，从而完成排序。

3.3 列队起泡排序

设有{65，54，78，99，86，27，42，67}序列需要排序，按列队起泡策略，
第一次列队得{54，27，42，65，78，99，86，67}；
第二次列队得{27，42，54，65，67，78，99，86}；
第三次列队得{27，42，54，65，67，78，86，99}，完成递增排序。
4 总结
讨论了C语言中最重要、最常用的三种排序策略：选择排序法、插入排序法、起泡排序法，分析各种策略的基本排序过程，探讨各策略改善后的排序过程，编写了主要程序语句，通过计算时间复杂度对各种策略改善前后进行对比，结合实例应用，结果表明：三种排序的改善策略具有良好的优越性，可以很好地应用于程序设计中，是节约系统资源的有效途径。
参考文献
[1] 谭浩强.C程序设计（第2版）[M].北京：清华大学出版社，1999.
[2] 严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，1994.
[3] 王芸.选择法排序在C语言中的实现策略探讨[J].科技信息，
2011（23）：89-91.
[4] 达文姣，等.链式存储结构上直接插入排序算法的研究与实现
[J].自动化与仪器仪表，2011（6）：40-43.
[5] 梁凤兰.C语言中常用的三种排序策略的探讨[J].甘肃科技纵
横，2006（5）：16-17.
作者简介：
李支元（1975-），男，硕士，讲师.研究领域：多因素评估决策系
统.