排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

概述

排序分类

冒泡排序

选择排序(原理 优劣)

插入排序(原理 优劣)

shell排序(原理 Pascal程序 C程序 优劣)

快速排序(原理 优劣 Pascal程序)

箱排序

归并排序

树型排序

有关排序的面试题

稳定性(概念 常见排序算法)

概述

内排序的方法有许多种，按所用策略不同，可归纳为五类：插入排序、选择

排序、交换排序、归并排序和分配排序。

其中，插入排序主要包括直接插入排序和希尔排序两种；选择排序主要包括直接选择排序和堆排序；交换排序主要包括气（冒）泡排序和快速排序。

排序分类

稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在

用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法

是稳定的。其中冒泡，插入，基数，归并属于稳定排序，选择，快速，希尔，堆属于不稳定排序。

就地排序：若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间为O（1）,

则称为就地排序。

冒泡排序

已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[2]与a[3]的值，若a[2]大于a[3]则交换两者的值，否则不变。再比较a[3]与a[4]，以此类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处理一轮，则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮，以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。降序排列与升序排列相类似，若a[1]小于a[2]则交换两者的值，否则不变，后面以此类推。 总的来讲，每一轮排序后最大（或最小）的数将移动到数据序列的最后，理论上总共要进行n(n-1）/2次交换。

优点：稳定；

缺点：慢，每次只能移动相邻两个数据。

附Pascal程序：

program name;

var

a:array[1..N] of 1..MAX;

temp,i,j:integer;

begin

randomize;

for i:=1 to N do a:=1+random(MAX);

writeln('Array before sorted:');

for i:=1 to N do write(a,' ');

writeln;

for i:=N-1 downto 1 do

for j:=1 to i do

if a[j]<a[j+1] then

begin

temp:=a[j];

a[j]:=a[j+1];

a[j+1]:=temp

end;

writeln('Array sorted:');

for i:=1 to N do write(a,' ');

writeln;

writeln('End sorted.');

readln;

end.

附c/c++ma程序(共有N个数)

for(i=0;i<N-1;i++)

{

for(j=0;j<N-i-1;j++)

if(a[j]>a[j+1])

{temp=a[j];a[j]=a[j+1];a[j+1]=temp}

}

附 c# 程序(指定个数)

static void Main(string[] args)

{

int[] arr = { 4, 2, 5, 7, 4, 9, 6, 21 };

for (int i = 0; i < arr.Length; i++)

{

for (int j = i + 1; j < arr.Length; j++)

{

int temp = 0;

if (arr[i] > arr[j])

{

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

}

}

foreach (int num in arr)

{

Console.Write(" {0}", num);

}

Console.ReadKey();

}

选择排序

原理

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

选择排序是不稳定的排序方法(很多教科书都说选择排序是不稳定的，但是，完全可以将其实现成稳定的排序方法)。

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：

①初始状态：无序区为R[1..n]，有序区为空。

②第1趟排序

在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

……

③第i趟排序

第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

优劣

优点：移动数据的次数已知（n-1次）；

缺点：比较次数多，不稳定。

插入排序

原理

插入排序：已知一组升序排列数据a[1]、a[2]、……a[n]，一组无序数据b[1]、b[2]、……b[m]，需将二者合并成一个升序数列。首先比较b[1]与a[1]的值，若b[1]大于a[1]，则跳过，比较b[1]与a[2]的值，若b[1]仍然大于a[2]，则继续跳过，直到b[1]小于a数组中某一数据a[x]，则将a[x]~a[n]分别向后移动一位，将b[1]插入到原来a[x]的位置这就完成了b[1]的插入。b[2]~b[m]用相同方法插入。（若无数组a，可将b[1]当作n=1的数组a）

优劣

优点：稳定，快；

缺点：比较次数不一定，比较次数越多，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。

shell排序

由希尔在1959年提出，又称希尔排序(shell排序)。

原理

已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。发现当n不大时，插入排序的效果很好。首先取一增量d(d<n)，将a[1]、a[1+d]、a[1+2d]……列为第一组，a[2]、a[2+d]、a[2+2d]……列为第二组……，a[d]、a[2d]、a[3d]……列为最后一组以次类推，在各组内用插入排序，然后取d'<d，重复上述操作，直到d=1。

Pascal程序

program Shell;

type

arr=array[1..100] of integer;

var

a:arr;

i,j,t,d,n:integer;

bool:boolean;

begin

readln(n);

for i:=1 to n do

read(a[i]);

d:=n;

while d>1 do

begin

d:=d div 2;

for j:=d+1 to n do

begin

t:=a[j];

i:=j-d;

while (i>0) and (a[i]>t) do

begin

a[i+d]:=a[i];

i:=i-d;

end;

a[i+d]:=t;

end;

end;

for i:=1 to n do write(a[i],' ');

end.

C程序

k=n/2;

while(k>0)

{

for(i=k;i<=n;i++)

{

t=a[i];

j=i-k;

while(j>=1 && t<a[j])

{

a[j+k]=a[j];

j=j-k;

}

a[j+k]=t;

}

k/=2;

}

优劣

优点：快，数据移动少；

缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。

不需要大量的辅助空间，和归并排序一样容易实现。希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间复杂度为 O(N*(logN)2)， 没有快速排序算法快 O(N*(logN))，因此中等大小规模表现良好，对规模非常大的数据排序不是 最优选择。但是比O(N2）复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。 此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏 的情况下执行的效率会非常差。 专家门提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快， 再改成快速排序这样更高级的排序算法. 本质上讲，希尔排序算法的一种改进，减少了其复制的次数，速度要快很多。 原因是，当N值很大时数据项每一趟排序需要的个数很少，但数据项的距离很长。 当N值减小时每一趟需要和动的数据增多，此时已经接近于它们排序后的最终位置。 正是这两种情况的结合才使希尔排序效率比插入排序高很多。

快速排序

快速排序是目前已知的最快的排序方法。

原理

已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先任取数据a[x]作为基准。比较a[x]与其它数据并排序，使a[x]排在数据的第k位，并且使a[1]~a[k-1]中的每一个数据<a[x]，a[k+1]~a[n]中的每一个数据>a[x]，然后采用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n]两组数据进行快速排序。

优劣

优点：极快，数据移动少；

缺点：不稳定。

Pascal程序

program kuaipai;

var

a:array[1..100]of integer;

k,l,n,i:integer;

procedure kp(z,y:integer);

var

i,j,t:integer;

begin

i:=z;

j:=y;

t:=a[i];

repeat

while (a[j]>t)and(j>i) do

begin

inc(k);

dec(j);

end;

if i<j then

begin

a[i]:=a[j];

inc(i);

inc(l);

while (a[i]<t)and(i<j) do

begin

inc(k);

inc(i);

end;

if i<j then begin

a[j]:=a[i];

dec(j);

inc(l);

end;

end;

until i=j;

a[i]:=t;

inc(i);

dec(j);

inc(l);

if z<j then kp(z,j);

if i<y then kp(i,y);

end;

begin

readln(n);

for i:=1 to n do

read(a[i]);

k:=0;

l:=0;

kp(1,n);

for i:=1 to n do

write(a[i],' ');

end.

箱排序

已知一组无序正整数数据a[1]、a[2]、……a[n]，需将其按升序排列。首先定义一个数组x[m],且m>=a[1]、a[2]、……a[n]，接着循环n次，每次x[a]++.

优点：快，效率达到O(1)

缺点：数据范围必须为正整数并且比较小

箱排序(Bin Sort)

1、箱排序的基本思想

箱排序也称桶排序(Bucket Sort)，其基本思想是：设置若干个箱子，依次扫描待排序的记录R[0]，R[1]，…，R[n-1]，把关键字等于k的记录全都装入到第k个箱子里(分配)，然后按序号依次将各非空的箱子首尾连接起来(收集)。

【例】要将一副混洗的52张扑克牌按点数A<2<…<J<Q<K排序，需设置13个"箱子"，排序时依次将每张牌按点数放入相应的箱子里，然后依次将这些箱子首尾相接，就得到了按点数递增序排列的一副牌。

2、箱排序中，箱子的个数取决于关键字的取值范围。

若R[0..n-1]中关键字的取值范围是0到m-1的整数，则必须设置m个箱子。因此箱排序要求关键字的类型是有限类型，否则可能要无限个箱子。

3、箱子的类型应设计成链表为宜

一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的，故箱子的类型应设计成链表为宜。

4、为保证排序是稳定的，分配过程中装箱及收集过程中的连接必须按先进先出原则进行。

（1） 实现方法一

每个箱子设为一个链队列。当一记录装入某箱子时，应做人队操作将其插入该箱子尾部；而收集过程则是对箱子做出队操作，依次将出队的记录放到输出序列中。

（2） 实现方法二

若输入的待排序记录是以链表形式给出时，出队操作可简化为是将整个箱子链表链接到输出链表的尾部。这只需要修改输出链表的尾结点中的指针域，令其指向箱子链表的头，然后修改输出链表的尾指针，令其指向箱子链表的尾即可。

5、算法简析

分配过程的时间是O(n)；收集过程的时间为O(m) （采用链表来存储输入的待排序记录）或O(m+n)。因此，箱排序的时间为O(m+n)。若箱子个数m的数量级为O(n)，则箱排序的时间是线性的，即O(n)。

注意：

箱排序实用价值不大，仅适用于作为基数排序的一个中间步骤。

归并排序

归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。

归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方.

附Pascal程序：

program guibing;

type

arr=array[1..100] of integer;

var

a,b,c:arr;

i:integer;

procedure gb(r:arr;l,m,n:integer;var r2:arr);

var

i,j,k,p:integer;

begin

i:=l;

j:=m+1;

k:=l-1;

while (i<=m)and (j<=n) do

begin

k:=k+1;

if r[i]<=r[j] then

begin

r2[k]:=r[i];

i:=i+1

end

else

begin

r2[k]:=r[j];

j:=j+1

end

end;

if i<=m then

for p:=i to m do

begin

k:=k+1;

r2[k]:=r[p]

end;

if j<=n then

for p:=j to n do

begin

k:=k+1;

r2[k]:=r[p]

end;

end;

procedure gp( var r,r1:arr;s,t:integer);

var

k:integer;

c:arr;

begin

if s=t then r1[s]:=r[s]

else

begin

k:=(s+t) div 2;

gp(r,c,s,k);

gp(r,c,k+1,t);

gb(c,s,k,t,r1)

end;

end;

begin

readln(n);

for i:= 1 to n do

read(a[i]);

gp(a,b,1,n);

for i:=1 to n do

write(b[i],' ');

writeln;

end.

树型排序

树形排序的要素就是让所有的左子树都比根及右子树大，但不太稳定。

优点:效率高

缺点：不稳定

附Pascal程序：

program shupai;

type

point=^nod;

nod=record

w:integer;

right,left:point ;

end;

var

a:array[1..100]of integer;

root,first:point;

k:boolean;

i:integer;

procedure hyt(d:integer;var p:point);

begin

if p=nil then

begin

new(p);

with p^ do begin

w:=d;

right:=nil;

left:=nil

end;

if k then

begin

root:=p;

k:=false

end;

end

else

with p^ do

if d>=w then

hyt(d,right)

else

hyt(d,left);

end;

procedure hyt1(p:point);

begin

with p^ do

begin

if left<>nil then

hyt1(left);

write(w,' ');

if right<>nil then hyt1(right);

end;

end;

begin

first:=nil;

k:=true;

readln(n);

for i:=1 to n do

read(a[i]);

for i:=1 to n do

hyt(a[i],first);

hyt1(root);

end.

有关排序的面试题

1.对无序数组进行二分查找

2.对单链表进行排序

3.对40亿个8位正整数进行排序

稳定性

概念

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

常见排序算法

快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法