快排和歸并排序的思想都是分治

歸并排序

整體而已妹卿，歸并排序比插入排序更優(yōu)
但近乎有序的數(shù)組，歸并排序還是比插入排序慢蔑鹦。
以下是自頂向下的歸并排序

圖片來自于https://www.cnblogs.com/nullzx/p/5968170.html

// 將arr[l...mid]和arr[mid+1...r]兩部分進(jìn)行歸并
template<typename  T>
void __merge(T arr[], int l, int mid, int r){

    //* VS不支持動(dòng)態(tài)長(zhǎng)度數(shù)組, 即不能使用 T aux[r-l+1]的方式申請(qǐng)aux的空間
    //* 使用VS的同學(xué), 請(qǐng)使用new的方式申請(qǐng)aux空間
    //* 使用new申請(qǐng)空間, 不要忘了在__merge函數(shù)的最后, delete掉申請(qǐng)的空間
    T aux[r-l+1];
    //T *aux = new T[r-l+1];   用new 和delete還是挺費(fèi)時(shí)的

    for( int i = l ; i <= r; i ++ )
        aux[i-l] = arr[i];

    // 初始化夺克，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
    int i = l, j = mid+1;
    for( int k = l ; k <= r; k ++ ){

        if( i > mid ){  // 如果左半部分元素已經(jīng)全部處理完畢
            arr[k] = aux[j-l]; j ++;
        }
        else if( j > r ){  // 如果右半部分元素已經(jīng)全部處理完畢
            arr[k] = aux[i-l]; i ++;
        }
        else if( aux[i-l] < aux[j-l] ) {  // 左半部分所指元素 < 右半部分所指元素
            arr[k] = aux[i-l]; i ++;
        }
        else{  // 左半部分所指元素 >= 右半部分所指元素
            arr[k] = aux[j-l]; j ++;
        }
    }

    //delete[] aux;
}

// 遞歸使用歸并排序,對(duì)arr[l...r]的范圍進(jìn)行排序
template<typename T>
void __mergeSort(T arr[], int l, int r){

    if( l >= r )
        return;

    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 );
}

歸并排序的優(yōu)化

經(jīng)過優(yōu)化后依然是nlogn級(jí)別的举反，但性能更優(yōu)
利用類似剪枝的技巧

// 使用優(yōu)化的歸并排序算法, 對(duì)arr[l...r]的范圍進(jìn)行排序
template<typename T>
void __mergeSort2(T arr[], int l, int r){

    // 優(yōu)化2: 對(duì)于小規(guī)模數(shù)組, 使用插入排序
    if( r - l <= 15 ){
        insertionSort(arr, l, r);
        return;
    }

    int mid = (l+r)/2;
    __mergeSort2(arr, l, mid);
    __mergeSort2(arr, mid+1, r);

    // 優(yōu)化1: 對(duì)于arr[mid] <= arr[mid+1]的情況,不進(jìn)行merge
    // 對(duì)于近乎有序的數(shù)組非常有效,但是對(duì)于一般情況,有一定的性能損失
    if( arr[mid] > arr[mid+1] )
        __merge(arr, l, mid, r);
}

只開辟一次空間的歸并排序

// 比較Merge Sort和Merge Sort 2的性能效率
// Merge Sort 2 只開辟了一次輔助空間, 之后將這個(gè)輔助空間以參數(shù)形式傳遞給完成歸并排序的其他子函數(shù)
// 可以看出 Merge Sort 2的性能優(yōu)于 Merge Sort

template<typename  T>
void __merge2(T arr[], T aux[], int l, int mid, int r){

    // 由于aux的大小和arr一樣, 所以我們也不需要處理aux索引的偏移量
    // 進(jìn)一步節(jié)省了計(jì)算量:)
    for( int i = l ; i <= r; i ++ )
        aux[i] = arr[i];

    // 初始化懊直，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
    int i = l, j = mid+1;
    for( int k = l ; k <= r; k ++ ){

        if( i > mid ){  // 如果左半部分元素已經(jīng)全部處理完畢
            arr[k] = aux[j]; j ++;
        }
        else if( j > r ){  // 如果右半部分元素已經(jīng)全部處理完畢
            arr[k] = aux[i]; i ++;
        }
        else if( aux[i] < aux[j] ) {  // 左半部分所指元素 < 右半部分所指元素
            arr[k] = aux[i]; i ++;
        }
        else{  // 左半部分所指元素 >= 右半部分所指元素
            arr[k] = aux[j]; j ++;
        }
    }

}

// 使用優(yōu)化的歸并排序算法, 對(duì)arr[l...r]的范圍進(jìn)行排序
// 其中aux為完成merge過程所需要的輔助空間
template<typename T>
void __mergeSort2(T arr[], T aux[], int l, int r){

    // 對(duì)于小規(guī)模數(shù)組, 使用插入排序
    if( r - l <= 15 ){
        insertionSort(arr, l, r);
        return;
    }

    int mid = (l+r)/2;
    __mergeSort2(arr, aux, l, mid);
    __mergeSort2(arr, aux, mid+1, r);

    // 對(duì)于arr[mid] <= arr[mid+1]的情況,不進(jìn)行merge
    // 對(duì)于近乎有序的數(shù)組非常有效,但是對(duì)于一般情況,有一定的性能損失
    if( arr[mid] > arr[mid+1] )
        __merge2(arr, aux, l, mid, r);
}


