数据结构与算法-算法篇：排序—冒泡排序（一）

数据结构与算法系列文章：数据结构与算法目录

冒泡排序无疑是最为出名的排序算法之一，从序列的一端开始往另一端冒泡（你可以从左往右冒泡，也可以从右往左冒泡，看心情），依次比较相邻的两个数的大小（到底是比大还是比小也看你心情）。

冒泡优化：

冒泡有一个最大的问题就是这种算法不管不管你有序还是没序，都会挨个循环比较。

举个数组例子：[ 9，8，7，6，5 ]，一个有序的数组，根本不需要排序，它仍然是双层循环一个不少的把数据遍历干净，这其实就是做了没必要做的事情，属于浪费资源。

针对这个问题，我们可以设定一个临时标志，来标记该数组是否已经有序，如果有序了就不用遍历了。

实现：

/// <summary>
/// 冒泡排序
/// </summary>
/// <param name="arr"></param>
public void BubbleSort(int[] arr)
{
    int len = arr.Length;
    int temp;
    for (int i = 0; i < len; i++)
    {
        // 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
        bool flag = true;
        for (int j = 0; j < len - 1 - i; j++)
        {
            // 相邻元素两两对比
            if (arr[j] > arr[j + 1])
            {
                // 元素交换
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;

                flag = false;
            }
        }

        if (flag)
        {
            break;
        }
    }
}