Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3882042
  • 博文数量: 408
  • 博客积分: 10227
  • 博客等级: 上将
  • 技术积分: 9820
  • 用 户 组: 普通用户
  • 注册时间: 2009-04-17 21:48
个人简介

非淡泊无以明志,非宁静无以致远

文章存档

2022年(1)

2021年(1)

2020年(2)

2019年(5)

2018年(4)

2017年(3)

2016年(24)

2015年(8)

2014年(7)

2013年(3)

2012年(1)

2011年(23)

2010年(179)

2009年(147)

分类: C/C++

2010-04-17 22:56:18

交换排序主要是根据记录的关键字的大小,将记录交换来进行排序的。交换排序的特点是:将关键字值较大的记录向序列的后部移动,关键字较小的记录向前移动。这里介绍两种交换排序方法,它们是冒泡排序和快速排序。

一.冒泡排序

将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上"飘浮"。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。

1.算法思路

(1)jn2,将r[j].keyr[j-1].key比较,如果r[j].key,则把记录r[j]r[j-1]交换位置,否则不进行交换。最后是r[2].keyr[1].key对比,关键字较小的记录就换到r[1]的位置上,到此第一趟结束。最小关键字的记录就象最轻的气泡冒到顶部一样换到了文件的前边。

(2)jn3,重复上述的比较对换操作,最终r[2]之中存放的是剩余n-1个记录(r[1]除外)中关键字最小的记录。

(3) jni+1,经过一系列对联对比交换之后,r[i]之中是剩余若干记录中关键字最小的记录。

(4) jnn-1,将r[n].keyr[n-1].key对比,把关键字较小的记录交换到r[n-1]之中。

【例】设有一组关键字序列{ 55 22 44 11 33 },这里 n=5 ,即有 5 个记录。请将其按由小到大的顺序排序。

2.具体算法

template

  bubblesort(T r[],int n)

   { int t=1,tag,j;T x;

     do{ tag=0;

         for(j=n;j>=i;j--)

         if(r[j].key

         r[j-1]=x;tag=1;

        }

     i++;

   }while(tag==1&&i

 } //bubblesort

3.算法时间复杂度

该算法的时间复杂度为O(n2)。但是,当原始关键字序列已有序时,只进行一趟比较就结束,此时时间复杂度为O(n)

4.算法的稳定性:

算法是稳定的。

二.快速排序

快速排序由霍尔 (Hoare) 提出,它是一种对冒泡排序的改正。由于其排序速度快,故称快速排序 (quick sort) 。快速排序方法的实质是将一组关键字 [K 1 ,K 2 ,,K n ] 进行分区交换排序。

1.算法思路

①以第一个关键字 K 1 为控制字,将 [K 1 ,K 2 ,,K n ] 分成两个子区,使左区所有关键字小于等于 K 1 ,右区所有关键字大于等于 K 1 ,最后控制字居两个子区中间的适当位置。在子区内数据尚处于无序状态。

②将右区首、尾指针 ( 记录的下标号 ) 保存入栈,对左区进行与第①步相类似的处理,又得到它的左子区和右子区,控制字居中。

③重复第①、②步,直到左区处理完毕。然后退栈对一个个右子区进行相类似的处理,直到栈空。

由以上三步可以看出:快速排序算法总框架是进行多趟的分区处理;而对某一特定子区,则应把它看成又是一个待排序的文件,控制字总是取子区中第一个记录的关键字。现在设计一个函数 hoare ,它仅对某一待排序文件进行左、右子区的划分,使控制字居中;再设计一个主体框架函数 quicksort ,在这里多次调用 hoare 函数以实现对整个文件的排序。

快速排序各次划分后的状态变化
[49 38 65 97 76 13 27 49] //
初始关键字
[27 38 13] 49 [76 97 65 49] //
1次划分完成之后,对应递归树第2
[13] 27 [38] 49 [49 65] 76 [97] //
对上一层各无序区划分完成后,对应递归树第3

13 27 38 49 49 [65] 76 97 //对上一层各无序区划分完成后,对应递归树第4
13 27 38 49 49 65 76 97 //
最后的排序结果

2.具体算法:

void qsort(int *a,int l,int r){

     int i=l,j=r;

     int flag=a[l];//记录i记录的数值,这就是与它为标志,排序后能保证这个数左边小于等于它,右边大于等                       于它

    while(i

         //J找到一个比标志小的值并把它放在i下标处

        while(i

        if(i

        //i找到一个比标志小的值并把它放在j下标处

        while(i

        if(i

    }a[i]=flag;//经过上面的步骤之后能保证i=j,这时能确定标志数放在这里

    i--,j++;

    if(l左边递归

    if(j右边递归

}

3.快速排序算法分析

快速排序的非递归算法引用了辅助栈,它的深度为 log2n 。假设每一次分区处理所得的两个子区长度相近,那么可入栈的子区长度分别为:n/21n/22n/23 n/24 , n/2k ,又因为 n/2k=1, 所以 k= log2n 。分母中 2 的指数恰好反映出需要入栈的子区个数,它就是 log2n ,也即栈的深度。在最坏情况下,比如原文件关键字已经有序,每次分区处理仅能得到一个子区。可入的子区个数接近 n, 此时栈的最大深度为 n.

快速排序主体算法时间运算量约 O(log2n) ,划分子区函数运算量约 O(n) ,所以总的时间复杂度为 O(nlog2n) ,它显然优于冒泡排序 O(n2). 可是算法的优势并不是绝对的。试分析,当原文件关键字有序时,快速排序时间复杂度是 O(n2), 这种情况下快速排序不快。而这种情况的冒泡排序是 O(n), 反而很快。在原文件记录关键字无序时的多种排序方法中,快速排序被认为是最好的一种排序方法。

4.算法稳定性:快速排序是不稳定的。

阅读(5860) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~