快捷搜索:  as  MTU2MzEzMTkxMg`

八大排序算法 (转载)

概述:排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大年夜,一次不能容纳整个的排序记录,在排序历程中必要造访外存。

我们这里说说八大年夜排序便是内部排序。

当n较大年夜,则应采纳光阴繁杂度为O(nlog2n)的排序措施:快速排序、堆排序或归并排序序。

快速排序:是今朝基于对照的内部排序中被觉得是最好的措施,当待排序的关键字是随机散播时,快速排序的匀称光阴最短;

1.插入排序—直接插入排序(Straight Insertion Sort)

基础思惟:

将一个记录插入到已排序好的有序表中,从而获得一个新,记录数增1的有序表。即:先将序列的第1个记录当作是一个有序的子序列,然后从第2个记录逐个进行插入,直至全部序列有序为止。

要点:设立哨兵,作为临时存储和判断数组界限之用。

直接插入排序示例:

假如遇见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。以是,相等元素的前后顺序没有改变,从原无序序列出去的顺序便是排好序后的顺序,以是插入排序是稳定的。

算法的实现:

[cpp]view plaincopy

print?

voidprint(inta[],intn ,inti){

cout

效率:

光阴繁杂度:O(n^2).

其他的插入排序有二分插入排序,2-路插入排序。

2. 插入排序—希尔排序(Shell`s Sort)

希尔排序是1959 年由D.L.Shell 提出来的,相对直接排序有较大年夜的改进。希尔排序又叫缩小增量排序

基础思惟:

先将全部待排序的记录序列瓜分成为多少子序列分手进行直接插入排序,待全部序列中的记录“基础有序”时,再对全体记录进行依次直接插入排序。

操作措施:

选择一个增量序列t1,t2,…,tk,此中ti>tj,tk=1;

按增量序列个数k,对序列进行k 趟排序;

每趟排序,根据对应的增量ti,将待排序列瓜分成多少长度为m 的子序列,分手对各子表进行直接插入排序。仅增量因子为1 时,全部序列作为一个表来处置惩罚,表长度即为全部序列的长度。

希尔排序的示例:

算法实现:

我们简单处置惩罚增量序列:增量序列d = {n/2 ,n/4, n/8 .....1}n为要排序数的个数

即:先将要排序的一组记录按某个增量d(n/2,n为要排序数的个数)分成多少组子序列,每组中记录的下标相差d.对每组中整个元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。继承赓续缩小增量直至为1,着末应用直接插入排序完成排序。

[cpp]view plaincopy

print?

voidprint(inta[],intn ,inti){

cout= 1  ){

ShellInsertSort(a, n, dk);

dk = dk/2;

}

}

intmain(){

inta[8] = {3,1,5,7,2,4,9,6};

//ShellInsertSort(a,8,1); //直接插入排序

shellSort(a,8);//希尔插入排序

print(a,8,8);

}

希尔排序时效阐发很难,关键码的对照次数与记录移动次数依附于增量因子序列d的拔取,特定环境下可以准确估算出关键码的对照次数和记录的移动次数。今朝还没有人给出拔取最好的增量因子序列的措施。增量因子序列可以有各类取法,有取奇数的,也有取质数的,但必要留意:增量因子中除1 外没有公因子,且着末一个增量因子必须为1。希尔排序措施是一个不稳定的排序措施。

3. 选择排序—简单选择排序(Simple Selection Sort)

基础思惟:

在要排序的一组数中,选出最小(或者最大年夜)的一个数与第1个位置的数互换;然后在剩下的数傍边再找最小(或者最大年夜)的与第2个位置的数互换,依次类推,直到第n-1个元素(倒数第二个数)和第n个元素(着末一个数)对照为止。

简单选择排序的示例:

操作措施:

第一趟,从n 个记录中找出关键码最小的记录与第一个记录互换;

第二趟,从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录互换;

以此类推.....

第i 趟,则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录互换,

直到全部序列按关键码有序。

算法实现:

[cpp]view plaincopy

print?

voidprint(inta[],intn ,inti){

cout a[j]) k = j;

}