template<typename T>
void mergeSort2(T arr[], int n){

    // 在 mergeSort2中, 我們一次性申請(qǐng)aux空間,
    // 并將這個(gè)輔助空間以參數(shù)形式傳遞給完成歸并排序的各個(gè)子函數(shù)
    T *aux = new T[n];

    __mergeSort2( arr , aux, 0 , n-1 );

    delete[] aux;   // 使用C++, new出來的空間不要忘記釋放掉:)
}

自底向上的歸并排序

利用迭代

圖片來自于https://www.cnblogs.com/nullzx/p/5968170.html

// 使用自底向上的歸并排序算法
template <typename T>
void mergeSortBU(T arr[], int n){

    // Merge Sort Bottom Up 無優(yōu)化版本
//    for( int sz = 1; sz < n ; sz += sz )
//        for( int i = 0 ; i < n - sz ; i += sz+sz )
//            // 對(duì) arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 進(jìn)行歸并
//            __merge(arr, i, i+sz-1, min(i+sz+sz-1,n-1) );


    // Merge Sort Bottom Up 優(yōu)化
    // 對(duì)于小數(shù)組, 使用插入排序優(yōu)化
    for( int i = 0 ; i < n ; i += 16 )
        insertionSort(arr,i,min(i+15,n-1));

    for( int sz = 16; sz < n ; sz += sz )
        for( int i = 0 ; i < n - sz ; i += sz+sz )
            // 對(duì)于arr[mid] <= arr[mid+1]的情況,不進(jìn)行merge
            if( arr[i+sz-1] > arr[i+sz] )
                __merge(arr, i, i+sz-1, min(i+sz+sz-1,n-1) );

    // Merge Sort BU 也是一個(gè)O(nlogn)復(fù)雜度的算法火鼻，雖然只使用兩重for循環(huán)
    // 所以室囊，Merge Sort BU也可以在1秒之內(nèi)輕松處理100萬數(shù)量級(jí)的數(shù)據(jù)
    // 注意：不要輕易根據(jù)循環(huán)層數(shù)來判斷算法的復(fù)雜度，Merge Sort BU就是一個(gè)反例

}

自底向上的歸并排序因?yàn)闆]有應(yīng)用到數(shù)組隨機(jī)存取的特性魁索，所以可以用來排序鏈表融撞。

總體來說, Merge Sort BU 比 Merge Sort 快一些。但優(yōu)化后, 二者的性能差距不明顯

快速排序

在一個(gè)隨機(jī)生成的數(shù)組粗蔚，快排明顯比歸并排序快尝偎。
但基本有序的數(shù)組效率就不如歸并好。
在幾乎有序的數(shù)組（或者含大量重復(fù)鍵值）使用快排會(huì)使時(shí)間復(fù)雜度到O(n*n)。

在隨機(jī)數(shù)組中效率：二路快排>快排>三路快排
在幾乎有序數(shù)組中的效率：二路快排>快排>三路快排
在含有大量重復(fù)鍵值的數(shù)組中的效率：三路快排>二路快排>快排

// 對(duì)arr[l...r]部分進(jìn)行partition操作
// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
template <typename T>
int _partition(T arr[], int l, int r){

    // 隨機(jī)在arr[l...r]的范圍中, 選擇一個(gè)數(shù)值作為標(biāo)定點(diǎn)pivot
    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 ){
            j ++;
            swap( arr[j] , arr[i] );
        }

    swap( arr[l] , arr[j]);

    return j;
}

// 對(duì)arr[l...r]部分進(jìn)行快速排序
template <typename T>
void _quickSort(T arr[], int l, int r){

    // 對(duì)于小規(guī)模數(shù)組, 使用插入排序進(jìn)行優(yōu)化
    if( r - l <= 15 ){
        insertionSort(arr,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){

    srand(time(NULL));
    _quickSort(arr, 0, n-1);
}

隨機(jī)化快速排序

可以避免幾乎有序的數(shù)組進(jìn)行快速排序時(shí)間復(fù)雜度退化成O(n*n)

template <typename T>
int _partition(T arr[], int l, int r){

    // 隨機(jī)在arr[l...r]的范圍中, 選擇一個(gè)數(shù)值作為標(biāo)定點(diǎn)pivot
    swap( arr[l] , arr[rand()%(r-l+1)+l] );   //關(guān)鍵句

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

    swap( arr[l] , arr[j]);

    return j;
}

二路快速排序

二路快速排序?qū)写罅恐貜?fù)鍵值的數(shù)組排序可以有效避免時(shí)間復(fù)雜度退化成O(n*n)

