浅谈几种排序算法
发表时间：2010-04-23 15:28:31 浏览(8897) 评论(7)
作为一个信息学竞赛选手,排序算法可谓是入门必备的知识。本文将介绍几种常见的排序算法，并对其进行简单的比较分析。
【什么是排序算法】
在实际信息处理过程中，我们时常需要将数据按一定顺序排序以增强数据的可用性。因此，好的排序算法是十分重要的。下面将简单介绍几种排序算法，他们各自都有一些优势。
【冒泡排序】
这种算法十分简单易懂。它之所以被叫做冒泡排序，是因为它的思想是每次将剩余未排序数据中最小（大）的数据通过交换浮动到剩余序列的开头，类似于烧开水轻的气泡往上冒的过程。
具体过程：每次从后往前扫描未排序的序列，依次比较相邻的元素。如果后一个元素小于前一个元素则交换。这样最终剩余序列中的最小的元素就到了序列的开头。这样做序列元素个数次，就得到了一个升序的序列。
Pascal代码：
var i,j,k,n:longint;
a:array[0..1000] of longint;
begin
read(n);
for i:=1 to n do read(a[i]);
for i:=1 to n-1 do
for j:=n-1 downto i do
if (a[j]>a[j+1]) then
begin
k:=a[j];a[j]:=a[j+1];a[j+1];=k;
end;
for i:=1 to n do writeln(a[i]);
end.
时间复杂度：O(N^2)
【选择排序】
这种算法和冒泡排序的代码十分相似，核心思想是按照一定的顺序比较任意一对元素，如果位置靠前的元素大于位置靠后的元素则交换两个元素。最终将得到一个升序的序列。
Pascal代码：
var i,j,k,n:longint;
a:array[0..1000] of longint;
begin
read(n);
for i:=1 to n do read(a[i]);
for i:=1 to n-1 do
for j:=i+1 to n do
if (a[i]>a[j]) then
begin
k:=a[i];a[i]:=a[j];a[j];=k;
end;
for i:=1 to n do writeln(a[i]);
end.
时间复杂度：O(N^2)
【归并排序】
一种典型的分治排序算法。
所谓分治算法，就是一个问题可以划分为几个性质相同但规模较小的子问题，且解决子问题之后可以很容易解决原问题。我们递归这种划分问题缩小规模的做法，直到问题规模小到可以直接出解，再回溯解决其父问题。直至最终得到原问题的解。
归并排序的流程如下：
如果要排序的序列长度为1，无需再进行其他操作，直接回溯。
否则将该序列从中间劈开化为前后两段长度相同或差1的子序列。递归排序两子序列。
设置两个标记，分别指向两个子序列的开头。循环序列长度次以下操作：
找到两标记处较小的元素，加入新队列的队尾，后移那个标记。
这样，我们将该序列排好了。如果这就是原序列，直接输出。否则回溯到其父问题。
Pascal代码：
var i,j,k,l,m,n,p,q:longint;
a,tmp:array[0..100000] of longint;
procedure Gbsort(x,y:longint);
var t:longint;
begin
if (x=y) then exit;
t:=(x+y) div 2;
Gbsort(x,t);
Gbsort(t+1,y);
p:=x;q:=t+1;
for k:=x to y do
begin
if (p>t) then
begin
tmp[k]:=a[q];
inc(q);
end else
if (q>y) then
begin
tmp[k]:=a[p];
inc(p);
end else
begin
if (a[p]<a[q]) then
begin
tmp[k]:=a[p];inc(p);
end else
begin
tmp[k]:=a[q];inc(q);
end;
end;
end;
for k:=x to y do a[k]:=tmp[k];
end;
begin
read(n);
for i:=1 to n do read(a[i]);
Gbsort(1,n);
for i:=1 to n do writeln(a[i]);
end.
时间复杂度：由于我们递归LogN（在OI中表示以2为底N的对数）层，每层中实际上做了N这个数量级的操作。因此归并排序时间复杂度为O(NLogN)
【快速排序】
在实践中最快的排序方法。用到了分治的思想。
每次在当前序列中找一个数，通过序列长度次操作将序列分成两段，一段中所有元素比选择的元素不大，另一段中所有元素比选择的元素不小，且第一段在前，第二段在后。递归排序两段，这样最终得到原问题的解。
Pascal代码：
var i,j,k,l,n:longint;
a:array[0..100000] of longint;
procedure qsort(x,y:longint);
var g,t,l,r:longint;
begin
l:=x;r:=y;
t:=a[(x+y) div 2];
repeat
while (a[l]<t) do inc(l);
while (a[r]>t) do dec(r);
if (l<=r) then
begin
g:=a[l];a[l]:=a[r];a[r]:=g;
inc(l);dec(r);
end;
until l>r;
if (x<r) then qsort(x,r);
if (l<y) then qsort(l,y);
end;
begin
read(n);
for i:=1 to n do read(a[i]);
qsort(1,n);
for i:=1 to n do writeln(a[i]);
end.
时间复杂度：期望上来说为O(NLogN)
但是，快排可能退化。极端情况，如果每次划分都使得一段长度为1，另一段长度为原序列长度-1。快排的复杂度将退化成O(N^2)。这主要取决于选择中间元素的方法和数据的构造。所以，随机选择中间元素t不失为一个好的选择。另外，当序列长度已经很小时，如果依然递归快排，系统由于开堆栈而耗费的时间将抵消LogN少于N的时间。反而是选择排序更快。所以，一个优化是当该问题所排序列长度<20左右时直接选择排序后回溯，否则再执行递归的快排。
【堆排序】
堆是一种特殊的完全二叉树，分为小根堆和大根堆两种。如果对于任意一课子树都满足根的权<=两个儿子的权，则为小根堆。反过来为大根堆。
堆的好处在于其根一定是堆中所有元素中最小（大）的元素。如果我们将原序列建立成一个小根堆，每次将根元素取出，然后删除该元素。操作序列元素个数次，最终将得到一个升序序列。
小根堆维护将用到两种操作：UP(x)当x非根且x比其父亲元素小，则交换x与其父亲；Down(x)当x比其儿子任何一个要大时，将x与较大的儿子交换，递归Down（x交换后的位置）。
由于是完全二叉树，所以一个节点x如果有左儿子，则其左儿子编号一定是x*2；x如果有右儿子，则其右儿子编号一定是x*2+1。
Pascal代码：
var i,j,k,l,m,n:longint;
a:array[0..100000] of longint;
procedure up(x:longint);
var g:longint;
begin
if (x=1) then exit;
if (a[x]>=a[x div 2]) then exit;
g:=a[x];a[x]:=a[x div 2];a[x div 2]:=g;
up(x div 2);
end;
procedure down(x:longint);
var g,t:longint;
begin
g:=x;
if (x*2<=n) and (a[g]>a[x*2]) then g:=x*2;
if (x*2<n) and (a[g]>a[x*2+1]) then g:=x*2+1;
if (g=x) then exit;
t:=a[x];a[x]:=a[g];a[g]:=t;
down(g);
end;
begin
read(n);
for i:=1 to n do
begin
read(a[i]);
up[i];
end;
for i:=1 to n do
begin
writeln(a[1]);
a[1]:=maxlongint;
down(1);
end;
end.
时间复杂度：堆维护复杂度为LogN，所以总复杂度为O(NLogN)
【计数排序】
当元素的取值范围比较小的时候，可以考虑用计数排序。这是一种很简单的排序方式，开一个元素取值范围的数组，一次扫描元素，每扫描到一个元素数组中相应的位置计数结果+1。这样扫描一次后再顺序扫描整个统计数组，就得到了最终的排序结果。
Pascal代码：
var i,j,n:longint;
t:array[-100000..100000] of longint;
begin
read(n);
for i:=1 to n do
begin
read(j);inc(t[j]);
end;
for i:=-100000 to 100000 do
for j:=1 to t[i] do
writeln(i);
end.
时间复杂度：O(N)
【基数排序】
一种非交换的排序方式，这种排序打破了交换排序时间复杂度O(NLogN)下限的限制。一个简单的例子是我们先将数据按照个位进行计数排序，再按照十位排，再按百位排，以此类推。这中算法每次排某一位的时间复杂度是O(N)，一共要排最大数字位数次，因此复杂度为位数*元素个数。
Pascal代码:
const ten:array[0..10] of int64=(1,10,100,1000,10000,100000,1000000,
10000000,100000000,1000000000,10000000000);
var i,j,k,l,m,n,max:longint;
a:array[0..100000] of longint;
tot:array[0..1000000] of longint;
tp:array[0..9] of longint;
begin
read(n);max:=0;
for i:=1 to n do
begin
read(a[i]);
if (a[i]>max) then max:=a[i];
end;
k:=0;
while (max>0) do
begin
inc(k);max:=max div 10;
end;
for i:=1 to k do
begin
for j:=0 to 9 do tp[j]:=j*n;
for j:=1 to n do
begin
l:=(a[j] mod ten[i]) div ten[i-1];
inc(tp[l]);
tot[tp[l]]:=a[j];
end;
m:=0;
for j:=0 to 9 do
for l:=j*n+1 to tp[j] do
begin
inc(m);
a[m]:=tot[l];
end;
end;
for i:=1 to n do writeln(a[i]);
end.
这里我用的是以空间换时间的方法，将统计数组开到元素个数的10倍。其实更好的方法是开一个链表。本程序只适合仅含有非负数的排序。如果含有负数应该作相应的改变。
【多关键字排序】
一个很实际的例子就是奥运会金牌榜的排序。在各个国家的排名中，我们先比较国家金牌个数，金牌个数相同的情况下比较银牌个数，银牌个数相同的情况下比较铜牌个数。这就是一个典型的3关键字排序。金牌数为第一关键字，银牌数为第二关键字，铜牌数为第三关键字。
多关键字排序也要基于以上或其他的排序算法，只是其比较方式有区别。上面的比较方式是直接对值进行比较从而得出大小关系，而多关键字排序并不总能通过一次比较得出两元素的大小关系。首先对第一关键字进行比较，如果不相等，则将其比较结果作为元素大小关系。如果相等，则需比较第二关键字。以此类推。只有所有关键字分别相等，才能说两个元素相等。
如果我们用二维数组a[1..n][1..m]表示n个m关键字的元素，现在要比较元素i和元素j，则比较函数伪代码为：
function compare(i,j as longint);
var t as longint;
{
for t<-1 to m
if (a[i][t]>a[j,t]) {return i 元素大于 j 元素}
else if (a[i][t]<a[j][t]) {return i 元素小于 j 元素}
return i 元素等于 j 元素
}
【总结】
本文对各种排序算法和思想作了初步的介绍和简单的分析。其实，还有很多著名的排序算法，如希尔排序，限于篇幅和使用频率而没有介绍。如果有兴趣大家找到相关资料来学习。
由于水平有限，文中难免出现各种错误和遗漏。欢迎大家提出宝贵意见！
【什么是排序算法】
在实际信息处理过程中，我们时常需要将数据按一定顺序排序以增强数据的可用性。因此，好的排序算法是十分重要的。下面将简单介绍几种排序算法，他们各自都有一些优势。
【冒泡排序】
这种算法十分简单易懂。它之所以被叫做冒泡排序，是因为它的思想是每次将剩余未排序数据中最小（大）的数据通过交换浮动到剩余序列的开头，类似于烧开水轻的气泡往上冒的过程。
具体过程：每次从后往前扫描未排序的序列，依次比较相邻的元素。如果后一个元素小于前一个元素则交换。这样最终剩余序列中的最小的元素就到了序列的开头。这样做序列元素个数次，就得到了一个升序的序列。
Pascal代码：
var i,j,k,n:longint;
a:array[0..1000] of longint;
begin
read(n);
for i:=1 to n do read(a[i]);
for i:=1 to n-1 do
for j:=n-1 downto i do
if (a[j]>a[j+1]) then
begin
k:=a[j];a[j]:=a[j+1];a[j+1];=k;
end;
for i:=1 to n do writeln(a[i]);
end.
时间复杂度：O(N^2)
【选择排序】
这种算法和冒泡排序的代码十分相似，核心思想是按照一定的顺序比较任意一对元素，如果位置靠前的元素大于位置靠后的元素则交换两个元素。最终将得到一个升序的序列。
Pascal代码：
var i,j,k,n:longint;
a:array[0..1000] of longint;
begin
read(n);
for i:=1 to n do read(a[i]);
for i:=1 to n-1 do
for j:=i+1 to n do
if (a[i]>a[j]) then
begin
k:=a[i];a[i]:=a[j];a[j];=k;
end;
for i:=1 to n do writeln(a[i]);
end.
时间复杂度：O(N^2)
【归并排序】
一种典型的分治排序算法。
所谓分治算法，就是一个问题可以划分为几个性质相同但规模较小的子问题，且解决子问题之后可以很容易解决原问题。我们递归这种划分问题缩小规模的做法，直到问题规模小到可以直接出解，再回溯解决其父问题。直至最终得到原问题的解。
归并排序的流程如下：
如果要排序的序列长度为1，无需再进行其他操作，直接回溯。
否则将该序列从中间劈开化为前后两段长度相同或差1的子序列。递归排序两子序列。
设置两个标记，分别指向两个子序列的开头。循环序列长度次以下操作：
找到两标记处较小的元素，加入新队列的队尾，后移那个标记。
这样，我们将该序列排好了。如果这就是原序列，直接输出。否则回溯到其父问题。
Pascal代码：
var i,j,k,l,m,n,p,q:longint;
a,tmp:array[0..100000] of longint;
procedure Gbsort(x,y:longint);
var t:longint;
begin
if (x=y) then exit;
t:=(x+y) div 2;
Gbsort(x,t);
Gbsort(t+1,y);
p:=x;q:=t+1;
for k:=x to y do
begin
if (p>t) then
begin
tmp[k]:=a[q];
inc(q);
end else
if (q>y) then
begin
tmp[k]:=a[p];
inc(p);
end else
begin
if (a[p]<a[q]) then
begin
tmp[k]:=a[p];inc(p);
end else
begin
tmp[k]:=a[q];inc(q);
end;
end;
end;
for k:=x to y do a[k]:=tmp[k];
end;
begin
read(n);
for i:=1 to n do read(a[i]);
Gbsort(1,n);
for i:=1 to n do writeln(a[i]);
end.
时间复杂度：由于我们递归LogN（在OI中表示以2为底N的对数）层，每层中实际上做了N这个数量级的操作。因此归并排序时间复杂度为O(NLogN)
【快速排序】
在实践中最快的排序方法。用到了分治的思想。
每次在当前序列中找一个数，通过序列长度次操作将序列分成两段，一段中所有元素比选择的元素不大，另一段中所有元素比选择的元素不小，且第一段在前，第二段在后。递归排序两段，这样最终得到原问题的解。
Pascal代码：
var i,j,k,l,n:longint;
a:array[0..100000] of longint;
procedure qsort(x,y:longint);
var g,t,l,r:longint;
begin
l:=x;r:=y;
t:=a[(x+y) div 2];
repeat
while (a[l]<t) do inc(l);
while (a[r]>t) do dec(r);
if (l<=r) then
begin
g:=a[l];a[l]:=a[r];a[r]:=g;
inc(l);dec(r);
end;
until l>r;
if (x<r) then qsort(x,r);
if (l<y) then qsort(l,y);
end;
begin
read(n);
for i:=1 to n do read(a[i]);
qsort(1,n);
for i:=1 to n do writeln(a[i]);
end.
时间复杂度：期望上来说为O(NLogN)
但是，快排可能退化。极端情况，如果每次划分都使得一段长度为1，另一段长度为原序列长度-1。快排的复杂度将退化成O(N^2)。这主要取决于选择中间元素的方法和数据的构造。所以，随机选择中间元素t不失为一个好的选择。另外，当序列长度已经很小时，如果依然递归快排，系统由于开堆栈而耗费的时间将抵消LogN少于N的时间。反而是选择排序更快。所以，一个优化是当该问题所排序列长度<20左右时直接选择排序后回溯，否则再执行递归的快排。
【堆排序】
堆是一种特殊的完全二叉树，分为小根堆和大根堆两种。如果对于任意一课子树都满足根的权<=两个儿子的权，则为小根堆。反过来为大根堆。
堆的好处在于其根一定是堆中所有元素中最小（大）的元素。如果我们将原序列建立成一个小根堆，每次将根元素取出，然后删除该元素。操作序列元素个数次，最终将得到一个升序序列。
小根堆维护将用到两种操作：UP(x)当x非根且x比其父亲元素小，则交换x与其父亲；Down(x)当x比其儿子任何一个要大时，将x与较大的儿子交换，递归Down（x交换后的位置）。
由于是完全二叉树，所以一个节点x如果有左儿子，则其左儿子编号一定是x*2；x如果有右儿子，则其右儿子编号一定是x*2+1。
Pascal代码：
var i,j,k,l,m,n:longint;
a:array[0..100000] of longint;
procedure up(x:longint);
var g:longint;
begin
if (x=1) then exit;
if (a[x]>=a[x div 2]) then exit;
g:=a[x];a[x]:=a[x div 2];a[x div 2]:=g;
up(x div 2);
end;
procedure down(x:longint);
var g,t:longint;
begin
g:=x;
if (x*2<=n) and (a[g]>a[x*2]) then g:=x*2;
if (x*2<n) and (a[g]>a[x*2+1]) then g:=x*2+1;
if (g=x) then exit;
t:=a[x];a[x]:=a[g];a[g]:=t;
down(g);
end;
begin
read(n);
for i:=1 to n do
begin
read(a[i]);
up[i];
end;
for i:=1 to n do
begin
writeln(a[1]);
a[1]:=maxlongint;
down(1);
end;
end.
时间复杂度：堆维护复杂度为LogN，所以总复杂度为O(NLogN)
【计数排序】
当元素的取值范围比较小的时候，可以考虑用计数排序。这是一种很简单的排序方式，开一个元素取值范围的数组，一次扫描元素，每扫描到一个元素数组中相应的位置计数结果+1。这样扫描一次后再顺序扫描整个统计数组，就得到了最终的排序结果。
Pascal代码：
var i,j,n:longint;
t:array[-100000..100000] of longint;
begin
read(n);
for i:=1 to n do
begin
read(j);inc(t[j]);
end;
for i:=-100000 to 100000 do
for j:=1 to t[i] do
writeln(i);
end.
时间复杂度：O(N)
【基数排序】
一种非交换的排序方式，这种排序打破了交换排序时间复杂度O(NLogN)下限的限制。一个简单的例子是我们先将数据按照个位进行计数排序，再按照十位排，再按百位排，以此类推。这中算法每次排某一位的时间复杂度是O(N)，一共要排最大数字位数次，因此复杂度为位数*元素个数。
Pascal代码:
const ten:array[0..10] of int64=(1,10,100,1000,10000,100000,1000000,
10000000,100000000,1000000000,10000000000);
var i,j,k,l,m,n,max:longint;
a:array[0..100000] of longint;
tot:array[0..1000000] of longint;
tp:array[0..9] of longint;
begin
read(n);max:=0;
for i:=1 to n do
begin
read(a[i]);
if (a[i]>max) then max:=a[i];
end;
k:=0;
while (max>0) do
begin
inc(k);max:=max div 10;
end;
for i:=1 to k do
begin
for j:=0 to 9 do tp[j]:=j*n;
for j:=1 to n do
begin
l:=(a[j] mod ten[i]) div ten[i-1];
inc(tp[l]);
tot[tp[l]]:=a[j];
end;
m:=0;
for j:=0 to 9 do
for l:=j*n+1 to tp[j] do
begin
inc(m);
a[m]:=tot[l];
end;
end;
for i:=1 to n do writeln(a[i]);
end.
这里我用的是以空间换时间的方法，将统计数组开到元素个数的10倍。其实更好的方法是开一个链表。本程序只适合仅含有非负数的排序。如果含有负数应该作相应的改变。
【多关键字排序】
一个很实际的例子就是奥运会金牌榜的排序。在各个国家的排名中，我们先比较国家金牌个数，金牌个数相同的情况下比较银牌个数，银牌个数相同的情况下比较铜牌个数。这就是一个典型的3关键字排序。金牌数为第一关键字，银牌数为第二关键字，铜牌数为第三关键字。
多关键字排序也要基于以上或其他的排序算法，只是其比较方式有区别。上面的比较方式是直接对值进行比较从而得出大小关系，而多关键字排序并不总能通过一次比较得出两元素的大小关系。首先对第一关键字进行比较，如果不相等，则将其比较结果作为元素大小关系。如果相等，则需比较第二关键字。以此类推。只有所有关键字分别相等，才能说两个元素相等。
如果我们用二维数组a[1..n][1..m]表示n个m关键字的元素，现在要比较元素i和元素j，则比较函数伪代码为：
function compare(i,j as longint);
var t as longint;
{
for t<-1 to m
if (a[i][t]>a[j,t]) {return i 元素大于 j 元素}
else if (a[i][t]<a[j][t]) {return i 元素小于 j 元素}
return i 元素等于 j 元素
}
【总结】
本文对各种排序算法和思想作了初步的介绍和简单的分析。其实，还有很多著名的排序算法，如希尔排序，限于篇幅和使用频率而没有介绍。如果有兴趣大家找到相关资料来学习。
由于水平有限，文中难免出现各种错误和遗漏。欢迎大家提出宝贵意见！
网友评论：
 | 1 Akai 于 2010-04-23 17:35:31 说： | 回复 |
|---|---|---|
抢沙发 外加支持一下 火前留名
| ||
 | 2 Admin 于 2010-04-24 14:28:43 说： | 回复 |
回复Akai：谢谢支持!
我会努力做得更好! | ||
 | 3 claire_ 于 2010-04-25 20:52:18 说： | 回复 |
我怎么感觉我好像连排序都不会了
| ||
| 4 Admin 于 2010-05-10 22:57:47 说： | 回复 |
回复claire_：神牛谦虚！
OI，我心飞翔！ | ||
 | 5 Guest 于 2010-05-12 23:53:27 说： | 回复 |
顶一下下，强大的RC
| ||
| 6 lonelycorn 于 2010-05-14 23:34:53 说： | 回复 |
隐约觉得css有改动余地
| ||
| 7 Admin 于 2010-05-15 18:56:54 说： | 回复 |
回复lonelycorn：欢迎提出建议！我会不断完善！
|