1.常用排序演算法介紹

一個排序演算法的好壞需要針對它在某個場景下的時間復雜度和空間復雜度來進行判斷、并且排序都需要求其穩定性,比如排序之前a在b前面,且a=b,排序之后也要保持a在b前面、

常用排序演算法如下所示:

2.選擇排序

首先i等于0,每次i++,并從i輪詢到末尾,選擇一個最小者與第i個位置進行交換.

比如:

16,8,21,10,49

第1次遍歷整個陣列,找到最小值8,則與arr[0]進行交換:

8,16,21,10,49

第2次遍歷下標1~4的陣列,找到10,則與arr[1]進行交換:

8,10 ,21,16,49

第3次遍歷下標2~4的陣列,找到16,則與arr[2]進行交換:

8,10 , 16, 21,49

第4次遍歷下標3~4的陣列,找到21,由于交換的位置相等,則保持不變

由于第5次,起始小標等于n-1了.所以已經比較完了.則結束了.

所以代碼如下所示:

template <typename T>
void mySwap(T& a, T& b)    // 交換函式
{
    T c(a);
    a = b;
    b = c;
}


template <typename T>
void seleteSort(T arr[], int len, bool ascend = true)      // ascend為ture表示升序
{
    for (int i = 0; i < len -1; ++i) {
        int minIdx = i;
        for (int j = i+1; j < len; ++j) {
            if (ascend ? (arr[minIdx] > arr[j]) : (arr[minIdx] < arr[j])) {
                minIdx = j;
            }
        }
        if (minIdx != i) {
            mySwap(arr[i], arr[minIdx]);
        }
    }
}

測驗代碼如下所示:

    int arr[8] = {25, 22, 12, 8, 9, 11, 30 ,40};

    bubbleSort(arr, 8);
    cout<<"ascend: "<<endl;
    for (int i = 0; i < 8; ++i) {
        cout<<i<<": "<<arr[i]<<endl;
    }

    bubbleSort(arr, 8, false);
    cout<<"descend: "<<endl;
    for (int i = 0; i < 8; ++i) {
        cout<<i<<": "<<arr[i]<<endl;
    }

列印如下所示:

總結:

選擇排序是不穩定的排序演算法,例如 [3, 4, 3, 1, 5]這個陣列，第一次交換，第一個3和1交換位置，此時原來兩個3的相對位置發生了變化,所以無法保證值相等的元素的相對位置不變，

3.冒泡排序

重復len次冒泡,每次冒泡都是(int j=len-1; j>i; j--)從陣列末尾往前進行冒泡,如果arr[j-1]>arr[j],則將arr[j]與arr[j-1]交換,讓值小的冒泡上去.

代碼如下所示:

template < typename T >
static void bubbleSort(T arr[], int len, bool ascend = true)
{
    bool isSwap = true;

    for(int i=0; (i<len) && isSwap; i++)    // 每次冒泡時,則判斷上次是否發生過交換,如果交換過,那說明還不是個有序的表
    {
        isSwap = false;     // 每次冒泡的時候復位 “交換標志位”

        for(int j=len-1; j>i; j--)
        {
            if( ascend ? ( arr[j-1] > arr[j] ) : (arr[j-1] < arr[j] ) ) // 如果是升序,arr[j-1] > arr[j],則將arr[j]從末尾冒泡冒上去
            {
                mySwap(arr[j], arr[j-1]);
                isSwap = true;     // “交換標志位” 設定為true
            }
        }
    }
}

PS: 由于mySwap()函式和測驗代碼已經寫過了,后面就不再重復寫了，

總結:

冒泡排序是穩定的排序演算法,因為每次都是冒泡相鄰比較,比如升序,如果后者>=前者,是不會進行交換

4.插入排序

將一個陣列分為兩個部分,左邊是排序好的,右邊是未排序的.

然后每次提取一個右邊的資料出來,然后輪詢左邊(排序好的),如果找到合適的位置(前者小于它且后者大于它),則插入進去.如果未找到,則插入在左邊排序好的末尾位置.

比如16,8,21,10,49,由于左邊默認會有一個數值(一個數值無需判斷比較),所以無需判斷arr[0]:

16 | 8,21,10,49 ( |左邊是排序好的,右邊是等待排序的 )