// 雙路快速排序的partition
// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
template <typename T>
int _partition2Ways(T arr[], int l, int r){

    // 隨機(jī)在arr[l...r]的范圍中, 選擇一個(gè)數(shù)值作為標(biāo)定點(diǎn)pivot
    swap( arr[l] , arr[rand()%(r-l+1)+l] );
    T v = arr[l];

    // arr[l+1...i) <= v; arr(j...r] >= v
    int i = l+1, j = r;
    while( true ){
        // 注意這里的邊界, arr[i] < v, 不能是arr[i] <= v

        while( i <= r && arr[i] < v )
            i ++;

        // 注意這里的邊界, arr[j] > v, 不能是arr[j] >= v
        
        while( j >= l+1 && arr[j] > v )
            j --;

        /* 對(duì)于上面的兩個(gè)邊界的設(shè)定
            a. 對(duì)于arr[i]<v和arr[j]>v的方式致扯，第一次partition得到的分點(diǎn)是數(shù)組中間肤寝；
            b. 對(duì)于arr[i]<=v和arr[j]>=v的方式，第一次partition得到的分點(diǎn)是數(shù)組的倒數(shù)第二個(gè)抖僵。
            這是因?yàn)閷?duì)于連續(xù)出現(xiàn)相等的情況鲤看，a方式會(huì)交換i和j的值；而b方式則會(huì)將連續(xù)出現(xiàn)的這些值歸為其中一方耍群，使得兩棵子樹不平衡
        */
        if( i > j )
            break;

        swap( arr[i] , arr[j] );
        i ++;
        j --;
    }

    swap( arr[l] , arr[j]);

    return j;
}

// 對(duì)arr[l...r]部分進(jìn)行快速排序
template <typename T>
void _quickSort2Ways(T arr[], int l, int r){

    // 對(duì)于小規(guī)模數(shù)組, 使用插入排序進(jìn)行優(yōu)化
    if( r - l <= 15 ){
        insertionSort(arr,l,r);
        return;
    }

    // 調(diào)用雙路快速排序的partition
    int p = _partition2Ways(arr, l, r);
    _quickSort2Ways(arr, l, p-1 );
    _quickSort2Ways(arr, p+1, r);
}

template <typename T>
void quickSort2Ways(T arr[], int n){

    srand(time(NULL));
    _quickSort2Ways(arr, 0, n-1);
}

三路快速排序

三路快速排序?qū)χ貜?fù)鍵值多的數(shù)組進(jìn)行排序效率更高

template <typename T>
void __quickSort3Ways(T arr[], int l, int r){

    // 對(duì)于小規(guī)模數(shù)組, 使用插入排序進(jìn)行優(yōu)化
    if( r - l <= 15 ){
        insertionSort(arr,l,r);
        return;
    }
    //partition
    // 隨機(jī)在arr[l...r]的范圍中, 選擇一個(gè)數(shù)值作為標(biāo)定點(diǎn)pivot
    swap( arr[l], arr[rand()%(r-l+1)+l ] );

    T v = arr[l];

    int lt = l;     // arr[l+1...lt] < v
    int gt = r + 1; // arr[gt...r] > v
    int i = l+1;    // arr[lt+1...i) == v
    while( i < gt ){
        if( arr[i] < v ){
            swap( arr[i], arr[lt+1]);
            i ++;
            lt ++;
        }
        else if( arr[i] > v ){
            swap( arr[i], arr[gt-1]);
            gt --;
        }
        else{ // arr[i] == v
            i ++;
        }
    }

    swap( arr[l] , arr[lt] );

    __quickSort3Ways(arr, l, lt-1);
    __quickSort3Ways(arr, gt, r);
}

template <typename T>
void quickSort3Ways(T arr[], int n){

    srand(time(NULL));
    __quickSort3Ways( arr, 0, n-1);
}

歸并排序和快速排序的衍生問題

在求解逆序?qū)Γㄈ?义桂、2就是）可以用歸并排序的思想解決時(shí)間復(fù)雜度是nlogn

在求解一個(gè)數(shù)組的第n大的數(shù)可以用快排的思想解決，時(shí)間復(fù)雜度是n

另外關(guān)于希爾排序與nlogn排序算法的比較：
Shell Sort雖然慢于高級(jí)的排序方式, 但仍然是非常有競(jìng)爭(zhēng)力的一種排序算法
其所花費(fèi)的時(shí)間完全在可以容忍的范圍內(nèi), 遠(yuǎn)不像O(n^2)的排序算法, 在數(shù)據(jù)量較大的時(shí)候無法忍受
同時(shí), Shell Sort實(shí)現(xiàn)簡(jiǎn)單, 只使用循環(huán)的方式解決排序問題, 不需要實(shí)現(xiàn)遞歸, 不占用系統(tǒng)占空間, 也不依賴隨機(jī)數(shù)
所以, 如果算法實(shí)現(xiàn)所使用的環(huán)境不利于實(shí)現(xiàn)復(fù)雜的排序算法, 或者在項(xiàng)目工程的測(cè)試階段, 完全可以暫時(shí)使用Shell Sort來進(jìn)行排序任務(wù)