排序算法的原理及其分類

排序算法的原理及其特性

• 排序的分類
• • 根據穩定性分類
  • 根據時間複雜度分類
  • 常見的排序算法的思想：
  • • 冒泡排序
    • 選擇排序
    • 插入排序
    • 快速排序
    • 歸并排序
    • 基數排序
    • 希爾排序
    • 堆排序
  • 其他排序算法：
  • • 計數排序
    • 桶排序

排序的分類

根據穩定性分類

  排序算法可以分為穩定性排序算法和非穩定性排序算法。它們的定義如下：

• 穩定排序：如果 a 原本在 b 的前面，且 a == b；排序後， a 仍然在 b 的前面，則為穩定排序。
• 非穩定排序：如果 a 原本在 b 的前面，且 a == b；排序後， a 可能不在 b 的前面，則為非穩定排序。

其分類如下：

• 穩定性排序：冒泡排序，插入排序、歸并排序、基數排序
• 不穩定性排序：選擇排序、快速排序、希爾排序、堆排序

穩定性的意義

  當排序的内容是一個複雜對象的多個數字屬性，且其原本的初始順序存在意義，那麼我們需要在二次排序的基礎上保持原有排序的意義，才需要使用到穩定性的算法，例如：要排序的内容是一組原本按照價格高低排序的對象，如今需要按照銷量高低排序，使用穩定性算法，可以使得相同銷量的對象依舊保持着價格高低的排序展現，隻有銷量不同的才會重新排序。

根據時間複雜度分類

O ( n 2 ) {\rm{O}}({n^2}) O(n2)：冒泡排序、選擇排序、插入排序。

O ( n log ⁡ 2 n ) {\rm{O}}({\rm{n}}{\log _2}n) O(nlog2​n)：快速排序、希爾排序、歸并排序和堆排序。

O ( n ) {\rm{O}}({\rm{n}}) O(n)：計數排序，桶排序，基數排序

常見的排序算法的思想：

冒泡排序

  冒泡排序是相鄰元素之間的比較和交換，兩重循環 O ( n 2 ) {\rm{O}}({n^2}) O(n2)；由于如果兩個相鄰元素相等，是不會交換的，是以這是一種穩定的排序方法。

選擇排序

  每個元素都與第一個元素相比，産生交換，兩重循環 O ( n 2 ) {\rm{O}}({n^2}) O(n2)；舉例：5，8，5，2，9,其中2會與5交換，那麼原序列中兩個5的順序就被破壞了，是以不是穩定的排序算法。

插入排序

  插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。剛開始這個小序列隻包含第一個元素，事件複雜度 O ( n 2 ) {\rm{O}}({n^2}) O(n2)。比較是從這個小序列的末尾開始的。想要插入的元素和小序列的最大者開始比起，如果比它大則直接插入在其後面，否則一直往前找它該插入的位置。如果遇見了一個和插入元素相等的，則把插入元素放在這個相等元素的後面，是以相等元素間的順序沒有改變。

快速排序

  快速排序有兩個方向，右邊的j下标一直往左走，當a[j] >= a[center_index]（其中center_index是中樞元素的數組下标，一般取為數組第0個元素），如果j走不動了，将j的值賦給位置i。左邊的i下标一直往右走，當a[i] <= a[center_index]；如果i走不動了，将i的值賦給位置j。重複上面的過程，直到i>j。 交換a[j]和a[center_index]，完成一趟快速排序。在中樞元素和a[j]交換的時候，很有可能把前面的元素的穩定性打亂。

歸并排序

  歸并排序是把排序遞歸地分成短序列，遞歸出口是短序列隻有1個元素(認為直接有序)或者2個序列(1次比較和交換),然後把各個有序的段序列合并成一個有序的長序列，不斷合并直到原序列全部排好序。歸并排序是穩定的排序算法，下面代碼中temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];這行代碼可以保證當左右兩部分的值相等的時候，先複制左邊的值，這樣可以保證值相等的時候兩個元素的相對位置不變。