第1次,獲取arr[1],由于8小于16,插入在16前面,所以插入后:

8,16 | 21,10,49

第2次,獲取arr[2],向前輪詢,由于21>16,所以停止向前遍歷, 并且位置沒改變過,所以無需操作:

8,16,21 | 10,49

第3次,獲取arr[3], 向前輪詢,由于10<21,則21向后挪位,再繼續向前輪詢,由于10<16,則16向后挪位,最后10>=8,則插入在8后面:

8, 10,16,21 | 49

第4次,獲取arr[4],由于49>21,所以停止向前遍歷, 并且位置沒改變過,所以無需操作最終為:

8, 10,16,21 ,49

代碼如下所示:

template < typename T >
static void insertSort(T arr[], int len, bool ascend = true)
{
    for(int i=1; i<len; i++) // 回圈取出右邊未排序的
    {
        int k = i;
        T temp = arr[i];		// 把值取出來,后面會進行挪位操作,會覆寫掉arr[i]原來的內容

        // 如果ascend為true,則表示升序,那么當后者大于前者時,則停止for輪詢,因為左邊是有序序列
        for(int j=i-1; (j>=0) && (ascend ? (arr[j]>temp) : (arr[j]<temp)); j--)    
        {
            arr[j+1] = arr[j];   // 進行先后挪位操作
            k = j;				 // 更新要插入的位置
        }

        if( k != i )			// 如果未進行挪位,那么k==i,則不需要重復插入
        {
            arr[k] = temp;
        }
    }
}

總結:

插入排序是穩定的排序演算法,例如 [4,3, 3, 1, 5]這個陣列，由于左邊的3是提前插入的[ 3, 4 | 3, 1, 5],而后續的3由于>=前面的3,所以插入在后面

5.希爾排序

希爾排序是插入排序的升級版.并且比插入排序快.

希爾排序則是將一個插入排序,比如初始步長間隔gap為3,那么將會分成3個小組進行插入排序,每個小組插入排序好后,再次將步長間隔gap較少一部分再次進行插入排序,直到最后步長偏移為1后,進行整個插入排序.一般gap步長都是以 len/3+1來計算.以后每次以 gap/3+1來縮小，

PS: 也可以設定gap固定增量從 n/2 開始，以后每次縮小到原來的一半，

比如下圖所示:

代碼如下所示:

template < typename T >
static void shellSort(T arr[], int len, bool ascend = true)
{
    int gap = len;

    while (gap > 1) {

        gap = gap / 3 + 1;      // 加一能夠保證gap最后一次為1.


        for(int offset = 0 ; offset < gap; ++offset) {      // 對每組進行插入排序

            for(int i=gap-offset; i<len; i+=gap) // 回圈取出右邊未排序的
            {
                int k = i;
                T temp = arr[i];		// 把值取出來,后面會進行挪位操作,會覆寫掉arr[i]原來的內容
                // 假如ascend為true,則表示升序,那么當后者大于前者時,則停止for輪詢
                for(int j=i-gap; (j>=0) && (ascend ? (arr[j]>temp) : (arr[j]<temp)); j-=gap)     
                {
                    arr[j+gap] = arr[j];   // 進行先后挪位操作
                    k = j;				 // 更新要插入的位置
                }

                if( k != i )			// 如果未進行挪位,那么k==i,則不需要重復插入
                {
                    arr[k] = temp;
                }
            }

        }
    }
}

總結:

希爾排序是不穩定的排序演算法,因為希爾排序通過分組方法,可能會將最后的值跳過中間重復的值排序到前面

6.歸并排序

歸并是將兩個或多個有序序列合并成一個新的有序序列，歸并方法有多種，一次對兩個有序記錄序列進行歸并，稱為二路歸并排序，也有三路歸并排序及多路歸并排序，本代碼是二路歸并排序.

思路如下所示:

通過遞回的方式將一個無序序列,對半拆解、直到不能拆解時,則進行兩路比較排序(歸并)到一個輔助空間陣列中,歸并完成后則將輔助陣列中內容拷貝回去,回傳上一級遞回再進行兩路比較排序(歸并)和拷貝.直到最后則整個序列歸并完成.

如下圖所示(紅色數字表示遞回拆解和歸并的先后順序):

