内容发布更新时间 : 2024/6/18 19:55:47星期一 下面是文章的全部内容请认真阅读。

静态排序算法设计与分析

谢清泉

（安徽中医学院 医药信息工程学院， 安徽 合肥 230031）

摘 要： 描述静态排序算法的定义、设计思想以及具体的实现，并且从理论值和实验值两个方面入手对静态排序算法与其它排序算法的复杂度进行了详细的比较，最终根据对比结果认真分析得出各种算法的适用情况。

关键词：静态排序 算法复杂度 记录比较 记录移动 中图分类号：TP312

Desin and analysis of static sorting algorithm

XIE Qing-quan

(School of Medical information engineering,Anhui University of Traditional Chinese Mdeicine,HeiFei 230031,

China)

Abstract :The thesis not only describes the definition，design thought and concrete realization of static sorting algorithm，but also makes a detailed comparison between complexities of static sorting algorithm and other sorting algorithms from two aspects，i．e．the theoretical value and the experimental value．Finally，by careful analysis on comparison results，it draws out the applicable situations of all algorithms．

Keywords :Static sorting Algorithm complexity Record comparison Record movement

0引言

随着各行各业的飞速发展，计算机需要存储与处理的数据也在以惊人的速度增加。在如此庞大的数据群中，人们为了便于检索，通常希望能在计算机中保存的数据是按关键字值大小排列的有序表。在现今的计算机系统中，有相当大的一部分CPU时间开销是用于对数据的排序整理上的，而在这一部分CPU时间开销中，记录移动所引起的CPU时间开销又占据了相当大的一部分，并且如果待排序的记录相当大(即每个记录所占空间较多)时，记录移动所引起的CPU时间开销将对整个数据排序的CPU时间开销起到决定性的作用。因此，学习和研究各种排序算法，分析并设计出高效适用的排序算法，是摆在计算机科学工作者面前的重要课题之一。为了解决大量的记录移动而引起的CPU时间开销问题，本文提出了静态排序算法。这是一种记录移动次数(2n)恒定的稳定的内部排序算法。

1算法的定义与核心思想

1．1定义

静态排序算法是一种通过对数组Value［1…n］中任意两个记录比较来计算出每个记录在已排序数组中的索引值并把其储存在数组Index［1…n］中，进而由Result［Index［i］］=Valu［i］直接得到已排序数组Result［1…n］以达到对数据排序的目的稳定的内部排序算法。 1．2核心思想

每个记录在已排序数组中的索引值与其所在的数组中比它本身大(小)的记录的个数有关。具体而言，若在一个数组中小于记录A的记录有k(0＜=k＜n－1)个，则当对该数组排序后所得到的数组中记录A的索引值一定为k(规定:若Value［i］==Value［］j且i＜j则Value［i］＜Value［j］)。由原数组记录值及各个记录在已排序数组中的索引值直接构成有序数组。

2算法的实现

1

收稿日期：2012-4-10； 修改日期：2012-4-11

谢清泉 男 09713044 09医软（1）班

2．1排序实现

静态排序算法的实现过程主要分为三步。

第一步 通过记录值比较来求得各个记录在已排序数组中的索引值。求索引值的过程中有两种不同的情况。情况一:数组中任意两个记录的值大小都不相同，此时在数组中比记录A的值小的记录的个数则为记录A在已排序数组中的索引值。情况二:数组中至少存在两个记录的值相同，假设这两个值相同的记录分别为记录C和记录D，此时比记录C和记录D的值(假设记录D比记录C在原数组中的索引值大)小的记录的个数则不可能同时是记录C和记录D在已排序数组中的索引值。为了保持静态排序是稳定排序的特性，假设记录D的值要比记录C的值大。综合上述两种情况所述，若记录X的值小于比其索引值大计算机应用与软件2012年的记录Y的值则记录Y在已排序数组中的索引值加1，否则记录X在已排序数组中的索引值加1。当对数组中任意两个记录进行比较后，就可以得到所有记录在已排序数组中的索引值。

第二步 由数组Value［1…n］与数组Index［1…n］直接构成有序数组。其中巧妙地应用了两个数组相同位置的对应关系，即Index［i］中存储的索引值恰巧是Value［i］在已排序数组中的索引值。因此，可以得出Result［Index［i］］=Value［i］。这是一个有序有目的地插入记录的过程。当遍历了整个数组Index［1…n］后，所有的记录就有序地插入到了结果数组中，最终得到有序数组Result［1…n］。

第三步 把结果数组Result［1…n］中的所有记录拷贝到原数组Value［1…n］中，最终实现原数组的排序目的。下面是用算法语言描述静态排序的过程。静态算法如算法1所示。 算法1 StaticSort