public static void mergeSort(int[] arr) {
    sort(arr, 0, arr.length - 1);
}

public static void sort(int[] arr, int L, int R) {
    if(L == R) {
        return;
    }
    int mid = L + ((R - L) >> 1);
    sort(arr, L, mid);
    sort(arr, mid + 1, R);
    merge(arr, L, mid, R);
}

public static void merge(int[] arr, int L, int mid, int R) {
    int[] temp = new int[R - L + 1];
    int i = 0;
    int p1 = L;
    int p2 = mid + 1;
    // 比較左右兩部分的元素，哪個小，把那個元素填入temp中
    while(p1 <= mid && p2 <= R) {
        temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }


    // 上面的循環退出後，把剩餘的元素依次填入到temp中
    // 以下兩個while隻有一個會執行
    while(p1 <= mid) {
        temp[i++] = arr[p1++];
    }
    while(p2 <= R) {
        temp[i++] = arr[p2++];
    }
    // 把最終的排序的結果複制給原數組
    for(i = 0; i < temp.length; i++) {
        arr[L + i] = temp[i];
    }
}
           

基數排序

  基數排序是按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序。最後的次序就是高優先級高的在前，高優先級相同的低優先級高的在前。基數排序基于分别排序，分别收集，是以其是穩定的排序算法。

   題目：通過基數排序對數組{53, 3, 542, 748, 14, 214, 154, 63, 616}，寫出代碼。

  基本思想：将整數按位數切割成不同的數字，然後按每個位數分别比較。具體做法是：将所有待比較數值統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後, 數列就變成一個有序序列。如下圖所示：

代碼：

/**
 * 基數排序：C++
 */

#include<iostream>
using namespace std;

/*
 * 擷取數組a中最大值
 */
int getMax(int a[], int n)
{
    int i, max;

    max = a[0];
    for (i = 1; i < n; i++)
        if (a[i] > max)
            max = a[i];
    return max;
}

/*
 * 對數組按照"某個位數"進行排序(桶排序)
 * 例如，對于數組a={50, 3, 542, 745, 2014, 154, 63, 616}；
 *    (01) 當exp=1表示按照"個位"對數組a進行排序
 *    (02) 當exp=10表示按照"十位"對數組a進行排序
 *    (03) 當exp=100表示按照"百位"對數組a進行排序
 *    ...
 */
void countSort(int a[], int n, int exp)
{
    int output[n];             // 存儲"被排序資料"的臨時數組
    int i, buckets[10] = {0};

    // 将資料出現的次數存儲在buckets[]中
    for (i = 0; i < n; i++)
        buckets[ (a[i]/exp)%10 ]++;

    // 更改buckets[i]。目的是讓更改後的buckets[i]的值，是該資料在output[]中的位置。
    for (i = 1; i < 10; i++)
        buckets[i] += buckets[i - 1];

    // 将資料存儲到臨時數組output[]中
    for (i = n - 1; i >= 0; i--)
    {
        output[buckets[ (a[i]/exp)%10 ] - 1] = a[i];
        buckets[ (a[i]/exp)%10 ]--;
    }

    // 将排序好的資料指派給a[]
    for (i = 0; i < n; i++)
        a[i] = output[i];
}

/*
 * 基數排序
 *
 * 參數說明：
 *     a -- 數組
 *     n -- 數組長度
 */
void radixSort(int a[], int n)
{
    int exp;    // 指數。當對數組按個位進行排序時，exp=1；按十位進行排序時，exp=10；...
    int max = getMax(a, n);    // 數組a中的最大值

    // 從個位開始，對數組a按"指數"進行排序
    for (exp = 1; max/exp > 0; exp *= 10)
        countSort(a, n, exp);
}

