浙江大學-數據結構-簡單排序-9.1.1

簡單排序

在這裡討論的是至少一萬個數字起步的排序，排序演算法的效率就變得非常重要，那在介紹各種排序演算法之前，我們先來講清楚幾個前提條件，首先我們來看，後面我們在介紹各種排序演算法的時候，它們的函數頭都有一個統一規範的格式，叫做X_Sort,Sort就是排序的意思，X是排序演算法的名稱，我們統一默認輸入的參數有兩個，一個是我們待排的元素放在一個數組裡，這個數組到底是什麼類型的呢？在這我們把它寫成是ElementType,它可以是任意的類型，只要你可以比較大小，就可以，那另外一個，是一個正整數N,表示的是我們要排的元素到底有多少個，在這裡頭，大多數情況下，為了簡單起見，我們默認討論的是整數的排序，當然了，也不是非得整數不可，字元串也可以排序，甚至是任何一種數據結構，它都可以，只要能夠排大小，都可以用我們的排序演算法，但是為了簡單起見，我們在這默認，如果不特別說明的話，我們默認討論的是整數的排序，而且我們默認的是把整數從小到大的排序，另外幾件細節性的事情，一個我們默認的N一定是合法的正整數，再一個我們只討論基於比較的排序，也就是在我們這些排序演算法中間，最重要的一件事情，是要能夠比大小，也就是說不管我是對整數排序，還是對字元串排序，還是對別的，任何一個什麼樣的ElementType排序，那我就假設的是小於，等於，大於這3個符號是有定義的，另外一個假設呢，是說我們在這隻討論內部排序，什麼叫內部排序呢，就是我們假設我們的內存空間充分大，所有的數據都可以一次性的被導到內存空間里，然後我們所有的排序過程是在內存裡面一次性完成的，這個叫做內部排序，當然於此相對的，我們就還有外部排序，外部排序就更複雜一點，就比如說你的內存空間有2GB,但是呢，要求你對10TB的數據進行排序，那麼你就不可能了，內部排序就不可能了，因為你的內存不夠大，裝不下所有的數據，那個時候你要怎麼辦呢，這就是一個更複雜的問題，在這門課里呢，我們不討論這個問題，那跟排序演算法相關的，還有一個很重要的概念叫做穩定性，什麼是穩定性呢？就是任意兩個相等的數據，排序前後的相對位置不發生改變，這句話是什麼意思呢？比如說我們要把學生的名字，學生的名單來做排序的時候，我們有兩個同學都叫小明，我們不妨假設一個是小明1，一個小明2，那麼在排序之前，這兩個小明有一個相對位置，就是小明1是出現在小明2前面的，那在完成排序以後呢，因為他們兩個重名，所以這兩個名字應該會被排在一起，排在一起的時候，如果小明1仍然排在小明2的前面，如果一個排序演算法能夠保證說相對順序不改變，那我們說這種排序演算法是穩定的，否則呢，就叫做不穩定的，最後我們要說明非常重要的一點，就是為什麼在說到排序這個問題的時候，我們要介紹這麼多種演算法，那是因為每一種演算法都有它必須存在的理由，沒有任何一個演算法，是在任何情況下，都是最快最好的，每一種演算法，都是當你的數據具有某種特徵的時候，這種演算法，可能是最好的，當你的數據換了一種特徵的時候，這個原來好的演算法就不好了，另外一種演算法可能是最好的，這也就是說為什麼一種演算法能被寫進教科書，它一定有它存在的非常重要的理由。