冒泡排序算法

时间：2011-05-25 来源：傅红雪2011

一、基本思想

依次比较相邻的两个数，将小数放在前面，大数放在后面。

第1趟：

　　首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。

第2趟：

　　仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。

如此下去，重复以上过程，直至最终完成排序。

由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。

二、排序过程

需要排序的数列：49 38 65 97 76 13 27

排序过程：

38 49 65 76 13 27 97

38 49 65 13 27 76 97

38 49 13 27 65 76 97

38 13 27 49 65 76 97

13 27 38 49 65 76 97

三、代码示例

冒泡排序

using System;

namespace BubbleSortService
{
    public class BubbleSortService
    {
        static void Main(string[] args)
        {
            // 判断参数
            int argsLength = args.Length;
            if (argsLength == 0)
            {
                Console.WriteLine("请输入参数！");
                return;
            }
            int arg;
            int[] sortArray = new int[argsLength];
            for (int i = 0; i < argsLength; i++)
            {
                if (!int.TryParse(args[i], out arg))
                {
                    Console.WriteLine("参数必须全都为数字！");
                    return;
                }
                sortArray[i] = arg;
            }

            // 排序
            BubbleSortService bubble = new BubbleSortService();
            sortArray = bubble.BubbleSort(sortArray);
        }

        /// <summary>
        /// 冒泡排序算法
        /// </summary>
        /// <param name="arr">数字数组</param>
        /// <returns>排好序的数字数组</returns>
        public int[] BubbleSort(int[] arr)
        {
            int temp;
            for (int i = 0; i < arr.Length; i++ )
            {
                for (int j = 0; j < arr.Length - 1 - i; j++)
                {
                    if (arr[j] > arr[j + 1])
                    {
                        temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
                Console.WriteLine("");
                foreach (int item in arr)
                {
                    Console.Write(item + " ");
                }
            }
            return arr;
        }
    }
}

运行结果：

四、算法改进

1、设置标志位表明数列已排好序

　　假设需用冒泡排序将4、5、7、1、2、3这6个数排序。在该列中，第三趟排序结束后，数组已排好序，但计算机此时并不知道，因此还需要进行一趟比较。如果这一趟比较中未发生任何数据交换，则计算机知道已排序好，可以不再进行比较了。因而第四趟比较需要进行，但第五趟比较则是不必要的。为此，我们可以考虑程序的优化。

　　为了标志是否需要继续比较，声明一个布尔量flag，在进行每趟比较前将flag置true。如果在比较中发生了数据交换，则将flag置为false，在一趟比较结束后，再判断flag，如果它仍为true（表明在该趟比较中未发生一次数据交换）则结束排序，否则进行下一趟比较。

2、双向冒泡排序

　　又叫鸡尾酒排序算法，和冒泡排序的“编程复杂度”一样，但对随机序列排序性能稍高于普通冒泡排序，但是因为是双向冒泡，每次循环都双向检查，极端环境下会出现额外的比较，导致算法性能的退化，比如“4、5、7、1、2、3”这个序列就会出现退化

代码如下：

双向冒泡排序

/// <summary>
/// 双向冒泡排序算法
/// </summary>
/// <param name="arr">数字数组</param>
/// <returns>排好序的数字数组</returns>
public int[] BubbleSortTwoWay(int[] arr)
{
    int temp;
    int left = 1;
    int length = arr.Length;
    int right = length - 1;
    int t = 0;

    do
    {
        for (int i = right; i >= left; i--)
        {
            if (arr[i] < arr[i - 1])
            {
                temp = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = temp;
                t = i;
            }
        }
        left = t + 1;
        Console.WriteLine("");
        foreach (var item in arr)
        {
            Console.Write(item + " ");
        }

        for (int i = left; i < right + 1; i++)
        {
            if (arr[i] < arr[i - 1])
            {
                temp = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = temp;
                t = i;
            }
        }
        right = t - 1;
        Console.WriteLine("");
        foreach (var item in arr)
        {
            Console.Write(item + " ");
        }
    } while (left <= right);
    return arr;
}

五、算法分析

1、时间复杂度

若记录序列的初始状态为"正序"，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次交换，且不移动记录；反之，若记录序列的初始状态为"逆序"，则需进行n(n-1)/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)（即n的平方）。

2、空间复杂度

在冒泡排序的过程中，设置一个变量用来交换元素，所以空间复杂度为O(1)

3、排序稳定性

冒泡排序是稳定的