代碼如下所示:

template < typename T >
static void merge(T arr[], int l, int mid, int r, bool ascend = true)    // 進行比較歸并
{
    int n = r - l + 1;
    T* helper = new T[n];          // 創建一個輔助空間,用來臨時存盤

    int i = 0;
    int left = l;
    int right = mid+1;
    while (left <= mid && right <= r) {
        // 如果ascend = true, 則判斷左邊如果大于右邊的,則存放右邊的
        if (ascend ? arr[left] > arr[right] : arr[left] < arr[right])
            helper[i++] = arr[right++];
        else
            helper[i++] = arr[left++];
    }

    // 將某一側剩余的存放進去
    while (left <= mid)
         helper[i++] = arr[left++];

    while (right <= r)
         helper[i++] = arr[right++];


    // 最后將排序好的替換到原陣列
    for (i = 0; i < n; ++i) {
        arr[l + i] = helper[i];
    }

    delete [] helper;

}



template < typename T >
static void mergeSort(T arr[], int l, int r, bool ascend = true)    // 遞回拆解
{
    if (l >= r)      // 不能再進行拆解了,直接退出
        return;

    int mid = (l+r)/2;

    mergeSort(arr, l, mid, ascend);
    mergeSort(arr, mid+1, r, ascend);

    merge(arr, l, mid, r, ascend);


}


template < typename T >
static void mergeSort(T arr[], int len, bool ascend = true)
{
    mergeSort(arr, 0, len-1, ascend);
}

總結:

由于歸并排序需要使用一個輔助空間,所以空間復雜度為O(n),由于都是附近的兩兩比較,所以是個穩定的演算法.

7.快速排序

快速排序是冒泡排序的一種改進，主要的演算法思想是在待排序的 n 個資料中取第一個資料作為Pivot基準值,然后采用二分的思想,把大于Pivot的資料放在右邊,把小于Pivot的資料放在左邊，最后確定Pivot基準值的中間位置.然后再次遞回進行左右磁區確定基準值,直到左右兩邊都是一個數值時,則完成排序.

如下圖所示:

步驟如下:

1) 設定兩個變數l、r，排序開始的時候：l=0，r=n-1；
2）第一個陣列值作為Pivot基準值，pivot=arr[0]；
3）然后r-- ,向左搜索,找到小于pivot后,因為arr[l]的值保存在pivot中,所以直接賦值,s[l]=s[r]
4）然后l++,向右搜索,找到大于pivot后,因為arr[r]的值保存在第2步的s[l]中,所以直接賦值,s[r]=s[l],然后r--,避免死回圈
5）重復第3、4步，直到l=r,最后將pivot值放在arr[l]中(確定了位置)
6) 然后采用“二分”的思想,以i為分界線,拆分成兩個陣列 s[0,l-1]、s[l+1,n-1]又開始排序

代碼如下所示:

template < typename T >
static void quickSort(T arr[], int left, int right,  bool ascend = true)
{
    if (left>=right)
        return;

    int l =left, r = right;

    T pivot = arr[l];           // 默認將最左邊的設定為基值
    while(l<=r) {

        while(r > l && (ascend ? arr[r] >= pivot : arr[r] <= pivot)) r--;

        arr[l] = arr[r];       // 由于arr[l]已經存放在pivot了,所以直接替換

        while(l < r && (ascend ? arr[l] <= pivot: arr[r] >= pivot)) l++;

        arr[r--] = arr[l];     // 由于arr[r]之前的值已經存在了左邊,所以直接替換

    }
    arr[l]=pivot;             // 最后找到基值的位置
    quickSort(arr, left, l-1, ascend);
    quickSort(arr, l+1, right, ascend);

}

template < typename T >
static void quickSort(T arr[], int len, bool ascend = true)
{
    quickSort(arr, 0, len-1, ascend);

}

總結:

由于快速排序是判斷Pivot基準值的排序,可能會將后者的某個相等的數放在最前面, 是個不穩定的演算法.

快速排序比歸并排序總結

由于歸并排序涉及記憶體讀寫、所以快速排序比歸并排序快、但是快速排序是個不穩定的演算法、但是如果在區域大部分有序的情況下,還是使用歸并排序快