一种新的排序算法

摘 要：提出了一种新的排序算法：端点排序算法。其方法为：依次找出数据总数为N的数列最小和最大值，把二者放在本次所排数列的两端，再把剩余两端之间的数据总数为N-2的数列的最小值和最大值找出，放在此数列的两端，依此类推，直至数列中间，实现整个数组的排序。实验表明，该算法具有与冒泡排序更快的性能。在数据个数较多的情况下优于选择排序。

关键词：排序算法； 端点排序算法； 冒泡排序算法； 选择排序算法

中图分类号：TN919-34 文献标识码：A 文章编号：1004-373X(2011)24-0080-02

A New Algorithm：Endpoint Sort Algorithm

AN Chao-hui, QIAN Jian-min

(Information Science & Technology School, Shanghai 201620, China)

Abstract： A new sorting algorithm, endpoint sort algorithm is proposed. The method (assuming ascending order) is to find the minimum and maximum data values whose data total number is N array first, and then exchange the minimum one with the first data of the array, and exchange the maximum one with the last data of the array; after that, find the minimum and maximum data values in the residual data whose data total number is N-2 array, and then exchange the minimum one with the second data of the original array, and exchange the maximum one with the N-1 data of the original array, and so forth, until the entire array has been sorted. Experiments show that the endpoint sort algorithm is faster than the bubble one, and is faster than the selection sort algorithm when the array has more than 50 000 data.

Keywords： sort algorithm; endpoint sort algorithm; bubble sort algorithm; selection sort algorithm

0 引 言

排序(Sorting),就是将杂乱无章的数据,通过一定的方法按特定顺序排列的过程。由于排序是计算机科学中一项复杂而重要的技术,无论在系统软件还是在应用软件中使用频率都很高,有资料表明,在一些商用计算机上,用在排序上的CPU 时间达到20%~60%。在日常生活中也经常需要对所收集到的各种数据信息进行处理,这些数据处理中经常用到的核心运算就是排序。例如图书管理员将书籍按照编号排序放置在书架上,方便读者查找; 计算机的资源管理器可以选择按名称、大小、类型等来排列图标。排序已被广泛应用在几乎所有的领域，具有非常重要的作用。

1 算法描述与分析

对于一组无序数列而言，必有其最大和最小值，端点排序（假设按升序排列）是首先把序列中的最小值与最大值找出来，把最小值与数列第一个值交换，把最大值与数列最后一个值交换。然后把两端之间数列中的最小值与最大值找出，并分别与本次所要排序数列的第一个和最后一个数据交换。依此类推，直到数列的中间。

假设原有无序数列存放有N个数据，如图1所示。则第1次把此N个数的最小值MIN(N)和最大值MAX(N)找出，把MIN(N)与第1个数交换，把MAX(N)与第N个数交换，如图2所示。然后把剩下中间N-2个数的最小值MIN(N-2)和最大值MAX(N-2)找出，并分别与原数列的第2个数和第N-1个数相交换，之后以此类推。若N为偶数，则要进行N/2次，若N为奇数则要进行(N-1)/2次。

后端点排序算法：

设待排序数据存储于数组a［N］。

void swap(int *x ,int *y);

void endPoingSort(int * a，int N)

{

int i,j,min,max;

min=0;

max=N-1;

for(i=1;i

{

for(j=min;j

{

if(a［max］

if(a［min］>a［j］)swap(&a［min］,&a［j］);

}

min++;

max--;

}

}

void swap(int *x ,int *y)

{

int t;

t=*x;

*x=*y;

*y=t;

}

2 实验结果

表1是对冒泡排序、端点排序、选择排序、插入排序用C语言在Core 2.2G上做的一个比较。表中是用冒泡排序、端点排序、选择排序处理100个、1 000个、10 000个、100 000个随机数据（由RAND函数产生）所用的时间，每一个时间值是测试20次的平均值，单位为μs。

3 结 语

实验表明，端点排队序算法实现的端点排序算法速度明显优于冒泡排序算法，在数据个数较多的情况下优于选择排序。

参 考 文 献

［1］ 严蔚敏,吴伟民.数据结构(C 语言版)［M］.北京:清华大学出版社,2002.

［2］ CORMEN T H, LEISERSON C E, RIVEST R L, et al.算法导论［M］.2版.北京:高等教育出版社,2002.

［3］ 王晓东.计算机算法设计与分析［M］.北京:电子工业出版社,2007.

［4］ 周建钦.超快速排序［J］.计算机工程与应用,2006，42(29):41-42.

［5］ 王永刚.排序算法综述［J］.电脑知识与技术,2006，29(7):1-6.

［6］ 淦艳,杨有.五种排序算法的性能分析［J］.重庆文理学院学报,2010，29(3):45-50.

［7］ 陶冶.开发自己的剖分软件以辅能测试［J］.信息技术与标准化,2007(7):42-44.

［8］ 兰超.冒泡排序算法的优化［J］.兵工自动化,2006(12):50-52.

［9］ 李宝艳,马英红.排序算法研究［J］.电脑知识与技术,2007(8):424-456.

［10］ 王向阳.任意分布数据的基数分配链接排序算法［J］.计算机学报,2000,23(7):774-778.

作者简介: 安朝辉 男，1981年出生，河南郑州人。主要研究方向为嵌入式系统。

钱剑敏 男，1953年出生，上海人，副教授。主要研究方向为片上系统与嵌入式计算机。