一種混合排序方式

一、主要思路

目前眾多排序演算法中，最快的演算法時間復雜度為 O ( n l o g n ) O(nlogn) O(nlogn) ，能否實作一種更高效的演算法呢？本文嘗試尋找一種時間復雜度至多為 O ( n l o g n ) O(nlogn) O(nlogn) 的演算法，該演算法并不是自成一套的全新演算法，而是將兩種不同的演算法取其優勢混合而成，故稱 “ 混合排序演算法 ” .

1、時間復雜度 m a x { O ( m a x a ? m i n a ) , O ( n ) } max\{O(maxa - mina),\ O(n)\} max{O(maxa?mina), O(n)} 的排序法

首先來看一種特定情形下表現優良的演算法 .對于給定陣列 a r r [ n ] arr[n] arr[n]，

1. 遍歷陣列 a r r arr arr ，獲得 a r r arr arr 中最大值 m a x a maxa maxa 與最小值 m i n a mina mina ；

2. 分配一個大小為 m a x a ? m i n a + 1 maxa - mina + 1 maxa?mina+1 的陣列 s o r t sort sort ，元素初值均置為 0 0 0 ；

3. 第二次遍歷陣列 a r r arr arr ，將當前陣列元素 a r r [ i ] arr[i] arr[i] 對應的 s o r t [ a r r [ i ] ? m i n a ] sort[arr[i] - mina] sort[arr[i]?mina] 加 1 1 1 ；

4. 遍歷陣列 s o r t sort sort ，將所有非零元素 s o r t [ i ] sort[i] sort[i] 對應的數 m i n a + i mina + i mina+i 列印，同時 s o r t [ i ] sort[i] sort[i] 減 1 1 1 .

   當 s o r t [ i ] sort[i] sort[i] 為零時，處理下一個元素 .

相應 C++ 代碼為

vector<int> newSort(vector<int> &arr){
    //步驟1
    int mina = arr[0], maxa = arr[0];
    for(int i : arr) {
        mina = mina > i ? i : mina;
        maxa = maxa < i ? i : maxa;
    }
    //步驟2，3
    vector<int> sort(maxa - mina + 1);
    for(int i : arr) 
        sort[i - mina]++;
    //步驟4
    vector<int> res(arr.size());
    int index = 0;
    for(int i = 0; i < maxa - mina + 1; i++){
        if(sort[i]) {
            res[index++] = mina + i;
            sort[i--]--;
        }
    }
    return res;
}

通常情況下 m a x a ? m i n a + 1 > n maxa - mina + 1 > n maxa?mina+1>n ，但當 a r r arr arr 中大多數元素相同時，有 m a x a ? m i n a + 1 < n maxa - mina + 1 < n maxa?mina+1<n ，所以該演算法對應的時間復雜度為 m a x { O ( m a x a ? m i n a ) , O ( n ) } max\{O(maxa - mina),\ O(n)\} max{O(maxa?mina), O(n)} ，空間復雜度為 O ( m a x a ? m i n a ) O(maxa - mina) O(maxa?mina) . 這種演算法適合于資料分布集中型的陣列，資料越集中于某一區間， m a x a ? m i n a + 1 maxa - mina + 1 maxa?mina+1 的值越小，時間復雜度也就越趨近 O ( n ) O(n) O(n) .

目前其他演算法 ( 除去希爾排序 ) ，最快的是堆排序、快速排序與歸并排序，時間復雜度均為 O ( n l o g n ) O(nlogn) O(nlogn) ，空間復雜度分別為 O ( 1 ) , O ( l o g n ) , O ( n ) O(1),\ O(logn),\ O(n) O(1), O(logn), O(n) . 由于希爾排序的最優時間復雜度仍在證明中，本文暫不做考慮 .

當 m a x a ? m i n a < n l o g n maxa - mina < nlogn maxa?mina<nlogn 時，本演算法時間復雜度優于歸并/快速排序演算法；但當 m a x a ? m i n a > n l o g n maxa - mina >nlogn maxa?mina>nlogn 時，歸并/快速排序更優 . 若將兩者結合，是否可以得到一個時間復雜度始終不超過 O ( n l o g n ) O(nlogn) O(nlogn) 的演算法呢？