returnk;

}

/**

* 选择排序

*

*/

voidselectSort(inta[],intn){

intkey, tmp;

for(inti = 0; i[cpp]view plaincopy

print?

voidSelectSort(intr[],intn) {

inti ,j , min ,max, tmp;

for(i=1 ;i  r[max]) {

max = j ;continue;

}

if(r[j]基础思惟:

堆的定义如下:具有n个元素的序列(k1,k2,...,kn),当且仅当满意

时称之为堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)。

若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点的值均不大年夜于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大年夜)的。如:

(a)大年夜顶堆序列:(96, 83,27,38,11,09)

(b)  小顶堆序列:(12,36,24,85,47,30,53,91)

初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树(一维数组存储二叉树),调剂它们的存储序,使之成为一个堆,将堆顶元素输出,获得n 个元素中最小(或最大年夜)的元素,这时堆的根节点的数最小(或者最大年夜)。然后对前面(n-1)个元素从新调剂使之成为堆,输出堆顶元素,获得n 个元素中次小(或次大年夜)的元素。依此类推,直到只有两个节点的堆,并对它们作互换,着末获得有n个节点的有序序列。称这个历程为堆排序。

是以,实现堆排序需办理两个问题:

1. 若何将n 个待排序的数建成堆;

2. 输出堆顶元素后,如何调剂残剩n-1 个元素,使其成为一个新堆。

首先评论争论第二个问题:输出堆顶元素后,对残剩n-1元素从新建成堆的调剂历程。

调剂小顶堆的措施:

1)设有m 个元素的堆,输出堆顶元素后,剩下m-1 个元素。将堆底元素送入堆顶((着末一个元素与堆顶进行互换),堆被破坏,其缘故原由仅是根结点不满意堆的性子。

2)将根结点与左、右子树中较小元素的进行互换。

3)若与左子树互换:假如左子树堆被破坏,即左子树的根结点不满意堆的性子,则重复措施 (2).

4)若与右子树互换,假如右子树堆被破坏,即右子树的根结点不满意堆的性子。则重复措施 (2).

5)继承对不满意堆性子的子树进行上述互换操作,直到叶子结点,堆被建成。

称这个自根结点到叶子结点的调剂历程为筛选。如图:

再评论争论对n 个元素初始建堆的历程。

建堆措施:对初始序列建堆的历程,便是一个反复进行筛选的历程。

1)n 个结点的完全二叉树,则着末一个结点是第

个结点的子树。

2)筛选从第

个结点为根的子树开始,该子树成为堆。

3)之后向前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点。

如图建堆初始历程:无序序列:(49,38,65,97,76,13,27,49)

算法的实现:

从算法描述来看,堆排序必要两个历程,一是建立堆,二是堆顶与堆的着末一个元素交换位置。以是堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。

[cpp]view plaincopy

print?

voidprint(inta[],intn){

for(intj= 0; j

cout= 0; --i)

HeapAdjust(H,i,length);

}

/**

* 堆排序算法

*/

voidHeapSort(intH[],intlength)

{

//初始堆

BuildingHeap(H, length);

//从着末一个元素开始对序列进行调剂

for(inti = length - 1; i > 0; --i)

{

//互换堆顶元素H[0]和堆中着末一个元素

inttemp = H[i]; H[i] = H[0]; H[0] = temp;

//每次互换堆顶元素和堆中着末一个元素之后,都要对堆进行调剂

HeapAdjust(H,0,i);

}

}

intmain(){

intH[10] = {3,1,5,7,2,4,9,6,10,8};

cout阐发:

设树深度为k,

。从根到叶的筛选,元素对照次数至多2(k-1)次,互换记录至多k 次。以是,在建好堆后,排序历程中的筛选次数不跨越下式:

而建堆时的对照次数不跨越4n 次,是以堆排序最坏环境下,光阴繁杂度也为:O(nlogn )。

5. 互换排序—冒泡排序(Bubble Sort)

基础思惟:

在要排序的一组数中,对当前还未排好序的范围内的整个数,自上而下对相邻的两个数依次进行对照和调剂,让较大年夜的数往下沉,较小的往上冒。即:每当两相邻的数对照后发明它们的排序与排序要求相反时,就将它们交换。

冒泡排序的示例:

算法的实现:

[cpp]view plaincopy

print?

voidbubbleSort(inta[],intn){

for(inti =0 ; i a[j+1])

{

inttmp = a[j] ; a[j] = a[j+1] ;  a[j+1] = tmp;

}

}

}

}