int main()
{
    int i;
    int a[] = {53, 3, 542, 748, 14, 214, 154, 63, 616};
    int ilen = (sizeof(a)) / (sizeof(a[0]));

    radixSort(a, ilen);    // 基數排序
    
    cout << "after  sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    return 0;
}
           

希爾排序

  希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，是以插入排序的元素個數很少，速度很快；當元素基本有序了，步長很小，插入排序對于有序的序列效率很高。是以，希爾排序的時間複雜度會比 O ( n 2 ) {\rm{O}}({n^2}) O(n2)好一些。由于多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最後其穩定性就會被打亂，是以shell排序是不穩定的。

代碼：

void shellSort(int arr[],int length) {
   int gap;//間距or增量
   for (gap = length/2; gap>0; gap/=2) { //gap->1 共分幾次
       for (int i=gap; i<length; i++) {//從gap個元素開始，直接插入排序
           if (arr[i] < arr[i-gap]) {
               int tmp = arr[i];
               int k = i-gap;
               while (k>=0 && arr[k] > tmp) {
                   arr[k+gap] = arr[k];
                   k-=gap;
               }
               arr[k+gap] = tmp;
           }
       }
   }
}

           

堆排序

  我們知道堆的結構是節點i的孩子為2i和2i+1節點，大頂堆要求父節點大于等于其2個子節點，小頂堆要求父節點小于等于其2個子節點。

   在一個長為n的序列，堆排序的過程：從第n/2開始和其子節點共3個值選擇最大(大頂堆)或者最小(小頂堆),這3個元素之間的選擇當然不會破壞穩定性。但當為n/2-1, n/2-2, …1這些個父節點選擇元素時，就會破壞穩定性。有可能第n/2個父節點交換把後面一個元素交換過去了，而第n/2-1個父節點把後面一個相同的元素沒有交換，那麼這2個相同的元素之間的穩定性就被破壞了。是以，堆排序不是穩定的排序算法。

  流程總結如下：

• 首先将無序數組構造成一個大根堆，即：從第i=1個結點開始，将其與其父結點進行比較，如果插入的數比父結點大，則與父結點交換，否則一直向上交換，直到小于等于父結點，或者來到了頂端。當第i插入的結點找到合适位置後，采用上面的方法重複插入第i=2…n個結點。
• 固定一個最大值，将剩餘的數重新構造成一個大根堆，重複這樣的過程。即：将最大數落到堆的末尾進行固定，後面隻需要對頂端的資料進行操作即可，拿頂端的數與其左右孩子較大的數進行比較，如果頂端的數大于其左右孩子較大的數，則停止，如果頂端的數小于其左右孩子較大的數，則交換，然後繼續與下面的孩子進行比較。

實作代碼：

//堆排序
    public static void heapSort(int[] arr) {
        //構造大根堆
        heapInsert(arr);
        int size = arr.length;
        while (size > 1) {
            //固定最大值
            swap(arr, 0, size - 1);
            size--;
            //構造大根堆
            heapify(arr, 0, size);
 
        }
 
    }
 
    //構造大根堆（通過新插入的數上升）
    public static void heapInsert(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            //目前插入的索引
            int currentIndex = i;
            //父結點索引
            int fatherIndex = (currentIndex - 1) / 2;
            //如果目前插入的值大于其父結點的值,則交換值，并且将索引指向父結點
            //然後繼續和上面的父結點值比較，直到不大于父結點，則退出循環
            while (arr[currentIndex] > arr[fatherIndex]) {
                //交換目前結點與父結點的值
                swap(arr, currentIndex, fatherIndex);
                //将目前索引指向父索引
                currentIndex = fatherIndex;
                //重新計算目前索引的父索引
                fatherIndex = (currentIndex - 1) / 2;
            }
        }
    }
    //将剩餘的數構造成大根堆（通過頂端的數下降）
    public static void heapify(int[] arr, int index, int size) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        while (left < size) {
            int largestIndex;
            //判斷孩子中較大的值的索引（要確定右孩子在size範圍之内）
            if (arr[left] < arr[right] && right < size) {
                largestIndex = right;
            } else {
                largestIndex = left;
            }
            //比較父結點的值與孩子中較大的值，并确定最大值的索引
            if (arr[index] > arr[largestIndex]) {
                largestIndex = index;
            }
            //如果父結點索引是最大值的索引，那已經是大根堆了，則退出循環
            if (index == largestIndex) {
                break;
            }
            //父結點不是最大值，與孩子中較大的值交換
            swap(arr, largestIndex, index);
            //将索引指向孩子中較大的值的索引
            index = largestIndex;
            //重新計算交換之後的孩子的索引
            left = 2 * index + 1;
            right = 2 * index + 2;
        }
 
    }
    //交換數組中兩個元素的值
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
           