2、混合排序方法

綜上所述，可以嘗試一種兼具兩者性能的混合型排序演算法：

對于給定陣列 a r r [ n ] arr[n] arr[n]，

1. 遍歷陣列 a r r arr arr ，獲得 a r r arr arr 中最大值 m a x a maxa maxa 與最小值 m i n a mina mina ；

2. 比較 m a x a ? m i n a maxa - mina maxa?mina 與 n l o g n nlogn nlogn 大小，

   當 m a x a ? m i n a < n l o g n maxa - mina < nlogn maxa?mina<nlogn 時，轉到3 ；

   當 m a x a ? m i n a > n l o g n maxa - mina >nlogn maxa?mina>nlogn 時，轉到4 .

3. 使用 n e w S o r t ( ) newSort() newSort() 進行排序；

4. 使用歸并/快速/堆排序演算法排序 .

混合排序演算法 C++ 代碼 ( 這里步驟4以快速排序為例)

//稍加改動newSort()
vector<int> newSort(vector<int> &arr, int mina, int maxa){  
    vector<int> sort(maxa - mina + 1);
    for(int i : arr) 
        sort[i - mina]++;
    
    vector<int> res(arr.size());
    int index = 0;
    for(int i = 0; i < maxa - mina + 1; i++){
        if(sort[i]) {
            res[index++] = mina + i;
            sort[i--]--;
        }
    }
    return res;
}

//快速排序
//定義一個快排的劃分函式part()，即一趟排序程序，將陣列分為左右兩部分，左邊所有元素小于p，右邊元素全部大于等于p
int part(vector<int> &arr, int low, int high){
    int p = arr[low];
    while(low < high) {
        while(low < high && arr[high] >= p) high--;
        arr[low] = arr[high];
        while(low < high && arr[low] <= p) low++;
        arr[high] = arr[low];
    }
    arr[low] = p;
    return low;
}

vector<int> quickSort(vector<int> &arr, int low, int high){
    if(low < high) {
        int pos = part(arr, low, high);//劃分
        quickSort(arr, low, pos - 1);
        quickSort(arr, pos + 1, high);
    }
    return arr;
}

//混合排序
vector<int> mixSort(vector<int> &arr){
    //步驟1
    int mina = arr[0], maxa = arr[0];
    int n = arr.size();
    for(int i : arr) {
        mina = mina > i ? i : mina;
        maxa = maxa < i ? i : maxa;
    }
    //步驟2,3,4,這里取log以2為底；
    if(maxa - mina + 1 < n * log(n) / log(2)) return newSort(arr, mina, maxa);
    return quickSort(arr, 0, n - 1);//快排
}

//測驗用例
int main(){
    vector<int> a = {6, 9, 4, 2, 8, 6, 7, 3, 2, 5, 1};
    a = mixSort(a);
    for(int i : a) cout << i << ' ';
    return 0;
}

演算法時間復雜度 m i n { O ( n l o g n ) , m a x { O ( m a x a ? m i n a ) , O ( n ) } } min\{O(nlogn),\ max\{O(maxa-mina),\ O(n)\}\} min{O(nlogn), max{O(maxa?mina), O(n)}} ，空間復雜度為 O ( l o g n ) o r O ( m a x a ? m i n a ) O(logn)\ or\ O(maxa-mina) O(logn) or O(maxa?mina) .

二、演算法適用場合

本演算法適用于使 m a x a ? m i n a maxa - mina maxa?mina 盡可能小的資料集，即資料分布集中于某個區間的資料集， e g : { 1 , 5 , 3 , 2 , 4 } eg: \{1,5,3,2,4\} eg:{1,5,3,2,4} , { 1 , 3 , 3 , 4 , 3 , 3 , 5 } \ \{1,3,3,4,3,3,5\} {1,3,3,4,3,3,5}，并且單位區間內資料越密集，本演算法性能越優良 .

Y J Y F e b . 2 0 t h , 2021 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ YJY\ \ \ \ \ \ \ \ \ \\\ \\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Feb.\ 20^{th}\ ,\ 2021 YJY Feb. 20th , 2021