冒泡排序算法的改进

对冒泡排序常见的改进措施是加入一标志性变量exchange,用于标志某一趟排序历程中是否稀有据互换,假如进行某一趟排序时并没有进行数据互换,则阐明数据已经按要求排列好,可急速停止排序,避免不需要的对照历程。本文再供给以下两种改进算法:

1.设置一标志性变量pos,用于记录每趟排序中着末一次进行互换的位置。因为pos位置之后的记录均已互换到位,故在进行下一趟排序时只要扫描到pos位置即可。

改进后算法如下:

[cpp]view plaincopy

print?

voidBubble_1 (intr[],intn) {

inti= n -1;//初始时,着末位置维持不变

while( i> 0) {

intpos= 0;//每趟开始时,无记录互换

for(intj= 0; j r[j+1]) {

pos= j;//记录互换的位置

inttmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;

}

i= pos;//为下一趟排序作筹备

}

}

2.传统冒泡排序中每一趟排序操作只能找到一个最大年夜值或最小值,我们斟酌使用在每趟排序中进行正向和反向两遍冒泡的措施一次可以获得两个终极值(最大年夜者和最小者)

,从而使排序趟数险些削减了一半。

改进后的算法实现为:

[cpp]view plaincopy

print?

voidBubble_2 (intr[],intn){

intlow = 0;

inthigh= n -1;//设置变量的初始值

inttmp,j;

while(low  r[j+1]) {

tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;

}

--high;//改动high值, 前移一位

for( j=high; j>low; --j)//反向冒泡,找到最小者

if(r[j]

tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp;

}

++low;//改动low值,后移一位

}

}

6. 互换排序—快速排序(Quick Sort)

基础思惟:

1)选择一个基准元素,平日选择第一个元素或者着末一个元素,

2)经由过程一趟排序讲待排序的记录瓜分成自力的两部分,此中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大年夜。

3)此时基准元素在其排好序后的精确位置

4)然后分手对这两部分记任命同样的措施继承进行排序,直到全部序列有序。

快速排序的示例:

(a)一趟排序的历程:

(b)排序的全历程

算法的实现:

递归实现:

[cpp]view plaincopy

print?