其他排序算法：

計數排序

1.适用範圍：

  這個算法在n個輸入元素中每一個都是0到k的範圍的整數，其中k也是整數。當k = O(n)時，排序的時間複雜度為Θ(n)。它的性質也就決定了它的運用範圍比較窄，但是對于一個待排序的有負數的數組，我們可以将整個數組的整體加上一個整數，使得整個數組的最小值為0，然後就可以使用這個排序算法了。而且這個算法是穩定的。

2.基本思想

  對一個待排序的元素x，我們可以确定小于等于x的個數i，根據這個個數i，我們就可以把x放到索引i處。那麼如何确定小于等于x的個數i呢？

  我們可以專門開辟一個數組c[]，然後周遊數組，确定數組a中每個元素中出現的頻率，然後就可以确定對于a中每個元素x，小于等于這個元素的個數。然後就可以把元素x放到對應位置了。當然元素x的大小是可能重複的，這樣就需要我們對數組c的值通路之後減1，保證和x一樣大的元素能放在其前面。

3.運作過程

i . 對于數組A，我們首先統計每個值的個數，将A的值作為C元素索引，值的個數作為C數組的值。比如對于數組A中的元素2，在數組A中出現了2次，是以c[2] = 2，而元素5出現了1次，是以c[5] = 1。

ii . 至此為止，數組C中已經統計了各個元素的出現次數，那麼我們就可以根據各個元素的出現次數，累加出比該元素小的元素個數，更新到數組C中。比如a圖中，C[0]=2表示出現0的次數為2，C[1]=0表示出現1的次數為0，那麼小于等于1的元素個數為C[0]+C[1]=2，我們把C[1]更新為2，同理C[2]=2表示出現2的次數為2，那麼小于等于2的元素個數為C[1]+C[2]=4，繼續把C[2]更新為4，以此類推…

iii .到這裡，我們得到了存儲**小于等于元素的個數 **的數組C。現在我們開始從尾部到頭部周遊數組A，比如首先我們看A[7] = 3，然後查找C[3]，發現C[3] = 7，說明有7個元素小于等于3。我們首先需要做一步C[3] = C[3] - 1，因為這裡雖然有7個元素小于等于3，但是B的索引是從0開始的，而且這樣減一可以保證下次再找到一個3，可以放在這個3的前面。然後B[C[3]] = 3，就把第一個3放到了對的位置。後面以此類推，直到周遊完數組B。

iv. 截至到這，我們就獲得了一個有序的數組B。

4.代碼實作

   我們使用Java來實作這個算法：

public static void countingSort(int[] a, int[] b, int k){
        int[] c = new int[k+1];//存放0~k
        for(int i = 0; i<a.length; i++)
            c[a[i]] += 1;
        for(int i = 1; i<=k; i++)
            c[i] += c[i-1];
        for(int i = a.length-1; i >= 0; i--){
            c[a[i]] --;
            b[c[a[i]]] = a[i];
        }
    }
           

簡簡單單幾行代碼就實作了計數排序，其中參數a數組表示待排序的數組，b數組表示排序之後的存儲數組，k表示a數組中最大的值。

桶排序