发布时间 : 星期二 文章基于数据结构的选择排序算法剖析与改进更新完毕开始阅读b93f1f6d58fb770bf78a55bf
龙源期刊网 http://www.qikan.com.cn
基于数据结构的选择排序算法剖析与改进
作者：李 崇
来源：《现代电子技术》2010年第06期
摘 要:排序在数据处理中起着非常重要的作用。选择排序算法是数据结构中的一种基本的排序算法,运用极其广泛。这里对基本选择排序的算法进行剖析,继而提出一种改进的思路,形成改进型的选择排序。其特点是在比较的过程中将被交换数据的下标进行保存,在选择下一个目标时只需在最后一次交换的位置与待排纪录之间进行,从而大大地减少了比较的次数。从时间复杂度、空间复杂度与稳定性进行比较,体现出其优越性能。 关键词:选择排序;算法;时间复杂度;空间复杂度 中图分类号:TP311文献标识码:A 文章编号:1004-373X(2010)06-084-03
Research on Sorting Selective Algorithm Based on Data Structure LI Chong
(Chongqing Vocational Institute of Engineering,Chongqing,400037,China)
Abstract:Sorting plays an important role in data processing.The widely used selective algorithm is a basic sorting way in the data structure.This research analyses the basic selective sorting
algorithm,promotes improving ways,determines an improved selective sorting way.In this way the number of comparison is greatly reduced because only the subscript of the transferred data is stored in the process of comparison,and the next object is chosen between the last transferred and the to-be-sorted data.This research also compares them in time complexity,space complexity and stability,and presents excellent performance of the improved way.
Keywords:selective sorting;algorithm;time complexity;space complexity 0 引 言
一个好的排序算法主要体现在排序时间的快慢和查找效率上。如何设计一个好的排序算法在数据处理中是非常重要的。目前,常见的一些排序算法有插入排序、选择排序、冒泡排序、快速排序、希尔排序等。这些排序算法在数据处理的应用中各有优缺点。这里着重以选择排序为例,通过对其算法设计思路和排序的时间复杂度、空间复杂度及排序的稳定性进行分析,从而提出一些改进的排序思路,以提高其排序的效率。 1 基本选择排序算法思路
龙源期刊网 http://www.qikan.com.cn
选择排序算法思想是:对于待排序的n个对象,对它们进行逐趟扫描。对于第i趟(i=0,1,2,…,n--2)扫描,在后面的n-i个待排序对象中选出关键码最小或最大(从小到大的排序
选最小,从大到小的排序选最大)的对象,作为有序对象序列的第i个对象。当到第n-2趟时完成。因为最后待排序对象还剩一个数据,就不用再选了。 目前基本的选择排序算法有以下几种: (1)直接选择排序。
直接选择排序算法的设计思路如同前面所述,对于待排序的n个对象V～
。首先在V～
V中选出关键字最小的对象,如果它不是对象V,则将它与V交换。然后再从V[1] ～V中找出关键字最小的对象,如果它不是对象V[1],则将它与V[1]交换。以此类推,直到排至V时结束。 直接选择排序的关键字比较次数与对象的初始值无关。第i趟选择所需的比较次数为n-i-1(i=0,1,2,…,n-3,n-2)次。因此,对于n个对象的排序序列,总的关键码比较次数为: KCN=∑n-2i=0(n-i-1)=n(n-1)/2
另外,通过上述算法能清楚地分析得出:当找到第一个关键码最小的记录时需要比较n-1次,找到关键码次小的记录需要比较n-2次。以此类推,找到第i(i=0,1,2,…,n-3,n-2)个关键码时需要比较n-i次。因此,对于待排序的n个对象进行一次直接选择排序所需要的总的比较次数为: (n-1)+(n-2)+ …+2+1=n(n-
故直接选择排序的时间复杂度为O(n2)。 (2)锦标赛排序。
锦标排序算法的思路与体育比赛时的淘汰赛类似。首先取得待排序的n个对象的关键码,进行两两比较,得到个比较的优胜者(关键码小者),作为第一步比较的结果保留下来。然后再对这个关键码进行两两比较,…,如此重复,直到选出第一个关键码最小的对象为止,并将关键码最小的对象的参选标志进行修改。如果n不是2的k次幂,则将剩余的单个叶结点直接补足到满足2k-1
例如关键码为(5,3,2,9,1,8,7,4)的一组对象,其所构成的胜者树如图1所示,树根即为最小的关键码,然后把根结点的参选标志进行修改。在进行第二趟比较时,只需对修改了参选标志的子树进行重新比较,如图2所示(▲表示已经修改了参选标志的对象),这样以后每次的比较次数为O(log2 n)。 图1 胜利树 图2 修改后的胜利树