加载中…
个人资料
_陌上花开7_
_陌上花开7_
  • 博客等级:
  • 博客积分:0
  • 博客访问:68,244
  • 关注人气:29
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

交换排序(冒泡排序、快速排序)

(2013-08-27 21:40:39)
标签:

交换排序

冒泡排序

快速排序

it

分类: 数据结构

所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。

一、冒泡排序

冒泡排序(Bubble Sort)是一种最直观的排序方法,在排序过程中,将相邻的记录的关键字进行比较,若前面记录的关键字大于后面记录的关键字,则将它们交换,否则不交换。或者反过来,使较大关键字的记录后移,像水中的气泡一样,较小的记录向前冒出,较大的记录像石头沉入后部。故称此方法为冒泡排序法。

算法的基本思想为:首先在n个元素中,若ai>ai+1(i=1..n-1)则交换,遮阳得到一个最大元素放于an;其次在n-1个元素中,若ai>ai+1(i=1..n-2)则交换,这样得到的一个次大元素放于an-1,以此类推,直到选出n-1个元素,排序完成。

交换排序(冒泡排序、快速排序)

冒泡排序算法:

void BubbleSort(int r[],int n)//单元用作交换操作的暂存单元

{

   exchange=n; //第一趟起泡排序的区间是[1,n]

   while (exchange!=0) //当上一趟排序有记录交换时

   {

      bound=exchange;

      exchange=0;

      for(j=1;j<bound;j++)

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

        {

           交换r[j]和r[j+1];

           exchange=j;//记载每一次记录交换的位置

        }

   }

  

}

由冒泡排序算法可看出,若初始记录序列就是正序的,则只需一趟扫描即可完成排序,此时所需的关键字比较和记录移动的次数均为最小值:Cmin=n-1,Mmin=0.

即冒泡排序最好的时间复杂度为O(n);相反,若原始记录序列是反序的,则需要进行n-1趟排序,每趟排序需要进行n-i次关键字的比较(1<=i<=n-1),且每次比较都必须移动记录三次达到交换记录位置的目的,此时,关键字比较和记录移动的次数均达到最大值:Cmax=(n(n-1))/2,Mmax=(3n(n-1))/2。

因此,冒泡排序的最坏时间复杂度为O(n^2),在平均情况下,关键字的比较和记录的移动次数大约为最坏情况下的一半,因此冒泡排序算法的时间复杂度为O(n^2)。

同时,冒泡排序是以稳定的排序方法。

 

二、快速排序

快速排序(Quick Sorting)是对冒泡排序的一种改进。在冒泡排序中,记录的比较和交换是在相邻的单元中进行的,记录每次交换只能上移或下移一个单元,因而总的比较和移动次数较多。而在快速排序中,记录的比较和交换是从两端向中间进行的,关键字较小的记录一次就能从后面单元交换到前面去,而关键字较大的记录一次就能从前面的单元交换到后面的单元,记录每次移动的记录较远,因此可以减少记录总的比较和移动次数。

快速排序的基本做法是:任取待排序的n个记录中的某个记录作为基准(一般选取第一个记录),通过一趟排序,将待排序记录分成左右两个字序列,左子序列记录的关键字均小于或等于该基准记录的关键字,右子序列记录的关键字均大于或等于该基准记录的关键字,从而得到该记录最终排序的位置,然后该记录不再参加排序,此一趟排序成为第一趟快速排序。然后对所分得左右子序列分别重复上述方法,直到所有的记录都处在他们的最终位置,此时排序完成。在快速排序中,有时把待排序序列按照基准记录的关键字分为左右两个子序列的过程称为一次划分。

交换排序(冒泡排序、快速排序)

快速排序的过程为:

设待排序序列为r[s..t],为实现一次划分,可设置两个指针low和high,他们的初值分别为s和t。以r[s]为基准,在划分的过程中:
(1)从high端开始,依次向前扫描,并将扫描到的每一个记录的关键字同r[s](即基准记录)的关键字进行比较,直到r[high].key
(2)从low端开始,依次向后扫描,并将扫描到的每一个记录的关键字同r[s](即基准记录)的关键字进行比较,直到r[low].key>r[s].key时,将r[low]赋值到high所指的位置。
(3)如此交替改变扫描方向,重复上述两个步骤从两端各自向中间位置靠拢,直到low等于或大于high。经过此次划分后得到的左右两个子序列分别为r[s..low-1]和r[low+1..t]。然后对这两个子序列按上述方法进行再次划分,依次重复,直到每个序列只剩一个元素为止。

 任意子序列r[low..high]的一趟划分算法:

交换排序(冒泡排序、快速排序)

交换排序(冒泡排序、快速排序)



在快速排序中,若把每次划分所用的基准记录看作根节点,把划分得到的左子序列和右子序列分别看成根节点的左、右子树,那么整个排序过程就对应着一颗具有n个节点的二叉排序树,所需划分的层数等于二叉树的深度,所需划分的所有子序列数等于二叉树分枝结点数,而在快速排序中,记录的移动次数通常小于记录的比较次数。因此,讨论快速排序的时间复杂度时,仅考虑记录的比较次数即可。
若快速排序出现最好的情况(左、右子序列的长度大致相等),则结点数n与二叉树深度h应满足log2(n)<=h<=log2(n+1),所以总的比较次数不会超过(n+1)log2(n).因此,快速排序的最好时间复杂度应为O(nlog2(n))。若快速排序出现最坏的情况(每次能划分成两个子序列,但是其中一个为空),则此时得到的二叉树是一棵单枝树,得到的非空子序列包含有n-i(i代表二叉树的层数),每层划分需要比较n-i+2次,所以总的比较次数为(n^2+3n-4)/2.因此,快速排序的最坏时间复杂度为O(n^2).
快速排序所占用的辅助空间为递归时所需栈的深度,故空间复杂度为O(log2(n))。同时,快速排序是不稳定的排序。

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有