输入:n个记录的无序数组Value［1…n］。 输出:n个记录的有序数组Value［1…n］。

1．StaticSort(Value) 过程:StaticSort(Value) 1．Index［N］←{0}; 2．for i←1 to n 3．for j←i+1 to n

4．if Value［i］＞Value［j］then Index［i］++

5．else Index［j］++ 6．end for 7．end for 8．for i←1 to n

9．Result［Index［i］］=Value［i］ 10．end for 11．for i←1 to n

12．Value［i］=Result［i］ 13．end for 2．2测试结果

如图1所示:原先数组是一个无序数组，调用静态排序算法排序后得到一个有序的数组，从而验证了静态排序算法的正确性。

图1测试结果

3算法及测试结果的分析

表1是在测试静态排序算法过程中各变量值及存储值的变化情况(表中CC是记录的比较次数)。

表1过程变量值 Array Vaule[6] Index[6] Index[6] Index[6] Index[6] Index[6] Index[6] Result[6] CC Train 0 26 0 2 2 2 2 2 12 1 43 0 1 3 3 3 3 23 2 12 0 0 0 0 0 0 26 3 74 0 1 2 3 5 5 43 4 54 0 1 2 3 3 4 54 5 23 0 0 0 1 1 1 74 5 4 3 2 1 1 2 3 4 5

从表1可得每一趟比较都会得出在数组

2

收稿日期：2012-4-10； 修改日期：2012-4-11

谢清泉 男 09713044 09医软（1）班

中比该记录小的记录的个数，这个数值也正好是该记录在已排序数组中的索引值。分析静态排序的效率: 时间复杂度:

各种算法的记录比较次数的理论值如表3所示。

表3记录比较 Method Comparison frequency Static Sort Bubble Sort Insert Sort Shell Sort Select Sort Quick Sort Merge Sort n(n－1)/2 (n－1，n(n－1)/2) (n－1，(n+2)(n－1)/2)

Y??i?n(n?1)/21n?1 需进行n(n－1)/2次比较，且移动记录2n次。因此，总的时间复杂度为Ο(n)。 空间复杂度:

需要借助一个长度为n的整型数组空间和一个原数组相同的数组空间。所以空间复杂度为О(n)。

2(n1.3,n1.5) n(n－1)/2 (nlog2n/2,n(n?1)/2) (nlog2n/2,(nlog2n/2?n?1)/2)

4各种算法的比较与分析

4．1各种算法的平均复杂度

如表2所示，从时间复杂度上看，静态排序、起泡排序、插入排序、选择排序的平均时间复杂度均为Ο(n)，而希尔排序、快速排序和归并排序的平均时间复杂度均为Ο(nlog2n)。从空间复杂度上来看，起泡排序、插入排序、希尔排序、选择排序仅需一个存储空间，空间复杂度为О(1)。静态排序与归并排序都需要与n同级别的空间，空间复杂度为О(n)。而快速排序需要的空间与原数组中记录的顺序有关，需要(log2n，n)个存储空间，空间复杂度为О(n)。

表2Method Static Sort Bubble Sort Insert Sort Shell Sort Select Sort Quick Sort [4]各种算法的记录移动次数的理论值如表4所示。

表4记录移动 Method Static Sort Bubble Sort Insert Sort Shell Sort Select Sort Quick Sort Merge Sort Mobile number 2n (0，3n(n－1)/2) (0，(n+4)(n－1)/2) 2(3n1.3,3n1.5) (0，3(n－1)) (3nlog2n/2,3n(n?1)/2) (3nlog2n/2,(3nlog2n?n?1)/2

算法复杂度 Space complexity О(n) О(1) О(1) О(1) О(1) (o(nlog2О(n)) 2224．2．2根据记录比较与移动次数的实验值分析比较算法

以下四张图是根据1000次实验得到的数据绘制而成的。为了真实地模拟实际中的排序问题，每次的测试数据都由随机数构造而成。

图2是各种排序算法中记录移动次数的

Time complexity o(n) o(n) o(n) (nlog22n) o(n) o(nlog2n) n),总体比较，从图中可以看出起泡排序的记录移动次数是最多的，且比其它的排序方法的移动次数要多很多，插入排序的移动次数次之。其余五种排序方法的移动次序要少很多。

3

Merge Sort o(nlog2n)

О(n)

4．2各种算法的记录的比较次数与移动次数 4．2．1根据记录比较与移动次数的理论值分析比较算法

收稿日期：2012-4-10； 修改日期：2012-4-11 谢清泉 男 09713044 09医软（1）班