对排序算法的总结（共10篇）

对排序算法的总结 篇1

排序算法的算法思想和使用场景总结

总结就是把一个时间段取得的成绩、存在的问题及得到的经验和教训进行一次全面系统的总结的书面材料，它可以帮助我们有寻找学习和工作中的规律，快快来写一份总结吧。那么如何把总结写出新花样呢？下面是小编收集整理的排序算法的算法思想和使用场景总结，供大家参考借鉴，希望可以帮助到有需要的朋友。

1.概述

排序算法是计算机技术中最基本的算法，许多复杂算法都会用到排序。尽管各种排序算法都已被封装成库函数供程序员使用，但了解排序算法的思想和原理，对于编写高质量的软件，显得非常重要。

本文介绍了常见的排序算法，从算法思想，复杂度和使用场景等方面做了总结。

2.几个概念

（1）排序稳定：如果两个数相同，对他们进行的排序结果为他们的相对顺序不变。例如A={1,2,1,2,1}这里排序之后是A = {1,1,1,2,2}稳定就是排序后第一个1就是排序前的第一个1，第二个1就是排序前第二个1，第三个1就是排序前的第三个1。同理2也是一样。不稳定就是他们的顺序与开始顺序不一致。

（2）原地排序：指不申请多余的空间进行的排序，就是在原来的排序数据中比较和交换的排序。例如快速排序，堆排序等都是原地排序，合并排序，计数排序等不是原地排序。

