交換排序:冒泡排序vs快速排序 - elvinle－IT工程師數位筆記本

文章出處

在開發的過程中, 經常會遇到集合排序, 那么一般情況下, 我們都是使用list.OrderBy()的方式來排序, 也無需關注到里面算法的實現是個什么樣子. 正好這幾天準備回顧一下數據結構與算法.

首先來了解一下, 排序大致可以分為哪幾種:

　　交換排序：包括冒泡排序，快速排序。

選擇排序：包括直接選擇排序，堆排序。

插入排序：包括直接插入排序，希爾排序。

合并排序：合并排序。

List.OrderBy()采取的就是快速排序方式. 冒泡排序既然和它是同一種排序方式, 那么我們將他們比較一下看看. 看看哪一種排序更好一點.

一、示例(先看結果, 再講思想)

static void Test()
{
    //五次比較
    for (int i = 1; i <= 5; i++)
    {
        List<int> list = new List<int>();
        //插入2k個隨機數到數組中
        for (int j = 0; j < 2000; j++)
        {
            Thread.Sleep(3);
            list.Add(new Random((int)DateTime.Now.Ticks).Next(0, 100000));
        }

        Console.WriteLine("\n第" + i + "次比較：{0}...", string.Join(",", list.Take(10)));

        Stopwatch watch = new Stopwatch();
        watch.Start();
        var result = list.OrderBy(single => single).ToList();
        watch.Stop();
        Console.WriteLine("\n快速排序耗費時間：" + watch.ElapsedMilliseconds);
        Console.WriteLine("輸出前是十個數:" + string.Join(",", result.Take(10).ToList()));
        watch.Start();
        result = BubbleSort(list);
        watch.Stop();
        Console.WriteLine("\n冒泡排序耗費時間：" + watch.ElapsedMilliseconds);
        Console.WriteLine("輸出前是十個數:" + string.Join(",", result.Take(10).ToList()));
    }
}

//冒泡排序算法
static List<int> BubbleSort(List<int> list)
{
    int temp;
    int count = list.Count;
    //第一層循環： 表明要比較的次數，比如list.count個數，肯定要比較count-1次
    for (int i = 0; i < count - 1; i++)
    {
        //list.count-1：取數據最后一個數下標，
        //j>i: 從后往前的的下標一定大于從前往后的下標，否則就超越了。
        for (int j = count - 1; j > i; j--)
        {
            //如果前面一個數大于后面一個數則交換
            if (list[j - 1] > list[j])
            {
                temp = list[j - 1];
                list[j - 1] = list[j];
                list[j] = temp;
            }
        }
    }
    return list;
}

這段代碼是從參考鏈接里面拿的, 個人比較懶啊, 而且冒泡排序算法還是很簡單的, 就不自己寫了

從上面的結果來看, 快速排序比冒泡排序快的不是一星半點啊.

看到了神奇之處, 接下來就是深入了解一下, 算法的思想和實現.

二、思想及實現

1. 冒泡排序

首先來解釋一下冒泡吧, 在水里面, 呼出一口氣, 形成一個泡泡, 這個泡泡會在上升的過程中, 逐漸變大(水壓越來越小導致的). 最后露出說面破掉了.

聯系著這種思想, 可以想到, 冒泡排序, 應該就是讓大的數, 逐漸往上升, 一直升到比它大的數前面, 破掉了.

根據這種思想, 就大致有一個過程在腦海中形成了, 來看一下代碼: (下面的圖還蠻形象的, 就偷過來了)

//冒泡排序算法
static List<int> BubbleSort1(List<int> list)
{
    int temp;
    int count = list.Count;
    for (int i = 0; i < count - 1; i++)
    {
        for (int j = 1; j < count; j++)
        {
            //如果前面一個數大于后面一個數則交換
            if (list[j - 1] > list[j])
            {
                temp = list[j - 1];
                list[j - 1] = list[j];
                list[j] = temp;
            }
        }
    }
    return list;
}

首先, 每一次循環, 我都能確定一個數的位置, 那么需要循環多少次呢? 最后一個數應該不需要再循環比較了吧, 也沒數跟他比較了. 所以循環n-1次就行了.

接著, 這里面的每一次循環, 其實就是一個冒泡的過程了. 把開始的數與后面一位數進行比較, 如果大于后面的數, 就向后移一位. (其實想想, 這個也挺麻煩的, 為啥比較一次就要移動一次呢? 我不能找到他的位置, 才互換么? 起碼減少了換的操作了)

我這里的代碼與上面示例的稍有不同, 稍微注意一下.

來看一下這里的時間復雜度, 雖然外面只循環了n-1次, 里面也只循環了n-3次, 看似復雜度為(n-1)*(n-3), 但是如果n夠大的話, -1或者-3甚至-100, 對最后的結果影響都是很小的.

按照最壞的情況算的話, 這里的冒泡排序的時間復雜度, 極限情況是O(n²), 那么他有沒有理想情況呢? 好像沒有啊, 就算這個數組已經排好序了, 好像程序還是要這樣從頭走到尾啊, 一點都沒有少什么. 所以這里的平均復雜度, 也是 O(n²). 這么看來, 冒泡排序并不是一種理想的排序方式.

如果不能提供更好的排序方式的話, 還是老老實實的使用List.OrderBy的方式去排序吧.

2. 快速排序

快速排序算法其實也叫分治法, 其步驟大致可以分為這么幾步:

　　1. 先從數列中取出一個數作為基準數Num(取得好的話, 是可以減少步驟的)

　　2. 分區, 將大于Num的數放在它的右邊, 小于或等于它的數放在它的左邊

　　3. 再對左右區間重復前兩操作, 直到各個區間只有一個數為止.

從上面的文字可能還是不太好理解這個過程, 那么我用一張圖片來描繪一下這個過程

經過一輪比較之后, 總感覺這里要遞歸啊. 牽涉到遞歸, 那么他的空間復雜度可能會比冒泡排序高一點.

既然一輪的過程已經清楚了, 那么就先寫出一輪的代碼好了

static int Division(List<int> list, int left, int right)
{
    int baseNum = list[left];

    while (left < right)
    {
        while (left < right && list[right] > baseNum)
        {
            right -= 1;
        }

        list[left] = list[right];
　　　　 while (left < right && list[left] <= baseNum)
        {
            left += 1;
        }

        list[right] = list[left];
    }
    list[left] = baseNum;
    return left;
}

這里的Left+=1和Right-=1都是有前提條件的, 前提條件為:Left < Right

接下來就比較簡單了, 一個遞歸調用, 這個遞歸的思想是很簡單的:

static void QuickSort(List<int> list, int left, int right)
{
    if (left < right)
    {
        int i = Division(list, left, right);

        QuickSort(list, left, i - 1);

        QuickSort(list, i + 1, right);
    }
}