注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

天涯倦客的博客

祝福你朋友永远快乐!

 
 
 

日志

 
 

C# 冒泡排序  

2011-02-25 14:27:34|  分类: C# |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

冒泡排序(Bubble Sort)的基本思想是:将相邻的记录的关键码进行比较,若前面记录的关键码大于后面记录的关键码,则将它们交换,否则不交换。
设待排序的顺序表sqList中有n个记录,冒泡排序要进行n-1趟,每趟循环均是从最后两个记录开始。第1趟循环到第2个记录的关键码与第1个记录的关键码比较后终止,第2趟循环到第3个记录的关键码与第2个记录的关键码比较结束后终止。一般地,第i趟循环到第i+1个记录的关键码与第i个记录的关键码比较后终止,所以,第n-1趟循环到第n个记录的关键码与第n-1个记录的关键码比较后终止。
冒泡排序算法的实现如下所示,算法中记录的比较表示记录关键码的比较,顺序表中只存放了记录的关键码:

public void BubbleSort(List<int> sqList)
        {
            int tmp;
            for (int i = 0; i < sqList.Count; ++i)
            {
                for (int j = (sqList.Count - 2); j >= i; --j)
                {
                    if (sqList[j + 1] < sqList[j])
                    {
                        tmp = sqList[j + 1];
                        sqList[j + 1] = sqList[j];
                        sqList[j] = tmp;
                    } 
                }
            }
        }

冒泡排序算法的最好情况是记录已全部排好序,这时,循环n-1次,每次循环都因没有数据交换而退出。因此,冒泡排序算法在最好情况下的时间复杂度为O(n)。冒泡排序算法的最坏情况是记录全部逆序存放,这时,循环n-1次,总比较次数为: Σ?=?=??2n0i2)1n(n)i1n(
总的移动次数为比较次数的3倍,因为被进行一次比较,需要进行3次移动。因此,冒泡排序算法在最坏情况下的时间复杂度为O(n2)。
冒泡排序算法只需要一个辅助空间用于交换记录,所以,冒泡排序算法是一种稳定的排序方法。

  评论这张
 
阅读(580)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017