用户登录:

用户名:
密码:      

文章分类:


最新评论:

userleijiankun 说:膜拜神牛。……
usercss 说:康拓展开和逆康拓展……
usersongrenchu 说:欢迎大家踊……
userAdmin 说:……

浅谈几种排序算法

发表时间:2010-04-23 15:28:31  浏览(7863) 评论(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 元素
}

【总结】
    本文对各种排序算法和思想作了初步的介绍和简单的分析。其实,还有很多著名的排序算法,如希尔排序,限于篇幅和使用频率而没有介绍。如果有兴趣大家找到相关资料来学习。
    由于水平有限,文中难免出现各种错误和遗漏。欢迎大家提出宝贵意见!

网友评论:

user1  Akai 于 2010-04-23 17:35:31 说:回复
抢沙发 外加支持一下 火前留名
user2  Admin 于 2010-04-24 14:28:43 说:回复
回复Akai:谢谢支持!
          我会努力做得更好!

user3  claire_ 于 2010-04-25 20:52:18 说:回复
我怎么感觉我好像连排序都不会了
user4  Admin 于 2010-05-10 22:57:47 说:回复
回复claire_:神牛谦虚!
             OI,我心飞翔!
user5  Guest 于 2010-05-12 23:53:27 说:回复
顶一下下,强大的RC
user6  lonelycorn 于 2010-05-14 23:34:53 说:回复
隐约觉得css有改动余地
user7  Admin 于 2010-05-15 18:56:54 说:回复
回复lonelycorn:欢迎提出建议!我会不断完善!

Guest 发表评论