Data Structure_Sort Algorithm

排序算法

Tool implement

//generate a array of n elements, range [rangL, rangeR]
    int *generateRandomArray(int n, int rangL, int rangeR) {
        assert(rangeR >= rangL);
        int *arr = new int[n];
        srand(time(NULL));
        for (int i = 0; i < n; i++) {
            arr[i] = rand() % (rangeR - rangL + 1) + rangL;
        }
        return arr;
    }

    template<typename T>
    void showArray(T arr[], int n) {
        for (int i = 0; i < n; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }
           

生成随機的n個數量的數組，輸出數組每一個元素的内容。測試排序算法使用的标準就是運作時間和排序的正确性，是以需要一個驗證正确性和計算排序時間的：

template<typename T>
    void testSort( string sortName, void(*sort)(T[], int), T arr[], int n){
        clock_t startTime = clock();
        sort(arr, n);
        clock_t endTime = clock();
        if (isSorted(arr, n)){
            cout << sortName << ": " << double(endTime - startTime)/CLOCKS_PER_SEC << "s" << endl;
        } else
            cout << "sort function is wrong!" << endl;
        return;
    }

    template<typename T>
    bool isSorted(T arr[], int n){
        for (int i = 0; i < n-1; i++){
            if (arr[i] > arr[i+1])
                return false;
        }
        return true;
    }
           

的排序

這種算法應該是屬于比較慢的算法了，編碼簡單，易于實作，是一些簡單場景的選擇。在一些特殊情況下，簡單的排序算法更容易實作且更有效。從簡單的算法演變到複雜的算法，循序漸進，作為子過程改進跟複雜的算法。

選擇排序——SelectionSort

選擇排序比較簡單，如果是最簡單的一個了。基本思想就是周遊每一個位置，選擇這個位置之後最小的元素與目前元素對換：

比如這個數組，一開始是第一個位置，然後選擇2到n個位置最小的元素，找到就是1了，然後和第一個元素互換：

也就是挨個挨個位置找到最小的元素。很明顯，毫無疑問，他的複雜度肯定就是

。

代碼實作：

template<typename T>
void SelectionSort(T arr[], int n) {
    for (int i = 0; i < n; i++) {
        int minIndex = i;
        for (int j = i; j < n; j++) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        swap(arr[minIndex], arr[i]);
    }
}

           

由于是模闆類，是以還可以用來排序string，運算符重載還可以用來對類排序。

定義一個學生類用于排序：

struct student{
        string name;
        float score;

        bool operator<(const student &otherStudent){
            return score < otherStudent.score;
        }

        friend ostream& operator<<(ostream &os, const student &otherStudent){
            os << "Student: " << otherStudent.name << " " << otherStudent.score << endl;
            return os;
        }
    };

           

插入排序——InsertionSort

插入排序也是一個

的排序算法。

一開始先比較了第一和第二位，如果順序是正确的，那麼就不換，繼續比較第三第四位，2比8小交換位置，比6有小交換位置，直到适合它的位置即可。

以此類推最後排序完成。如果要判斷的元素是剛剛好大于之前的元素的時候，那麼就不用比較了，是以插入排序操作是可以比選擇排序要快的，來看一些代碼實作：

template<typename T>
void InsertionSort(T arr[], int n){
    for (int i = 1; i < n; i ++){
        for (int j = i; j > 0; j --){
            if (arr[j] < arr[j-1]){
                swap(arr[j], arr[j-1]);
            } else
                break;
        }
    }
}
           

然而事與願違，時間反而多了一倍。這是和插入排序的一些交換操作引起的，插入排序雖然可以終止某些交換操作，但是在周遊的時候同時也做交換了，每一次交換就有三次指派的操作，再加上索引數組這些時間，就遠大于選擇排序了。為了減少這種交換的次數，我們改進一下：

一開始隻做比較不做交換，複制一份6出來，比較6和8，如果8是大于6的，就證明這個8是不應該在目前位置的，是以8覆寫6，然後6往前移動，按照正常套路進行比較下去。

template<typename T>
void InsertionSort_version2(T arr[], int n){
    for (int i = 1; i < n; i ++){
        T temp = arr[i];
        int j = 0;
        for (j = i; j > 0 && arr[j-1] > temp; j --){
            arr[j] = arr[j-1];
        }
        arr[j] = temp;
    }
           

這次就正常了：

對于插入排序還有一個比較好的性質，如果目前數組是一個基本有序的數組那麼基本插入排序每一次就基本被終止了，那麼就會很快。

在小資料量的情況下，兩者的差别都不會特别大，但是當資料量變大的時候，兩者的差别就會越來越大了。

歸并排序——MergeSort

步驟其實很簡單，首先進行劃分，當劃分到一定的細度的時候就不能劃分了，然後就進行歸并

然後往上歸并即可。劃分的時間是

，歸并的時候就是

了，是以一共就是

級别了。那麼主要的困難就是歸并的時候了：

如何把如上的兩個歸并的數組合并？

需要用到三個索引，兩個紅色的索引代表的就是已經排好序的兩個數組，藍色的指向了一個臨時空間：

一開始2和1比較，1比較小，那麼1就填在了藍色索引的位置，藍色索引加一，因為1填進去了，是以右邊的紅色索引加一，以此類推，到最後哪邊沒有完就直接整塊扔進去就好了。代碼實作：

template<typename T>
void __merge(T arr[], int l, int mid, int r) {
    T *temp = new T[r-l+1];
    for (int i = l; i <= r; i++) {
        temp[i - l] = arr[i];
    }
    int i = l, j = mid + 1;
    for (int k = l; k <= r; k++) {
        if (i > mid) {
            arr[k] = temp[j - l];
            j++;
        } else if (j > r) {
            arr[k] = temp[i - l];
            i++;
        } else if (temp[i - l] < temp[j - l]) {
            arr[k] = temp[i - l];
            i++;
        } else {
            arr[k] = temp[j - l];
            j++;
        }
    }
    delete[] temp;
}

template<typename T>
void __mergeSort(T arr, int l, int r) {
    if (l >= r) {
        return;
    } else {
        int mid = (l + r) / 2;
        __mergeSort(arr, l, mid);
        __mergeSort(arr, mid + 1, r);
        __merge(arr, l, mid, r);
    }
}

template<typename T>
void MergeSort(T arr[], int n) {
    __mergeSort(arr, 0, n - 1);
}
           

最主要的就是Merge函數了。對于temp數組是存在有偏移的，是以是需要減去一個偏移量，因為到最後l和r不一定是從0開始的。

可以看到對于一萬個數組排序的時間很快，其實歸并排序就是典型的用空間換時間的，每一次遞歸就開了一個空間，每一次遞歸的時候還有一個緩沖數組，是以使用的空間複雜度比一般的排序算法要大。

如果是十萬個資料那麼差距就更加大了：

但是對于這個代碼來說，還是可以優化的，因為在歸并的時候，我們是無論兩邊的數組是個什麼情況都進行一個歸并，但是事實上這樣是不嚴謹的，因為事實上如果一邊的最大的元素小于另一邊的最小的元素，就可以說完全大于了，是以加上判斷：

void __mergeSort(T arr, int l, int r) {
    if (l >= r) {
        return;
    } else {
        int mid = (l + r) / 2;
        __mergeSort(arr, l, mid);
        __mergeSort(arr, mid + 1, r);
        if (arr[mid] > arr[mid + 1]) {
            __merge(arr, l, mid, r);
        }
    }
}
           

加上一個判斷即可。

自底向上的歸并排序——upMergeSort

其實思想都是一樣的，都是分而治之的思想，先兩個兩個的排，然後四個四個的排，然後八個八個的排，以此類推：

先兩個兩個的排，然後四個四個：

之後8個一起，這個過程其實不需要遞歸，直接疊代實作即可。

template<typename T>
void upMergeSort(T arr[], int n){
    for (int sz = 1; sz <= n; sz = sz + sz){
        for (int i = 0; i + sz < n; i += sz + sz){
            __merge(arr, i, i+sz-1, min(i+sz+sz-1, n-1));
        }
    }
}
           

可以看到代碼量很少。

時間差不多。

快速排序——QuickSort

歸并排序和快速排序不同的就是，歸并排序是無論什麼情況直接就一分為二兩部分，快速排序也是分成兩部分，但是快速排序是先找到對應的一個元素的位置，然後直接找到這個元素應該在的位置：

比如4，找到這個元素所在的位置。這個時候這個數組就有一個性質了，左邊的元素一定比4小，右邊的一定比4要大。那麼接下來的主要操作就是在于如何找到4這個元素對應的位置。

v是要分割的數字，e就是目前要判斷的數字。有兩個情況要判斷，如果是大于V的，那就簡單了，直接i++，如果是小于V，那就把i和j+1的數字進行交換即可，然後j++，最後i++即可。

最後就是這個樣子，隻需要j和l換即可。

template<typename T>
int __partition(T arr[], int l, int r) {
    T v = arr[l];
    int j = l;
    for (int i = l + 1; i <= r; i++) {
        if (arr[i] < v) {
            swap(arr[j + 1], arr[i]);
            j++;
        }
    }
    swap(arr[j], arr[l]);
    return j;
}

template<typename T>
void __quickSort(T arr[], int l, int r) {
    if (l >= r) {
        return;
    }
    int p = __partition(arr, l, r);
    __quickSort(arr, l, p - 1);
    __quickSort(arr, p + 1, r);
}

template<typename T>
void QuickSort(T arr[], int n) {
    __quickSort(arr, 0, n - 1);
}

           

.可以看到效果還是有的。快速排序之是以是

是因為每一次都會分成兩個，但是是不均等的兩個：

這樣，問題就來了，如果這個數組是一個基本有序的數組，那麼大概就是這樣了：

退化成了

的問題，因為我們選擇的是第一個個元素進行排序，是以改進我們就可以随機選擇一個元素做分割，改進一下。選擇一個随機：

template<typename T>
int __partition(T arr[], int l, int r) {
    swap(arr[l], arr[rand()%(r-l+1)+l]);
    T v = arr[l];
    int j = l;
    for (int i = l + 1; i <= r; i++) {
        if (arr[i] < v) {
            swap(arr[j + 1], arr[i]);
            j++;
        }
    }
           

效果就不出了。

接下來還有一個問題，如果這個數組是一個基本有序的數組，測試一下資料：

可以看到快速排序還是慢了點。為什麼會這樣，我們考慮一下partition函數：

當擁有大量重複元素的時候問題來了：

那麼切分的時候自然又回到剛剛的情況了。

我們可以用這種方法進行改進，把大于和小于的放在兩邊，找到i和j大于V和小于V就停下，交換兩個的值。

按照如上的這一種結構就算是有大量的重複的數值也可以平均分開，達到兩邊是相同的數量。

template<typename T>
int __partition_version2(T arr[], int l, int r) {
    swap(arr[l], arr[rand() % (r - l + 1) + l]);
    T v = arr[l];
    int i = l+1, j = r;
    while (true){
        while (i <= r && arr[i] < v){
            i++;
        }
        while (j >= l+1 && arr[j] > v){
            j--;
        }
        if (i > j){
            break;
        } else{
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }
    swap(arr[l], arr[j]);
    return j;
}
           

這樣效果就好很多了。

實作帶有重複元素的數組快速排序還有一個更加經典的實作方法，就是三路排序了。

template<typename T>
int __partition_version3(T arr[], int l, int r){
    swap(arr[l], arr[rand() % (r - l + 1) + l]);
    T v = arr[l];
    int lt = l, gt = r+1, i = l+1;
    while (i < gt){
        if (arr[i] < v){
            swap(arr[i], arr[lt+1]);
            lt++;
            i++;
        } else if (arr[i] > v){
            swap(arr[i], arr[gt-1]);
            gt--;
        } else{
            i++;
        }
    }
    swap(arr[l], arr[lt]);
    return lt;
}
           

堆排序——HeapSort

堆是一種比較常用的資料結構，常用的堆有二叉堆，費波納茨堆等等。堆是一顆完全二叉樹，除了最後一層其他的每一層都是滿的，而最後一層都的子節點都是集中在了左邊。堆的實作在DataStructure裡面提到，實作很簡單。因為實作的是最大堆，出來的元素就是最大的：

using namespace std;
template<typename T>
void HeapSort_version1(T arr[], int n){
    MaxHeap<T> heap = MaxHeap<T>(n);
    for (int i = 0; i < n; ++i) {
        heap.insert(arr[i]);
    }
    for (int j = n-1; j >= 0; --j) {
        arr[j] = heap.pop();
    }
}
           

但是有一個小問題，每一次都是插入這樣效率不高，是以我們可以直接在原數組上操作

比如這就并不是一個正确的最大堆，需要用heapify轉變一下。注意到每一個葉子都是一個堆，而且是符合規定的堆，是以肯定是從最底層開始。第一個不是堆的節點一定是最後一個葉子除2。是以第一個要做的就是對第一個不是堆的節點進行排序，很明顯就是22這個元素了，對比交換，這個過程其實就是一個shitDown的過程，而我們要shitdown的元素是那5個不是堆的元素，是以對于這個數組直接做5次循環對每一個不是堆的元素進行shiftDown操作即可。

MaxHeap(item arr[], int n){
        data = new item[n+1];
        capacity = n;
        for (int i = 0; i < n; ++i) {
            data[i+1] = arr[i];
        }
        count = n;
        for (int j = count/2; j >= 1; --j) {
            shiftDown(j);
        }
    }
           

之後就可以使用heapify來代替疊代插入，其實效果差别不大。堆排序在現實中其實蠻少用到的，常用的還是對于動态資料結構的維護。

事實上這個版本的和上一個版本的差别是不大的。剛剛的一個一個元素插入堆裡面的計算複雜度是

，而使用heapify的複雜度是

。上面的排序每一次都是複制一個數組出來排序，但是如果原地在原數組上進行排序，速度是可以快很多的，這個就是原地堆排序。

目前數組是一個最大堆，那麼他的第一個元素就是v，那麼v就是最大的元素，這個最大的元素應該在最後，是以和最後一個元素調換位置；

這個時候前面的幾個元素就不是堆了。這個時候繼續對第一個元素進行shifDown操作，之後再交換即可。但是如果是這樣，那就需要調整一下索引，之前是1開始，那麼現在就要從0開始了。

自然公式就要變一下。這個時候最後一個非葉子節點的索引就是(count-1)/2。是以，第一步就是先建立一個堆，就在目前的數組上建立；建立好堆之後那麼第一個元素就是最大的元素了，這個時候最大的元素應該是在最後的，是以第二部就是要将第一個元素和最後一個元素交換，然後把最後一個元素之前的(n-1)個元素進行heapify操作，之後又交換又heapify直到前面就剩下一個元素即可。是以首先要重寫shiftDown操作，因為這個操作的索引已經是從0開始了：

template<typename T>
void __shiftDown(T arr[], int n, int i){
    while (2*i + 1 < n){
        int change = 2*i + 1;
        if (change + 1 < n && arr[change] < arr[change+1]){
            change ++;
        }
        if (arr[i] >= arr[change]){
            break;
        }
        swap(arr[i], arr[change]);
        i = change;
    }
}

           

接下了就是按照上述流程排序：

template<typename T>
void HeapSort_version2(T arr[], int n) {
    //heapify,create a max heap;
    for (int i = (n-1)/2; i >= 0; --i) {
        __shiftDown(arr, n, i);
    }
    for (int j = n-1; j > 0 ; --j) {
        swap(arr[0], arr[j]);
        __shiftDown(arr, j, 0);
    }
}
           

看看效果：

差别不是特别大，但是總的來說還是快了，因為它不需要進行額外的空間，也不需要指派的操作等等，相對會快點。

排序算法總結

平均時間複雜度	原地排序	額外空間	穩定性
Insertion Sort		是
Merge Sort		否
Quick Sort
Heap Sort

快速排序的額外空間是logn，因為遞歸的次數就是logn，而每一次遞歸就需要一個棧空間來存儲。

最後附上GitHub代碼： https://github.com/GreenArrow2017/DataStructure/tree/master/SortAlgorithm