总体上说，排序算法有两种设计思路，一种是基于比较，另一种不是基于比较。《算法导论》一书给出了这样一个证明：“基于比较的算法的最优时间复杂度是O（N lg N）”。对于基于比较的算法，有三种设计思路，分别为：插入排序，交换排序和选择排序。非基于比较的`排序算法时间复杂度为O(lg N)，之所以复杂度如此低，是因为它们一般对排序数据有特殊要求。如计数排序要求数据范围不会太大，基数排序要求数据可以分解成多个属性等。

3.基于比较的排序算法

正如前一节介绍的，基于比较的排序算法有三种设计思路，分别为插入，交换和选择。对于插入排序，主要有直接插入排序，希尔排序；对于交换排序，主要有冒泡排序，快速排序；对于选择排序，主要有简单选择排序，堆排序；其它排序：归并排序。

3.1插入排序

（1）直接插入排序

特点：稳定排序，原地排序，时间复杂度O(N*N)

思想：将所有待排序数据分成两个序列，一个是有序序列S，另一个是待排序序列U，初始时，S为空，U为所有数据组成的数列，然后依次将U中的数据插到有序序列S中，直到U变为空。

适用场景：当数据已经基本有序时，采用插入排序可以明显减少数据交换和数据移动次数，进而提升排序效率。

（2）希尔排序

特点：非稳定排序，原地排序，时间复杂度O(n^lamda)(1 < lamda < 2), lamda和每次步长选择有关。

思想：增量缩小排序。先将序列按增量划分为元素个数近似的若干组，使用直接插入排序法对每组进行排序，然后不断缩小增量直至为1，最后使用直接插入排序完成排序。

适用场景：因为增量初始值不容易选择，所以该算法不常用。

3.2交换排序

（1）冒泡排序

特点：稳定排序，原地排序，时间复杂度O(N*N)

思想：将整个序列分为无序和有序两个子序列，不断通过交换较大元素至无序子序列首完成排序。

适用场景：同直接插入排序类似

（2）快速排序

特点：不稳定排序，原地排序，时间复杂度O(N*lg N)

思想：不断寻找一个序列的枢轴点，然后分别把小于和大于枢轴点的数据移到枢轴点两边，然后在两边数列中继续这样的操作，直至全部序列排序完成。

适用场景：应用很广泛，差不多各种语言均提供了快排API

3.3选择排序

（1）简单选择排序

特点：不稳定排序（比如对3 3 2三个数进行排序，第一个3会与2交换），原地排序，时间复杂度O(N*N)

思想：将序列划分为无序和有序两个子序列，寻找无序序列中的最小（大）值和无序序列的首元素交换，有序区扩大一个，循环下去，最终完成全部排序。

适用场景：交换少

（2）堆排序

特点：非稳定排序，原地排序，时间复杂度O(N*lg N)

思想：小顶堆或者大顶堆

适用场景：不如快排广泛

3.4其它排序

（1）归并排序

特点：稳定排序，非原地排序，时间复杂度O(N*N)

思想：首先，将整个序列（共N个元素）看成N个有序子序列，然后依次合并相邻的两个子序列，这样一直下去，直至变成一个整体有序的序列。

适用场景：外部排序

4.非基于比较的排序算法

非基于比较的排序算法主要有三种，分别为：基数排序，桶排序和计数排序。这些算法均是针对特殊数据的，不如要求数据分布均匀，数据偏差不会太大。采用的思想均是内存换时间，因而全是非原地排序。

4.1基数排序

特点：稳定排序，非原地排序，时间复杂度O(N)

思想：把每个数据看成d个属性组成，依次按照d个属性对数据排序（每轮排序可采用计数排序），复杂度为O(d*N)

适用场景：数据明显有几个关键字或者几个属性组成4.2桶排序

特点：稳定排序，非原地排序，时间复杂度O(N)

思想：将数据按大小分到若干个桶（比如链表）里面，每个桶内部采用简单排序算法进行排序。

适用场景：0

4.3计数排序

特点：稳定排序，非原地排序，时间复杂度O(N)

思想：对每个数据出现次数进行技术（用hash方法计数，最简单的hash是数组！），然后从大到小或者从小到大输出每个数据。

使用场景：比基数排序和桶排序广泛得多。

5.总结

对于基于比较的排序算法，大部分简单排序(直接插入排序，选择排序和冒泡排序)都是稳定排序，选择排序除外；大部分高级排序（除简单排序以外的）都是不稳定排序，归并排序除外，但归并排序需要额外的存储空间。对于非基于比较的排序算法，它们都对数据规律有特殊要求，且采用了内存换时间的思想。排序算法如此之多，往往需要根据实际应用选择最适合的排序算法。

对排序算法的总结 篇2

数据排序是计算机编程过程中经常会遇到的一个问题,同样C语言中关于排序问题的算法也有多种。本文主要对一些常见的排序算法进行一个归纳总结,方便初学者对这一问题有一个全面的了解。

所谓数据排序,就是将一组无序的数据,按照其中的某个关键字的大小,递增或递减的排列成有序的数据序列。在C语言的学习过程当中,经常会碰到关于整数、浮点数、字符以及字符串的排序问题。一般的排序方法有:冒泡排序、选择排序、插入排序、shel(希尔)排序、快速排序、堆排序等。下面就通过具体的例子,对这些排序方法的基本思想、执行过程、算法代码进行一个总结分析。

2 各种排序算法的分析

2.1 冒泡排序

冒泡排序法是C语言当中最为常见和通用的一种排序方法。

2.1.1 基本思想

在待排序的一组数中,相邻的两个数两两比较后发现它们的顺序与排序要求相反时,就将它们互换(即:如果从小到大排序,则两两比较时,让较大的数往下沉,较小数往上冒)。如此下去,直至最终完成排序。冒泡排序过程中,如果对N个数进行排序的话,需要进行比较的轮数是N-1轮,每轮进行N-1-i次。由于在排序过程中,它的工作看起来像冒泡,所以称作冒泡排序。

2.1.2 算法代码

例:对数组aa[5]={8,5,10,7,3}的元素从小到大进行排序。

该例子用冒泡法实现的代码段如下:

2.1.3 执行过程

第一轮:8,5,10,7,3->5,8,10,7,3->5,8,7,10,3->5,8,7,3,10(交换3次)

第二轮:5,8,7,3,10->5,7,8,3,10->5,7,3,8,10(交换2次)

第三轮:5,7,3,8,10->5,3,7,8,10(交换1次)

第四轮:5,3,7,8,10->3,5,7,8,10(交换1次)

2.1.4 分析

在程序执行过程中,关系到算法性能的主要因素是循环和交换的次数,次数越多,性能越差。

对上面这个例子中包含5个元素的数组采用冒泡法进行排序,总共进行交换的次数是3+2+1+1=7次。冒泡法的特点是原理简单,但其缺点是交换次数多、效率低。

2.2 选择排序

2.2.1 基本思想

在待排序的一组数中,每轮将首数与后数进行两两比较,按大小进行交换,选出待排序数组中最小(或最大)的一个元素,放在已经排好序的数列的最后。如此下去,直至最终完成排序。冒泡排序过程中,如果对N个数进行排序的话,需要进行比较的轮数是N-1次,每轮从i+1开始到N-1为止。

2.2.2 算法代码

同上例:对数组aa[5]={8,5,10,7,3}的元素从小到大进行排序。

2.2.3 执行过程

第一轮:8,5,10,7,3->3,5,10,7,8(交换1次)

第二轮:3,5,10,7,8(交换0次)

第三轮:3,5,10,7,8->3,5,7,10,8(交换1次)

第四轮:3,5,7,10,8->3,5,7,8,10(交换1次)

2.2.4 分析

对上面这个例子中包含5个元素的数组采用冒泡法进行排序,总共进行交换的次数是1+0+1+1=3次。选择法的循环过程与冒泡法一致,它定义了作为记号的变量k赋初值为i,依次把a[k]同后面元素比较,若有元素比a[k]小,则将该元素下标赋值给k,使得变量k当中存放的永远是最小元素的下标。最后再a[k]与a[i]交换,这样就比冒泡法省下许多无用的交换,提高了效率。

2.3 直接插入排序

2.3.1 基本思想

在待排序的一组数中,先比较前两个数,按大小顺序排列好,然后每次从后面的无序数中取出第一个元素,把它插入到前面有序数的合适位置,使有序数组仍然有序,把数组元素插完也就完成了排序。

2.3.2 算法代码

同上例:对数组aa[5]={8,5,10,7,3}的元素从小到大进行排序。

2.3.3 执行过程

第一轮:8,5,10,7,3->5,8,10,7,3(交换1次)

第二轮:5,8,10,7,3(交换0次)

第三轮:5,8,10,7,3->5,7,8,10,3(交换1次)

第四轮:5,7,8,10,3->3,5,7,8,10(交换1次)

2.3.4 分析

对上面这个例子中包含5个元素的数组采用冒泡法进行排序,总共进行交换的次数是1+0+1+1=3次。直接插入排序的特点是算法简单、容易实现。它是采用逐步增加有序元素想法,直至所有元素排列完成。如果待排序数组元素不是特别多的时候,该算法的效率快是较佳的排序方法。但对于大数组,这种算法比较慢就不大适用了。

2.4 shell排序

2.4.1 基本思想

希尔算法的本质是缩小增量排序,是对直接插入排序算法的改进。先取一个小于N的整数p作为第一个增量,将待排序的一组数按增量p分割成多个组,对每个组分别进行一趟直接插入排序。然后缩小增量p的值(一般取其一半)再排序,直到p=1时完成排序。

2.4.2 算法代码

同上例:对数组aa[5]={8,5,10,7,3}的元素从小到大进行排序。

2.4.3 执行过程

第一轮:8,5,10,7,3->8,5,3,7,10(交换1次)

第二轮:8,5,3,7,10->3,5,8,7,10(交换1次)

第三轮:3,5,8,7,10->3,5,7,8,10(交换1次)

2.4.4 分析

对上面这个例子中包含5个元素的数组采用冒泡法进行排序,总共进行交换的次数是1+1+1=3次。Shell排序的优点是不管待排序数组长度多长,在分组增量p的切割下每个子组的规模都不会太大,然后用直接插入排序效率较高。后来增量p的逐渐递减,分组数逐渐减少,而各组的记录数目逐渐增多,但由于排过序,整个数组的有序性越来越清晰,所以排序的效率依然较高。所以,希尔排序在效率上比直接插人排序有很大的改进。

2.4.5 快速排序

2.4.5. 1 基本思想

在待排序的一组数中,先选择其中一个元素作为分隔点(一般选取数组中间的那个元素),然后把比该元素小的数据放在左边,大的放在右边。再按此方法对两边的数据分别再快速排序(也就是递归调用),直到整个数组有序为止。

2.4.5. 2 算法代码

同上例:对数组aa[5]={8,5,10,7,3}的元素从小到大进行排序。

2.4.5. 3 执行过程

第一轮:8,5,10,7,3->8,5,3,7,10(交换1次)

第二轮:8,5,3,7,10->3,5,8,7,10(交换1次)

第三轮:3,5,8,7,10->3,5,7,8,10(交换1次)

2.4.5. 4 分析

对上面这个例子中包含5个元素的数组采用冒泡法进行排序,总共进行交换的次数是1+1+1=3次。快速排序是对冒泡排序的一种本质改进,其优点是运算速度快,数据移动少。缺点是算法稍复杂。快速排序法中关键是对三个参数的设定,即待排序数组元素的起始下标、最后一个元素下标以及分隔元素下标的确定。

3 总结

除了上述分析的五种常见的排序方法外,还有堆排序、归并排序等。在选择排序算法的时候,要根据待排元素数目N的大小以及元素本身的初始状态来做最佳的抉择。如果N数较小,则可采取直接插入排序或选择排序;若数组本身初始状态局部或整体有序时,则可采取冒泡排序或插入排序;若N数较大,则可采取快速排序、堆排序或归并排序。

参考文献

[1]谭浩强.C程序设计[M].3版.北京:清华大学出版社,2005.

[2]谭浩强,张基温,唐永炎.C程序设计教程[M].北京:高等教育出版社,1992.

一种线性时间排序算法的实现 篇3

关键词：排序；算法；有序树；复杂性

0引言

排序是计算机科学中一项复杂而重要的技术，无论在系统软件还是应用软件中使用频率都很高。许多专家学者对排序问题讲行了深入的研究，给出了许多时间复杂度为O(n)的高效排序算法。其中有许多排序算法充分利用待排序数据的分布信息，降低了排序算法的时间复杂度；有的排序效率过分依赖于关键字的均匀分布且算法不稳，仅适用于数据位很少的一类数据排序；有的算法稳定但只针对具有均匀分布或近似均匀分布的数据。本文提出一种不依赖关键字的分布，数据位数不受限制的整型或实型数的排序，此思想亦可应用到字符型数据的排序，且时间和空间复杂度均为O(n)。

1算法思想

假定待排数据为大于0的实型数且放在数组A中。排序的主要工作是创建一棵有序树。首先找到这组数中值最大和最小的数以确定树根结点的大小，根结点为一指针类型的数组root，假定最大数的十进制阶码为max，最小数的十进制阶码为min，那么root数组大小为max-min+1即root[min..max]，root[O]指向10₀的子树根结点，root[1]指向10₁的子树根结点……root[n]指向10₀的子树根结点，中间分支结点为一大小为10的指针数组B[10]。如果把根结点所在的一层约定为第0层，那么第1层中B1[0]指向尾数中第1位值为0的子树根结点，B1[1]指向尾数中第1位值为1的子树根结点……B1[9]指向尾数中第1位值为9的子树根结点；第2层中B2[0]指向尾数中第2位值为0的子树根结点，B2[1]指向尾数中第2位值为l的子树根结点……B2[9]指向尾数中第2位值为9的子树根结点；……待排数据均放在叶子结点上，叶子结点类型为待排数据类型的单链表，数的深度取决于待排数据中尾数的最大长度len，所有叶子结点都在第len+1层。将数组A中所有的数据都插入上述树中，然后将叶子结点按从左到右输出即为—个已经排好序的有序序列。例如待排数据为{860，734，53，5，9，16，18，231，234，53*，256，378，897}，可知max=3，min=1，root大小为3即为root[1..3]，len=3，树的深度为5。对应的排序树如图1所示。

具体算法描述如下：

定义三类结点①根结点root：为一基类型为指针类型的活动数组；②中间结点branch：为一基类型为指针类型大小为10的数组，③叶子结点leaf：为一待排数据类型(可以增加一个指针用来指向其同义词结点)。

step1：找到待排数据中值最大数的十进制阶码放入max中，最小数的十进制阶码放min中，规格化十进制尾数位数最长值放len中；

step2：申请根结点root[min．．max]，其中每个元素初始化为空指针；

step3：如果待排队列为空转step5：，否则： 从待排数据中取出一个数据按下面方法插入到排序树中： (1)取出此数十进制阶码放入exp，尾数部分放tail中；所在层数depth=0；

(2)如果root[exp]为非空则转step4，否则；

(3)申请一枝结点banch，初始化为空，并由工作指针P和root[exp]指向它；depth加1；

(4)如果depth小于len继续，否则转(8)；

(5)取尾数tail的第depth位置于f中；

(6)如果P所指结点的第f位为非空，则P指向P[f]，depth加1转(4)否则；

(7)申请一枝结点banch，并由P[f]指向它，P指向当前新结点，depth加1，转(4)；

(8)取尾数tail的第len位置于f中；

(9)申请一叶子结点将待排数据元素放入，并由P[f]指向它，转step3；

step4：工作指针P指向root[exp]所指结点，depth加1，转(4)。

step5：按从左到右逐一打印输出叶子结点即为已经排好序的有序序列。

算法结束。

2算法分析

时间本算法关键在于建树，从算法中可以看出建树的时间复杂度为O(1en*n)。对于一组待排数据，其中数据的最大位数必将是一个定值常量，所以其时间复杂度为O(n)。

空间本算法辅助空间为根结点和分支结点所用的空间，最好情况为每一个中间结点都是充满的，即都有10个子结点，可以推算出如果有n个待排数据辅助结点个数为((1/(max-min+1)-1/9)／10len+1/9)n，对于给定的数max，min，len均为常量，所以空间复杂度为O(n)；最坏情况每个叶子从根结点起为单枝子树，那么n个待排数据共需1+len*n，空间复杂度仍然为O(n)。所以空间复杂度也是O(n)。

3结束语

选择排序算法总结 篇4

/***记录最大值和最小值在数组里面的位置*/class MinMaxPair{public: MinMaxPair(int _minPos = -1 , int _maxPos = -1):minPos(_minPos),maxPos(_maxPos){} size_t minPos;// 最小值在数组里面得位置 size_t maxPos;// 最大值在数组里面的位置 bool perator==(const MinMaxPair & pair) { return (this->minPos == pair.minPos && this->maxPos == pair.maxPos); }}; /** 找到一个数组里面的最大值和最小值 */MinMaxPair findMinMax(int array[] , int arraySize , int * minNumber , int * maxNumber){ if(array == NULL || arraySize <= 0 || minNumber == NULL || maxNumber == NULL) return MinMaxPair; /** 奇数个元素设置，取出第一个元素作为初始的最大值和最小值 */ int maxNumberTemp = array[0]; int minNumberTemp = array[0]; size_t maxPos=-1; size_t minPos=-1; int i = 1; if(arraySize%2 == 0)// 一共有偶数个元素，取出前两个元素，大的作为最大值的初始值，小的作为最小值的初始值 { i=2; // 比较数组前两个元素 maxNumberTemp = array[0]; minNumberTemp = array[1]; maxPos = 0; minPos = 1; if(array[0] < array[1]) {maxNumberTemp = array[1];minNumberTemp = array[0];maxPos = 1;minPos = 0; } } for (; i < arraySize ; i+=2) { /** 每次取出两个元素 */ int temp1 = array[i]; int temp2 = array[i+1]; int tempPos1 = i; int tempPos2 = i+1; /** 比较两个取出的元素 */ if(array[i] > array[i+1]) {temp1 = array[i+1];temp2 = array[i];tempPos1 = i+1;tempPos2 = i; } /** 将小者与标识的最小值比较 */ if(minNumberTemp > temp1) {minNumberTemp = temp1;minPos = tempPos1; } /** 将大者与标识的最大值比较 */ if(maxNumberTemp < temp2) {maxNumberTemp = temp2;maxPos = tempPos2; } } // 最后设置输出的元素 *maxNumber = maxNumberTemp; *minNumber = minNumberTemp; return MinMaxPair(minPos , maxPos);}

运行结果

input array is :

69 72 82 53 61 35 43 74 83 76

find the min number 35 at pos 6

find the max number 83 at pos 9

在上面的代码，如果输入数据的长度为奇数，我们就选取第一个元素作为最大值和最小值元素的初始值，并从数组的第二个元素开始每次选出两个元素；如果为偶数，那么取出前两个元素，大的作为最大值的初始值，小的作为最小值的初始值，并从第三个元素开始，每次取出两个元素

快速选择算法

排序算法（一） 篇5

首先参考大话数据结构定义一个链表类：

 

#include#define MAXSIZE 1000 using namespace std; class SqList{ public: SqList:length(0){} SqList(int length1,int value=0):length(length1) { for(int i=0;i=MAXSIZE) { return false; } data[length]=value; length++; } friend ostream& operator<<(ostream& output, SqList list); public: int data[MAXSIZE]; int length; }; void swap(int& a,int &b) { int tmp=a; a=b; b=tmp; } ostream& operator<<(ostream& output, SqList list) { for (int i = 0; i

 

冒泡排序法：

/** *冒泡排序即相邻的两者相互比较，根据需求把较大的或较小的前移或后移 *记住，两两相邻的比较是冒泡排序的特点之一 */void BubbleSort1(SqList* list){//每次遍历时把较大者后移 int length=list->length; while(length>0) { for(int i=0;idata[i] >list->data[i+1]) swap(list->data[i],list->data[i+1]); } length--; }}void BubbleSort2(SqList* list){//每次遍历时，把较小的前移 for(int i=0;ilength;i++) { for(int j=list->length-2;j>=i;j--) { if(list->data[j] >list->data[j+1]) swap(list->data[j],list->data[j+1]); } } }

选择排序法：

/** *选取排序即每次在未排序队列当中选取一个最小值，然后与第i个值进行交换，直至i为length为止； *当然，也可以选取最大值把到后面，根据需求而定 */void selectSort(SqList* list){ for (int i = 0; i < list->length; ++i) { int min = list->data[i]; int pos = i; for (int j = i+1; j < list->length; ++j) { if (list->data[j] < min) { min = list->data[j]; pos = j; } } if (pos != i) { swap(list->data[i], list->data[pos]); } }}

简单插入排序法：

/** *遍历链表，把每个元素插入到正确位置 */void InsertSort1(SqList *list){ for (int i = 1; i < list->length; ++i) { int j = i - 1; for (; j >=0; j--) { if (list->data[i] >list->data[j]) break; } int tmp = list->data[i]; for (int k = i; k >j+1; --k) { list->data[k] = list->data[k - 1]; } list->data[j + 1] = tmp; }}void InsertSort2(SqList *list){ for (int i = 1; i < list->length; ++i) { if (list->data[i] < list->data[i - 1]) { int tmp = list->data[i]; int j = i-1; for (; j >= 0 && list->data[j] >tmp; --j) {//查找的同时，进行后移操作 list->data[j + 1] = list->data[j]; } list->data[j + 1] = tmp; } }}

希尔排序法（简单插入排序的改进）：

对排序算法的总结 篇6

停机位分配作业关系到整个机场的系统运作,其作用相当重要.通过分析航班占用停机位的特性,建立停机位分配问题的.排序模型,然后考虑“先到先服务”的规则并通过引入机位标号函数和航班标号函数设计一种求解模型的标号算法,该算法的计算复杂性为O(nm),最后将该算法应用于一个算例,说明该算法为利用计算机进行停机位自动分配并优化停机位结果提供了一种可行手段.

作 者：文军 孙宏 徐杰 梁志杰 作者单位：文军,孙宏(西南交通大学,交通运输学院,四川,成都,610031;中国民用航空飞行学院,空中管制系,四川,广汉,618307)

徐杰,梁志杰(西南交通大学,交通运输学院,四川,成都,610031)

最简单的排序算法(续) 篇7

虽然实现原理很简单,但毕竟还是用到了记事本这个软件。实际上根据珠排序的原理,自己DIY一台专门用来进行数据排序的计算机也是很容易的,使用到的设备,仅仅是几个逻辑门电路和移位寄存器。如果手头没有门电路的元件,那么用逻辑门电路模拟器也能实现设计,笔者使用的是Logisim,可从网上免费下载到。

需要解决的关键问题是如何利用逻辑门,搜索出字符串中所有的“10”,使之变成“01”。在一个字符串中搜索数据,首先,需要取出字符串中第一个和第二个数字,把数字输入到变量中;其次,匹配两个变量的值是否是“1”和“0”,若是则把两个变量的值重置为“0”和“1”,若不是则不用重置;再次,继续取出后续的数字进行匹配。如此多的步骤,实现起来似乎相当复杂,但实际上,只需要四个逻辑门,就可以完成任务。

这个装备需要用到与门和异或门两种逻辑门,与门的作用是当两个输入端均为1的时候,则输出为1,否则输出为0,用符号表示。异或门的作用是当两个输入端输入的值不相等时,输出为1,若两个输入端输入的值相等,则输出为0,用符号表示。

电路有三个输入端,一个输出端,用一个实际的例子能够更好地说明这个逻辑电路的作用(如下页图2)。假设初始值是“101”,首先,第一个初始数值“1”和第二个初始数值“0”进行逻辑门的与操作,得到中间结果A是“0”;其次,第二个初始数值“0”和第三个初始数值“1”进行逻辑门的与操作,得到的中间结果B是“0”;再次,第一个初始数值“1”和中间结果A即“0”作异或操作,得到的中间结果C是“1”;最后,中间结果C“1”和中间结果B“0”作异或操作,得到的结果是“1”。于是输入初始值“101”,得到结果为1。

不妨再来一个例子,假设初始值是“011”,首先,第一个初始数值“0”和第二个初始数值“1”进行逻辑门的与操作,得到中间结果A是“0”;其次,第二个初始数值“1”和第三个初始数值“1”进行逻辑门的与操作,得到的中间结果B是“1”;再次,第一个初始数值“0”和中间结果A即“0”作异或操作,得到的中间结果C是“0”;最后,中间结果C“0”和中间结果B“1”作异或操作,得到的结果是“1”。于是输入初始值是“011”,得到结果为“1”。

大家也许会说,在这里可一点也看不出“1”和“0”对调位置的效果。别着急,想象一下,如果对字符串“101”作“将10变为01”的替换,那么这个字符串会变成“011”,中间那个数字是“1”。如果对字符串“011”作替换,那么这个字符串仍然是“011”,中间那个数字仍然是“1”。上面的那个逻辑电路的作用,就是把三个数字作为一组,计算出搜索和替换后中间那个数值的值。

例如,字符串“1011001101011110”,如果我们想要将字符串中的“10”变成“01”,可以先把整个字符串首尾各补一个“0”,使其变成“010110011010111100”,则可以把字符串放进一个移位寄存器中(如图3)。首先,逻辑电路获得的数据是“010”,逻辑运算后得到结果是“0”;接着,移动一位,输入的数据是“101”,得到的结果是“1”;然后,再移动一位,输入数据是“011”,得到的结果仍然是“1”,以此类推。整个数据全部经逻辑电路运算后,得到的字符串就是“0110101010111101”,把初始字符串和经逻辑运算后的字符串并列排放,我们就能看出替换的效果了(如图4)。

初始字符串:1011001101011110

结果字符串:0110101010111101

既然能够对一行字符串进行替换操作,那么对多行的字符串进行替换操作其原理也完全相同。这样的话,就能很容易打造出一个实体的排序计算机,所需要的仅仅是两种逻辑门和若干移位寄存器。

对排序算法的总结 篇8

对于数据的处理工作，排序是其最基本的运算之一，在当今的计算机系统中，花费在排序上的时间占系统CPU运行时间的很大比重。有资料表明，在一些商用计算机上，在排序上的CPU时间达到20%至60%。为了提高计算机的工作效率，人们提出了各种各样的排序方法和算法。这些算法有力地发展、并充分地展示了算法设计的某些重要原则和高超技巧。因此，对于计算专业人员来说掌握排序算法是十分重要的。

二、排序算法简介

本次课程中我们将介绍六种排序方法：插入排序，选择排序，冒泡排序，希尔排序，快速排序及二路归并。

<1>直接选择排序(Selection Sort)：简单的选择排序，它的比较次数一定：n(n-1)/2。也因此无论在序列何种情况下，它都不会有优秀的表现(从上100K的正序和反序数据可以发现它耗时相差不多，相差的只是数据移动时间)，可见对数据的有序性不敏感。它虽然比较次数多，但它的数据交换量却很少。所以我们将发现它在一般情况下将快于冒泡排序。

<2>直接插入排序(Insertion Sort)：简单的插入排序，每次比较后最多移掉一个逆序，因此与冒泡排序的效率相同。但它在速度上还是要高点，这是因为在冒泡排序下是进行值交换，而在插入排序下是值移动，所以直接插入排序将要优于冒泡排序。直接插入法也是一种对数据的有序性非常敏感的一种算法。在有序情况下只需要经过n-1次比较，在最坏情况下，将需要n(n-1)/2次比较。

<3>冒泡排序(Bubble Sort)：将相邻的两个数据元素按关键字进行比较，如果反序，则交换。对于一个待排序的数据元素序列，经一趟排序后最大值数据元素移到最大位置，其它值较大的数据元素向也最终位置移动，此过程为一次起泡。然后对下面的记录重复上述过程直到过程中没有交换为止，则已完成对记录的排序。

<4>快速排序(Quick Sort)：是冒泡排序的改进，它通过一次交换能消除多个逆序，这样可以减少逆序时所消耗的扫描和数据交换次数。在最优情况下，它的排序时间复杂度为O(nlog2n)。即每次划分序列时，能均匀分成两个子串。但最差情况下它的时间复杂度将是O(n^2)。即每次划分子串时，一串为空，另一串为m-1(程序中的100K正序和逆序就正是这样，如果程序中采用每次取序列中部数据作为划分点，那将在正序和逆时达到最优)。从100K中正序的结果上看“快速排序”会比“冒泡排序”更慢，这主要是“冒泡排序”中采用了提前结束排序的方法。有的书上这解释“快速排序”，在理论上讲，如果每次能均匀划分序列，它将是最快的排序算法，因此称它作快速排序。虽然很难均匀划分序列，但就平均性能而言，它仍是基于关键字比较的内部排序算法中速度最快者。

<5>希尔排序(Shell Sort)：增量的选择将影响希尔排序的效率。但是无论怎样选择增量，最后一定要使增量为1，进行一次直接插入排序。但它相对于直接插入排序，由于在子表中每进行一次比较，就可能移去整个经性表中的多个逆序，从而改善了整个排序性能。希尔排序算是一种基于插入排序的算法，所以对数据有序敏感。

<6>归并排序(Merge Sort)：归并排序是一种非就地排序，将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并，将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大，那将不适合。但可改造成索引操作，效果将非常出色。

三、排序方法的选择

因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法很重要

(1)若n较小，可采用直接插入或直接选择排序。

当记录规模较小时，直接插入排序较好，它会比选择更少的比较次数;

但当记录规模较大时，因为直接选择移动的记录数少于直接插人，所以宜用选直接选择排序。

这两种都是稳定排序算法。

(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜(这里的随机是指基准取值的随机，原因见上的快速排序分析);这里快速排序算法将不稳定。

(3)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。

快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短;

堆排序虽不会出现快速排序可能出现的最坏情况。但它需要建堆的过程。这两种排序都是不稳定的。

归并排序是稳定的排序算法，但它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。

(4)特殊的箱排序、基数排序

它们都是一种稳定的排序算法，但有一定的局限性：

1>关键字可分解。

2>记录的关键字位数较少，如果密集更好

3>如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。

四、AS中排列数组

1.申请一个长度为n的数组A：

var n:Number = 400;

var A:Array = new Array(n);

for (i=0; i < n; i++) {

A[i] = i;

}

trace(A);

2.将长度为n的数组打乱次序：

for (i=0; i < n; i++) {

var ran = int(Math.random()*n);

var temp = A[i];

A[i] = A[ran];

A[ran] = temp;

}

trace(A)

3.将数组中的所有元素倒排序：

A.reverse();

trace(A)

五、AS实现排序算法：

在执行各各排序算法之前，已经默认存在一个乱序的数组 A[400]，默认代码：

var n:Number = 400;

var A:Array = new Array(n);

for (i=0; i < n; i++) {

A[i] = i;

}

for (i=0; i < n; i++) {

var ran = int(Math.random()*n);

var temp = A[i];

A[i] = A[ran];

A[ran] = temp;

}

1.直接插入排序

for (i = 0; i < n; i++) {

var temp = A[i];

for (j = i; j > 0 && temp < A[j - 1]; j--) {

A[j] = A[j - 1];

A[j - 1] = temp;

}

}

2.直接选择排序

for (i = 0; i < n - 1; i++) {

var s:Number = i;

for (j = s + 1; j < n; j++) {

if (A[j] < A[s]) {

s = j;

}

}

var temp = A[i];

A[i] = A[s];

A[s] = temp;

}

3.冒泡排序

for (i = 0; i < n; i++) {

for (j = i; j < n; j++) {

if (A[i] > A[j]) {

var temp = A[i];

A[i] = A[j];

A[j] = temp;

}

}

}

4.希尔排序

var increment = 6;

while (increment > 1) {

increment = int(increment / 3 + 1);

Shellpass(increment);

}

function Shellpass(c) {

for (i = c; i < n; i++) {

if (A[i] < A[i - c]) {

var temp = A[i];

j = i - c;

do {

A[j + c] = A[j];

j = j - c;

} while (j > 0 && temp < A[j]);

A[j + c] = temp;

}

}

}

5.快速排序

function QuickSort(A, low, hig) {

var i = low, j = hig;

var mid = A[int((low + hig) / 2)];

do {

while (A[i] < mid) {

i++;

}

while (A[j] > mid) {

j--;

}

if (i <= j) {

var temp = A[i];

A[i] = A[j];

A[j] = temp;

i++;

j--;

}

} while (i <= j);

if (low < j) {

arguments.callee(A,low,j);

}

if (i < hig) {

arguments.callee(A,i,hig);

}

}

QuickSort(A,0,n - 1);

6.二路归并

var B:Array = new Array(A.length);

for (k = 1; k < n; k *= 2) {

MergePass(k);

}

function MergePass(len) {

for (i = 0; i + 2 * len < n; i = i + 2 * len) {

MergeA(i,i + len - 1,i + 2 * len - 1);

}

if (i + len < n) {

MergeA(i,i + len - 1,n - 1);

}

}

function MergeA(low, m, hig) {

var i = low, j = m + 1, z = 0;

while (i <= m && j <= hig) {

B[z++] = (A[i] <= A[j]) ? A[i++] : A[j++];

}

while (i <= m) {

B[z++] = A[i++];

}

while (j <= hig) {

B[z++] = A[j++];

}

for (z = 0, i = low; i <= hig; z++, i++) {

A[i] = B[z];

}

一种改进的冒泡排序算法 篇9

关键词：排序,算法,算法复杂度

0▍引言

目前,最常见的排序算法有:冒泡排序法、选择排序法、快速排序法。冒泡排序法是一种简单的排序算法,由于性能很差,只有在待排数据量很小的时候才会选用它。选择排序法的性能有很大的提高,但当待排数据量很大的时候,它也不能胜任。据悉,快速排序法在所有的排序算法之中,效率最高,在对大数据量进行排序时常采用它。本文推出一种效率更高的改进的冒泡排序算法。

1▍一种改进的冒泡排序算法的思想

传统的冒泡排序算法需要元素之间一次次相互比较,这是影响排序速度的一个主要原因。随着待排元素个数的增加,比较次数几乎呈几何级数增长。而这种改进后的冒泡排序算法在大多数情况下,会减少待排数据之间的重复比较,只要增加一个标识变量,如果在某次比较过程中,标识变量未发生变化,则可证明数据已经有序,不必再进行比较,这样就大大提高了效率。下面是改进的冒泡排序的实验过程。

设待排序数组为一维数组A,其元素个数为NUM。

创建一个标识变量flag,初始化flag=0。

排序开始:①将数组A中的相邻元素进行大小比较,若顺序不对,则进行交换,并将标识变量flag置1,继续比较;②若在某次循环结束后,flag为0,则证明该数组已经排好序,不必再比较,循环结束。

2▍排序算法

排序算法如下:

3▍与传统的冒泡排序法的实验比较

设数组A有9个元素,按从小到大的顺序排序。

(1)如果待排序的数组元素原来已经排序或只有相邻的一对数未排好序(如:2,5,9,6,17,19,23,56,78),则本算法只执行8次循环即可结束,而传统的冒泡排序法需执行9*8=72次循环;

(2)又如:对于数据(12,10,23,19,46,37,76,90,92),本算法只执行30次循环即可结束,而传统的冒泡排序法需执行9 x 8=72次循环;

(3)再如:对于数据(100,93,85,80,78,74,60,59,34),本算法与传统的冒泡排序算法一样,需要执行72次循环;

(4)经过反复实验比较,本算法在最坏的情况下,即所有待排序元素顺序都不正确时,其时间复杂度与传统的冒泡排序法一样,其余情况本算法的时间复杂度均小于传统冒泡排序法的时间复杂度。而且可以看出:在数据量很大的情况下,本算法在一定情况下可大大降低时间复杂度,这是很实用的。

4▍实验结果的进一步分析

根据实验数据可以看出:

当待排序元素基本有序时,本排序算法的时间复杂度会大大降低,而传统的冒泡排序算法所需时间复杂度会随着待排序元素个数的增加而大大增加。

5▍结论

本排序算法在待排序元素大多有序的情况下,会大大节省时间,降低算法的时间复杂度,有时其时间复杂度可达0(n),具有一定的实用性。

6▍本算法的优缺点

本算法只有在待排序数据元素基本有序的情况下,不愧为一种好算法,但如果待排数据元素杂乱无章,那本算法和传统的冒泡排序法效果一样。在大多数场合下,本算法优点大于缺点,是实用的。

参考文献

[1]J．Keogh、P．Aitken、B．L．Jones著．冯博琴等译．C语言程序设计轻松入门[M]．北京：机械工业出版社，1996．

[2]谭浩强．C程序设计教程[M]．北京：清华大学出版社，2007．

[3]严蔚民．数据结构[M]．北京：清华大学出版社，2005．

[4]谭浩强．C程序设计试题汇编[M]．北京：清华大学出版社，1998．

常用排序算法的比较与分析 篇10

关键词：排序算法,时间复杂度,空间复杂度,算法实现

排序是计算机图形学、计算机辅助设计、模式识别、商业事物处理和日常生活等领域的一种重要操作,应用广泛[1],比如招生切线的分数排序、录取新生的成绩排序等,是计算机科学中的需要解决的重要问题之一。计算机程序中的排序是将一串任意序列的数据按照所要求的既定排序方式确定每个数据的具体位置的算法。在以上领域的数据处理时,程序的排序算法占了很大的比重。因此,排序算法既有广泛的应用价值,又有深刻的理论意义,曾经被列为对科学与工程计算的研究影响最大的十大问题之一[2],长期以来,人们为了各种领域的应用需要,研究、开发出了多种排序算法,这些算法有着各自的特点,实现方法不尽相同、速度也有差异,而且都在各自的应用领域扮演了重要的角色。

尽管已经开发出了各种不尽相同的排序算法,但是对排序算法的复杂度分析、算法的稳定度和数据结构的研究是解决许多实际应用的基础。该文从排序算法的基本概念、原理出发,分别从算法复杂度(时间、空间)、算法的稳定性和速度等方面进行分析比较,为具体领域应用的排序选择提供依据,使得执行效率更高。

1 排序的基本概念和算法分析的理论依据

1.1 排序的基本概念

排序:将数据表中没有规律、任意序列的数据元素按照既定的排序依据(关键码)排列成有一定规律的序列。

关键码:规定数据对象的其中一个属性域用作排序依据,从而区分对象,该属性域就是关键码。当数据表中各对象的关键码互不相同时,该关键码为主关键码;否则为次关键码;根据主关键码进行排序时,结果是唯一的,否者可能不唯一。

内部、外部排序:所谓内部排序是指排序时数据元素全部存放在j计算机的随机存储器(内存);外部排序是指排序时数据元素在内、外存之间不断移动(待排序的数据量很大,内存无法一次容纳全部数据)。

静态排序:所谓静态排序是指对数据元素经过比较和判断之后将对象移动到相应的位置。

动态排序:所谓动态排序是指给每个对象增加一个链接指针,对数据元素经过比较和判断之后不移动对象,而是修改对象的链接指针来达到元素之间顺序的改变。

1.2 算法分析的理论依据

一个问题可以采用不同算法来实现,算法的质量优劣直接影响算法的效率。算法分析的目的在于选择合适的算法和改进算法。评价一个算法的优劣主要是根据算法的复杂度(分为时间复杂度和空间复杂度),不同的排序算法,其复杂度也不一样,简单的算法程序,其执行效率也低;反之,复杂的算法程序,其执行效率相对来说也会比较高。

如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数,T(n)称为这一算法的时间复杂度。当问题规模n趋于无穷大时,如果存在某个辅助函数f(n),T(n)/f(n)的极限值为不等于零的常数,该时间复杂性的极限情形称为算法的渐近时间复杂度[3,4],记作O(f(n))。一般情况,在算法分析时对两者不予区分,经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度,f(n)是算法中频度最大的语句频度。常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),k次方阶O(nk),指数阶O(2n)。n越大,时间复杂度也越大,算法的执行效率就越低。例如:

sum=0;(1次)

for(i=1;i<=n;i++)(n次)

for(j=1;j<=n;j++)(n2次)

sum++;(n2次)

在上述交换i和j的算法中,时间复杂度为T(n)=2n2+n+1=O(n2)。

空间复杂度是指算法在执行过程中,根据n的规模大小需要临时占用的存储空间[3-4],和时间复杂度类似,也是问题规模n的函数,记作S(n)=O(f(n))。

一般情况,时间复杂度和空间复杂度是相互影响的,即:时间复杂度较好时(效率较高),空间复杂度的可能就变差(占用较多的存储空间),反之也一样。所以设计或选择一个好的算法时要考虑算法的时间复杂度和空间复杂度。

对于排序算法的稳定性,如果待排序的序列中存在两个或两个以上具有相同关键词的数据,排序后这些数据的相对次序保持不变,即它们的位置保持不变,则该算法是稳定的;如果排序后,数据的相对次序发生了变化,则该算法是不稳定的。

不仅仅是时间复杂度和空间复杂度之间相互影响,算法的所有性能之间或多或少都会相互影响。因此,当设计或选择一个算法时,尤其是大型算法,要综合考虑算法的各项性能:复杂度、稳定性、以及算法描述语言的特性,算法运行的机器系统环境等各方面因素。

2 排序算法的分析比较

2.1 插入排序

基本思想:每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数据元素依然有序;直到待排序数据元素全部插入完为止。关键在于将新的数据元素插入到已排序好的序列当中,包括找到应插入的位置、如何移动序列当中的数据元素。因此,插入排序又分为以下两种。

2.1.1 直接插入排序

基本思想:将欲插入的第i个数据元素的关键码与前面已经排序好的i-1、i-2、i-3、…数据元素的关键码进行顺序比较,通过这种线性搜索的方法找到第i个数据元素的插入位置,并且原来位置的数据元素顺序后移,直到全部排好顺序。

直接插入排序中,关键词相同的数据元素将保持原有位置不变,所以该算法是稳定的,时间复杂度的最坏值为平方阶O(n2),空间复杂度为常数阶O(1)。

该排序方法是对冒泡排序的改进,比冒泡排序大约快3倍,但是只适用于数据量较小(1000)的排序。

2.1.2 希尔排序

基本思想:根据不同步长对数据元素执行插入排序,刚开始数据非常无序时,步长最大,此时插入排序的元素个数很少,速度很快;数据基本有序时,步长很小,插入排序对于有序的序列效率很高。因此,如果元素为你的待排序序列,先取一个小于n的整数I作为步长,将所有元素分为I个子序列,在每个子序列中分别执行直接插入排序。然后缩小步长I重新划分子序列和排序,直到I=1,此时,相当于将所有元素放在一个序列当中。

刚开始,由于步长I很大,所以排序效率很高,当步长I逐渐减小时,序列也趋于有序化,所以排序效率也很高。因此,希尔排序时间复杂度会比O(n2)好一些,然而,多次插入排序中,第一次插入排序是稳定的,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,所以希尔排序是不稳定的。

相对来说,希尔排序比较简单,适用于小数据量(5000以下)的排序,比直接插入排序快2倍、比冒泡排序快5倍,因此,希尔排序适用于小数据量的、排序速度要求不高的排序。

2.2 选择排序

基本思想:每一趟扫描时,从待排序的数据元素中选出关键码最小或最大的一个元素,顺序放在已经排好顺序序列的最后,直到全部待排序的数据元素排完为止。

2.2.1 直接选择排序

基本思想:给每个位置选择关键码最小的数据元素,即:选择最小的元素与第一个位置的元素交换,然后在剩下的元素中再选择最小的与第二个位置的元素交换,直到倒数第二个元素和最后一个元素比较为止。

根据其基本思想,每当扫描一趟时,如果当前元素比一个元素小,而且这个小元素又出现在一个和当前元素相等的元素后面,则它们的位置发生了交换,所以直接选择排序时不稳定的,其时间复杂度为平方阶O(n2),空间复杂度为O(1)。

该算法和冒泡排序算法一样,适用于n值较小的场合,而且是排序算法发展的初级阶段,在实际应用中采用的几率较小。

2.2.2 堆排序

堆排序时对直接选择排序的一种有效改进,其基本思想是:将所有的数据建成一个堆,最大的数据在堆顶,然后将堆顶的数据元素和序列的最后一个元素交换;接着重建堆、交换数据,依次下去,从而实现对所有的数据元素的排序。完成堆排序需要执行两个动作:建堆和堆的调整,如此反复进行。

由基本思想可知,堆排序有可能会使得两个相同关键码的元素位置发生互换,所以是不稳定的,其平均时间复杂度为O(nlog2n),空间复杂度为O(1)。由于堆的不断建立和调整,所以堆排序不适用于数据元素较少的排序,但是对于n较大的情形,该算法能够表现出较大的优越性。因此,堆排序比较适用于数据量达到百万及其以上的排序,在这种情况下,使用递归设计的快速排序和归并排序可能会发生堆栈溢出的现象。

2.3 交换排序

基本思想:顾名思义,就是一组待排序的数据元素中,按照位置的先后顺序相互比较各自的关键码,如果是逆序,则交换这两个数据元素,直到该序列数据元素有序为止。

2.3.1 冒泡排序

基本思想:对于待排序的一组数据元素,把每个数据元素看作有重量的气泡,按照轻气泡不能在重气泡之下的原则,将未排好顺序的全部元素自上而下的对相邻两个元素依次进行比较和调整,让较重的元素往下沉,较轻的往上冒。

根据基本思想,只有在两个元素的顺序与排序要求相反时才将调换它们的位置,否则保持不变,所以冒泡排序时稳定的。时间复杂度为平方阶O(n2),空间复杂度为O(1)。

冒泡排序时最慢的排序算法,是排序算法发展的初级阶段,实际应用中采用该算法的几率比较小。

2.3.2 快速排序

快速排序是对冒泡排序本质上的改进。其基本思想为:是一个就地排序,分而治之,大规模递归的算法。即:通过一趟扫描后确保基准点的这个数据元素的左边元素都比它小、右边元素都比它大,接着又以递归方法处理左右两边的元素,直到基准点的左右只有一个元素为止。

快速排序时一个不稳定的算法,其最坏值的时间复杂度为平方阶O(n2),空间复杂度为O(log n)。

快速排序是递归的、速度最快的排序算法,但是在内存有限的情况下不是一个好的选择;而且,对于基本有序的数据序列排序,快速排序反而变得比较慢。

2.4 归并排序

归并排序的基本思想是:把数据序列递归地分成短序列,即把1分成2、2分成4、依次分解,当分解到只有1个一组的时候排序这些分组,然后依次合并回原来的序列,不断合并直到原序列全部排好顺序。

合并过程中可以确保两个相等的当前元素中,把处在前面的元素保存在结果序列的前面,因此归并排序是稳定的,其时间复杂度为O(nlog2n),空间复杂度为O(n)。

归并排序比堆排序要快,但是需要的存储空间增加一倍。

2.5 基数排序

基数排序属于分配式排序,其基本思想是:首先是低位排序,然后收集;其次是高位排序,然后再收集;依次类推,直到最高位。

基数排序基于分别排序、分别收集,是稳定的排序算法,其时间复杂度为O(nlog(r)d),r是采取的基数、d是堆数,空间复杂度为O(rd)。

基数排序适用于规模n值很大的场合,但是只适用于整数的排序,如果对浮点数进行基数排序,则必须明确浮点数的存储格式,然后通过某种方式将其映射到整数上,最后再映射回去,过程复杂。

3 排序算法的选择

经过排序算法的分析比较,各种算法有自己比较适合的应用场合,选择算法时应综合考虑稳定性、时间复杂度和空间复杂度等因素。综合前面的分析比较,各种算法的各种因素影响见表1。

4 结束语

排序算法的应用非常广泛,是计算机图形学、计算机辅助设计、模式识别、商业事物处理和日常生活等领域的一种重要的程序操作。该文从时间复杂度、空间复杂度、稳定性以及规模n值的大小等方面对常用的排序算法进行了分析比较和总结,为排序算法的选择提供了依据。规模n值较小时、且对稳定性不作要求时选用选择排序比较有利,对稳定性有要求时选用插入或冒泡排序比较有利。规模n值较大、且关键码元素随机、对稳定性没要求时选用快速排序比较有利;关键码元素有序、对稳定性有要求时,存储空间又允许的情况下选用归并排序比较有利;关键码元素有序、对稳定性没有要求时选用堆排序比较有利。总而言之,充分了解各种排序算法自身的特点及其基本思想在选择、设计高效且合理的算法具有重要意义。

参考文献

[1]Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to Algorithms[M].2nd ed.The MIT Press,2001.

[2]Dongarra J.The top 10 algorithms[J].IEEE Computing in Science&Engineering,2000,2(1):22-23.

[3]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,2007.