voidprint(inta[],intn){

for(intj= 0; j

cout= privotKey) --high;//从high 所指位置向前搜索,至多到low+1 位置。将比基准元素小的互换到低端

swap(&a[low], &a[high]);

while(low 阐发:

快速排序是平日被觉得在同数量级(O(nlog2n))的排序措施中匀称机能最好的。但若初始序列按关键码有序或基础有序时,快排序反而堕落为冒泡排序。为改进之,平日以“三者取中法”来拔取基准记录,即将排序区间的两个端点与中点三个记录关键码居中的调剂为支点记录。快速排序是一个不稳定的排序措施。

快速排序的改进

在本改进算法中,只对长度大年夜于k的子序列递归调用快速排序,让原序列基础有序,然后再对全部基础有序序列用插入排序算法排序。实践证实,改进后的算法光阴繁杂度有所低落,且当k取值为8阁下时,改进算法的机能最佳。算法思惟如下:

[cpp]view plaincopy

print?

voidprint(inta[],intn){

for(intj= 0; j

cout= privotKey) --high;//从high 所指位置向前搜索,至多到low+1 位置。将比基准元素小的互换到低端

swap(&a[low], &a[high]);

while(low  k ) {//长度大年夜于k时递归, k为指定的数

intpivot = partition(r, low, high);// 调用的Partition算法维持不变

qsort_improve(r, low, pivot - 1,k);

qsort_improve(r, pivot + 1, high,k);

}

}

voidquickSort(intr[],intn,intk){

qsort_improve(r,0,n,k);//先调用改进算法Qsort使之基础有序

//再用插入排序对基础有序序列排序

for(inti=1; i基础思惟:

归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为多少个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序示例:

合并措施:

设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成,两个子表长度分手为n-i +1、n-m。

j=m+1;k=i;i=i; //置两个子表的肇端下标及帮助数组的肇端下标

若i>m 或j>n,转⑷ //此中一个子表已合并完,对照拔取停止

//拔取r[i]和r[j]较小的存入帮助数组rf

假如r[i]

否则,rf[k]=r[j]; j++; k++; 转⑵

//将尚未处置惩罚完的子表中元素存入rf

假如i[cpp]view plaincopy

print?

//将r[i…m]和r[m +1 …n]归并到帮助数组rf[i…n]

voidMerge(ElemType *r,ElemType *rf,inti,intm,intn)

{

intj,k;

for(j=m+1,k=i; i归并的迭代算法

1 个元素的表老是有序的。以是对n 个元素的待排序列,每个元素可当作1 个有序子表。对子表两两合并天生n/2个子表,所得子表除着末一个子表长度可能为1 外,另外子表长度均为2。再进行两两合并,直到天生n 个元素按关键码有序的表。

[cpp]view plaincopy

print?

voidprint(inta[],intn){

for(intj= 0; j

cout两路归并的递归算法

[cpp]view plaincopy

print?

voidMSort(ElemType *r, ElemType *rf,ints,intt)

{

ElemType *rf2;

if(s==t) r[s] = rf[s];

else

{

intm=(s+t)/2;/*等分*p 表*/

MSort(r, rf2, s, m);/*递归地将p[s…m]归并为有序的p2[s…m]*/

MSort(r, rf2, m+1, t);/*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/

Merge(rf2, rf, s, m+1,t);/*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/

}

}

voidMergeSort_recursive(ElemType *r, ElemType *rf,intn)

{/*对顺序表*p 作归并排序*/

MSort(r, rf,0, n-1);

}

8. 桶排序/基数排序(Radix Sort)

说基数排序之前,我们先说桶排序:

基础思惟:是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再应用其余排序算法或因此递回要领继承应用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是平均分配的时刻,桶排序应用线性光阴(Θ(n))。但桶排序并不是 对照排序,他不受到 O(n log n) 下限的影响。

简单来说,便是把数据分组,放在一个个的桶中,然后对每个桶里面的在进行排序。

例如要对大年夜小为[1..1000]范围内的n个整数A[1..n]排序

首先,可以把桶设为大年夜小为10的范围,详细而言,设聚拢B[1]存储[1..10]的整数,聚拢B[2]存储

(10..20]的整数,……聚拢B[i]存储(   (i-1)*10,   i*10]的整数,i   =   1,2,..100。统共有

100个桶。

然后,对A[1..n]从头到尾扫描一遍,把每个A[i]放入对应的桶B[j]中。  再对这100个桶中每个桶里的数字排序,这时可用冒泡,选择,甚至快排,一样平常来说任  何排序法都可以。

着末,依次输出每个桶里面的数字,且每个桶中的数字从小到大年夜输出,这  样就获得所稀有字排好序的一个序列了。

假设有n个数字,有m个桶,假如数字是匀称散播的,则每个桶里面匀称有n/m个数字。假如

对每个桶中的数字采纳快速排序,那么全部算法的繁杂度是

O(n   +   m   *   n/m*log(n/m))   =   O(n   +   nlogn   -   nlogm)

从上式看出,当m靠近n的时刻,桶排序繁杂度靠近O(n)

当然,以上繁杂度的谋略是基于输入的n个数字是匀称散播这个假设的。这个假设是很强的  ,实际利用中效果并没有这么好。假如所有的数字都落在同一个桶中,那就退化成一样平常的排序了。

前面说的几大年夜排序算法 ,大年夜部分光阴繁杂度都是O(n2),也有部分排序算法光阴繁杂度是O(nlogn)。而桶式排序却能实现O(n)的光阴繁杂度。但桶排序的毛病是:

1)首先是空间繁杂度对照高,必要的额外开销大年夜。排序有两个数组的空间开销,一个寄放待排序数组,一个便是所谓的桶,比如待排序值是从0到m-1,那就必要m个桶,这个桶数组就要至少m个空间。

2)其次待排序的元素都要在必然的范围内等等。

桶式排序是一种分配排序。分配排序的特定是不必要进行关键码的对照,但条件是要知道待排序列的一些详细环境。

分配排序的基础思惟:说白了便是进行多次的桶式排序。

基数排序历程无须对照关键字,而是经由过程“分配”和“网络”历程来实现排序。它们的光阴繁杂度可达到线性阶:O(n)。

实例:

扑克牌中52 张牌,可按花色和面值分成两个字段,其大年夜小关系为:

花色:梅花

面值:2

若对扑克牌按花色、面值进行升序排序,获得如下序列:

即两张牌,若花色不合,不论面值如何,花色低的那张牌小于花色高的,只有在同花色环境下,大年夜小关系才由面值的大年夜小确定。这便是多关键码排序。

为获得排序结果,我们评论争论两种排序措施。

措施1:先对花色排序,将其分为4 个组,即梅花组、方块组、红心组、黑心组。再对每个组分手按面值进行排序,着末,将4 个组连接起来即可。

措施2:先按13 个面值给出13 个编号组(2 号,3 号,...,A 号),将牌按面值依次放入对应的编号组,分成13 堆。再按花色给出4 个编号组(梅花、方块、红心、黑心),将2号组中牌掏出分手放入对应花色组,再将3 号组中牌掏出分手放入对应花色组,……,这样,4 个花色组中均按面值有序,然后,将4 个花色组依次连接起来即可。

设n 个元素的待排序列包孕d 个关键码{k1,k2,…,kd},则称序列对关键码{k1,k2,…,kd}有序是指:对付序列中任两个记录r[i]和r[j](1≤i≤j≤n)都满意下列有序关系:

此中k1 称为最主位关键码,kd 称为最次位关键码     。

两种多关键码排序措施:

多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序,分两种措施:

最高位优先(Most Significant Digit first)法,简称MSD 法:

1)先按k1 排序分组,将序列分成多少子序列,同一组序列的记录中,关键码k1 相等。

2)再对各组按k2 排序分成子组,之后,对后面的关键码继承这样的排序分组,直到按最次位关键码kd 对各子组排序后。

3)再将各组连接起来,便获得一个有序序列。扑克牌按花色、面值排序中先容的措施一等于MSD 法。

最低位优先(Least Significant Digit first)法,简称LSD 法:

1) 先从kd 开始排序,再对kd-1进行排序,依次重复,直到按k1排序分组分成最小的子序列后。

2) 着末将各个子序列连接起来,便可获得一个有序的序列, 扑克牌按花色、面值排序中先容的措施二等于LSD 法。

基于LSD措施的链式基数排序的基础思惟

“多关键字排序”的思惟实现“单关键字排序”。对数字型或字符型的单关键字,可以看作由多个数位或多个字符构成的多关键字,此时可以采纳“分配-网络”的措施进行排序,这一历程称作基数排序法,此中每个数字或字符可能的取值个数称为基数。比如,扑克牌的花色基数为4,面值基数为13。在收拾扑克牌时,既可以先按花色收拾,也可以先按面值收拾。按花色收拾时,先按红、黑、方、花的顺序分成4摞(分配),再按此顺序再叠放在一路(网络),然后按面值的顺序分成13摞(分配),再按此顺序叠放在一路(网络),如斯进行二次分配和网络即可将扑克牌排列有序。

基数排序:

是按照低位先排序,然后网络;再按照高位排序,然后再网络;依次类推,直到最高位。无意偶尔候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。着末的序次便是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分手排序,分手网络,所所以稳定的。

算法实现:

[cpp]view plaincopy

print?

Void RadixSort(Node L[],length,maxradix)

{

intm,n,k,lsp;

k=1;m=1;

inttemp[10][length-1];

Empty(temp);//清空临时空间

while(k

{

for(inti=0;i

{

if(L[i]

Temp[0][n]=L[i];

else

Lsp=(L[i]/m)%10;//确定关键字

Temp[lsp][n]=L[i];

n++;

}

CollectElement(L,Temp);//网络

n=0;

m=m*10;

k++;

}

}

总结

各类排序的稳定性,光阴繁杂度和空间繁杂度总结:

我们对照光阴繁杂度函数的环境:

光阴繁杂度函数O(n)的增长环境

以是对n较大年夜的排序记录。一样平常的选择都是光阴繁杂度为O(nlog2n)的排序措施。

光阴繁杂度来说:

(1)平方阶(O(n2))排序

种种简单排序:直接插入、直接选择和冒泡排序;(2)线性对数阶(O(nlog2n))排序快速排序、堆排序和归并排序;(3)O(n1+§))排序,§是介于0和1之间的常数。

希尔排序(4)线性阶(O(n))排序

基数排序,此外还有桶、箱排序。

阐明:

当原表有序或基础有序时,直接插入排序和冒泡排序将大年夜大年夜削减对照次数和移动记录的次数,光阴繁杂度可降至O(n);

而快速排序则相反,当原表基础有序时,将堕落为冒泡排序,光阴繁杂度前进为O(n2);

原表是否有序,对简单选择排序、堆排序、归并排序和基数排序的光阴繁杂度影响不大年夜。

稳定性:

排序算法的稳定性:若待排序的序列中,存在多个具有相同关键字的记录,颠末排序, 这些记录的相对序次维持不变,则称该算法是稳定的;若经排序后,记录的相对 序次发生了改变,则称该算法是不稳定的。

稳定性的好处:排序算法假如是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序便是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。别的,假如排序算法稳定,可以避免多余的对照;

稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序

不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序

选择排序算法准则:

每种排序算法都各有优毛病。是以,在实用时需根据不合环境适被选用,以致可以将多种措施结合起来应用。

选择排序算法的依据

影响排序的身分有很多,匀称光阴繁杂度低的算法并不必然便是最优的。相反,无意偶尔匀称光阴繁杂度高的算法可能更得当某些特殊环境。同时,选择算法时还得斟酌它的可读性,以利于软件的掩护。一样平常而言,必要斟酌的身分有以下四点:

1.待排序的记录数目n的大年夜小;

2.记录本身数据量的大年夜小,也便是记录中除关键字外的其他信息量的大年夜小;

3.关键字的布局及其散播环境;

4.对排序稳定性的要求。

设待排序元素的个数为n.

1)当n较大年夜,则应采纳光阴繁杂度为O(nlog2n)的排序措施:快速排序、堆排序或归并排序序。

快速排序:是今朝基于对照的内部排序中被觉得是最好的措施,当待排序的关键字是随机散播时,快速排序的匀称光阴最短;

堆排序:  假如内存空间容许且要求稳定性的,

归并排序:它有必然数量的数据移动,以是我们可能过与插入排序组合,先得到必然长度的序列,然后再合并,在效率上将有所前进。

2)当n较大年夜,内存空间容许,且要求稳定性 =》归并排序

3)当n较小,可采纳直接插入或直接选择排序。

直接插入排序:当元素散播有序,直接插入排序将大年夜大年夜削减对照次数和移动记录的次数。

直接选择排序 :元素散播有序,假如不要求稳定性,选择直接选择排序

5)一样平常不应用或不直接应用传统的冒泡排序。

6)基数排序

它是一种稳定的排序算法,但有必然的局限性:

1、关键字可分化。

2、记录的关键字位数较少,假如密集更好

3、假如是数字时,最好是无符号的,否则将增添响应的映射繁杂度,可先将其正负分开排序。

注明:转载请提示出处:http://blog.csdn.net/hguisu/article/details/7776068

您可能还会对下面的文章感兴趣: