Spiga

内排序（五）：冒泡排序

2012-07-20 13:33:03

一、基本思想

将被排序的记录的关键字垂直排列，首先将第一个记录的关键字与第二个记录的关键字进行比较，若前者大于后者，则交换两个记录，然后比较第二个记录与第三个记录的关键字，依次类推，直到第n-1个记录与第n个记录的关键字比较为止。上述过程称为第一趟起泡排序，其结果使得关键字最大的记录被安排在最后一个记录的位置上。然后进行第二趟起泡排序，对前n-1条记录进行同样的排序，使得关键字次大的记录被安排在第n-1个记录的位置上。一般地，第i趟起泡排序从第一条记录到第i条记录依次比较相邻两条记录的关键字，并在逆序时交换相邻记录，其结果使得这i条记录中关键字最大的记录被交换到第i条记录的位置上。整个排序过程需要K（1≤K≤n-1）趟起泡排序，判断起泡排序结束的条件是在一趟起泡排序的过程中，没有进行过记录交换的操作。从下图中可见，在起泡排序的过程中，关键字较小的记录像水中的气泡逐渐向上飘浮，而关键字较大的记录好比石块逐渐向下沉，每一次有一块最大的石块沉到底。

　　　　
二、冒泡排序的实现

public class BubbleSort
{
    public static List<int> Demo(List<int> data)
    {
        for (var i = 0; i < data.Count; i++)//i 
        {
            for (var j = 0; j < data.Count - 1 - i; j++)//j
            {
                if (data[j] > data[j + 1])
                {                    
                    var temp = data[j + 1];///空间复杂度
                    //J+1-->多了一个
                    data[j + 1] = data[j];//->j+1-->
                    data[j] = temp;
                }
            }
        }
        return data;
    }
}

三、时间复杂度分析

　　冒泡排序算法的最好情况是记录已全部排好序，这时，第一次循环时，因没有数据交换而退出
　　冒泡排序算法的最坏情况是记录全部逆序存放，这时，循环n-1次，比较和移动次数计算如下：
　　　　
　　冒泡排序算法是阶O(n2)的算法。这意味着执行算法所用的时间会按照数组大小的增加而成二次方增长。