也不知道與簡(jiǎn)單排序?qū)?yīng)的應(yīng)該叫什么, 就叫不那么簡(jiǎn)單的排序好了.

本篇博客主要學(xué)習(xí)了希爾排序、歸并排序and快速排序。

注: 這一篇和上一篇簡(jiǎn)單排序都算是學(xué)習(xí)白話算法系列的學(xué)習(xí)筆記吧

希爾排序

希爾排序是基于插入排序而來(lái), 插入排序的最好時(shí)間復(fù)雜度是O(n), 當(dāng)數(shù)組基本有序時(shí), 效率是很高的. 而希爾排序, 設(shè)定一個(gè)增量, 按增量將數(shù)組分組.

例如數(shù)組{1,2,3,4}, 增量是2, 那么數(shù)組就可以分為{1,3}, {2,4}兩組, 增量是1那就是1,2,3,4四組.

分組之后在組內(nèi)進(jìn)行插入排序, 再縮小增量重新分組再次排序, 直到增量是1(等同于正常的插入排序), 再插入排序一次, 排序完成.

void shellSort(int arr[], int n){
    
    for (int gap = n/2; gap>0; gap/=2) {
        for (int i = gap; i<n; i++) {
            if (arr[i] < arr[i - gap]) {
                int temp = arr[i];
                int j;
                // 思路與插入排序相同, 用臨時(shí)變量保存要插入的數(shù), 向數(shù)組前面查找插入的位置, 一邊查找, 一邊將前面較大的數(shù)字后移
                // 臨時(shí)變量不小于前面的某數(shù)時(shí), 說(shuō)明找到了正確的位置, 只要放在那個(gè)數(shù)后面就可以了
                for (j = i-gap; j>=0 && temp<arr[j]; j-=gap) {
                    arr[j+gap] = arr[j];
                }
                arr[j+gap] = temp;
            }
        }
    }
}

歸并排序

歸并二字就是遞歸&合并

歸并排序的關(guān)鍵在于合并有序數(shù)組, 合并兩個(gè)有序數(shù)組的方式是先比較兩數(shù)組的第一個(gè)元素, 更小的取出放入新數(shù)組, 再依次向后比較, 直到某個(gè)數(shù)組的元素取光, 把另一個(gè)數(shù)組的元素依次放入新數(shù)組既可.

//先來(lái)演示合并數(shù)組
void mergeArray(int a[], int m, int b[], int n){
    int c[m+n];
    
    int i, j, k;
    //必須初始化, 否則會(huì)有殘值
    i = j = k = 0;
    
    // 此處不能用for循環(huán), 除非只寫(xiě)第二個(gè)表達(dá)式, 否則ijk哪個(gè)做自增都不合適
    // 其中k看似合適, 但for循環(huán)最后會(huì)執(zhí)行一次第三個(gè)表達(dá)式, k會(huì)+1
    while (i < m && j < n) {
        if (a[i] < b[j]) {
            c[k++] = a[i++];
        }else{
            c[k++] = b[j++];
        }
    }
    
    while (i < m) {
        c[k++] = a[i++];
    }
    
    while (j < n) {
        c[k++] = b[j++];
    }
    
    printfArray(c, m+n);
}

下面開(kāi)始擼正式的歸并排序

// 合并有序序列
void mergearray(int arr[], int first, int last, int mid, int temp[]){
    int tempIndex = 0;
    
    int firstSequenceIndex = first;
    int secondSequeceIndex = mid + 1;
    
    // 因?yàn)檫@里用的是數(shù)組角標(biāo), 而不是長(zhǎng)度, 所以用<= 而不是<
    while (firstSequenceIndex <= mid && secondSequeceIndex <= last) {
        // 取較小值放入臨時(shí)數(shù)組
        if (arr[firstSequenceIndex] < arr[secondSequeceIndex] ) {
            temp[tempIndex++] = arr[firstSequenceIndex++];
        }else{
            temp[tempIndex++] = arr[secondSequeceIndex++];
        }
    }
    // 如果前一個(gè)序列還有值, 依次放入臨時(shí)數(shù)組
    while (firstSequenceIndex <= mid) {
        temp[tempIndex++] = arr[firstSequenceIndex++];
    }
    // 如果后一個(gè)序列還有值, 依次放入臨時(shí)數(shù)組
    while (secondSequeceIndex <= last) {
        temp[tempIndex++] = arr[secondSequeceIndex++];
    }
    // 將排好序的部分賦值給原數(shù)組
    for (int i = 0; i < tempIndex; i++) {
        arr[first++] = temp[i];
    }
    
}

// 搞清歸并排序, 主要搞清以下兩點(diǎn)
// 1. 遞歸到只有一個(gè)數(shù)時(shí), 遞歸函數(shù)開(kāi)始出棧, 一個(gè)數(shù)肯定是有序序列
// 2. 合并兩個(gè)有序序列, 可以形成新的有序序列
void mergeSort(int arr[], int first, int last, int temp[]){
    if(first < last){
        // 將數(shù)組分成兩部分
        int mid = (first + last)/2;
        // 前一半排序
        mergeSort(arr, first, mid, temp);
        // 后一半排序
        mergeSort(arr, mid+1, last, temp);
        // 合并有序序列
        mergearray(arr, first, last, mid, temp);
    }
}

快速排序

快速排序是時(shí)間復(fù)雜度O(logN*N)的排序算法中比較出名的, 面試算法常常會(huì)問(wèn), 而手寫(xiě)出來(lái)是很有難度的事情. 這里非常感謝白話經(jīng)典算法系列的作者, 講解通俗易懂.

快速排序的基本思想一句話概括就是<font color='red'>挖坑填數(shù)+分治法</font>, 下面詳細(xì)描述:

1. 先取左邊第一個(gè)數(shù)作為基準(zhǔn)數(shù)
2. 與基準(zhǔn)數(shù)比較, 比基準(zhǔn)數(shù)大的換到右邊, 小的換到左邊
3. 左右兩邊分成兩個(gè)部分, 再進(jìn)行一次前兩步的操作. 重復(fù)對(duì)左右兩邊拆分, 進(jìn)行前兩步操作, 直到只剩一個(gè)數(shù).

這樣說(shuō)還是太抽象, 舉個(gè)栗子吧

數(shù)組a = {3, 1, 4, 2, 0}

1. 取a[0]作為基準(zhǔn)數(shù), 使用新變量baseNumber存儲(chǔ)
2. 從右向左比較, 比基準(zhǔn)數(shù)小的放在基準(zhǔn)數(shù)的位置上, 數(shù)組變成{<font color='red'>0</font>, 1, 4, 2, <font color='red'>0</font>}, 此時(shí)出現(xiàn)一個(gè)坑a[4]
3. 從左往右比較, 比基準(zhǔn)數(shù)大的填入上一個(gè)坑a[4], 數(shù)組變成{0, 1, <font color='red'>4</font>, 2, <font color='red'>4</font>}, 此時(shí)的新坑是a[2]
4. 再?gòu)挠蚁蜃蟊容^, 比基準(zhǔn)數(shù)小的填入上一個(gè)坑a[2], 數(shù)組變成{0, 1, <font color='red'>2</font>, <font color='red'>2</font>, 4}, 此時(shí)的坑是a[3]
5. 再?gòu)淖笙蛴冶容^時(shí), 發(fā)現(xiàn)左右相遇了, 將baseNumber賦值給a[3], 數(shù)組變成{0, 1, 2, 3, 4}

因?yàn)閿?shù)組元素較少, 這樣就排序完成了, 但足夠大家了解挖坑填數(shù)的思路了.

有一點(diǎn)需要說(shuō)明, 為什么左右相遇了就可以把baseNumber賦值給那個(gè)元素? 因?yàn)樽笥覂蛇呄嘤鰰r(shí), 所有數(shù)字都已經(jīng)比較了一遍, 已經(jīng)做到"比基準(zhǔn)數(shù)大的都在右邊, 比基準(zhǔn)數(shù)小的都在左邊".

根據(jù)上面的分析, 可以很容易寫(xiě)出挖坑填數(shù)的代碼:

void changeArray(int arr[], int left, int right){
    int i = left;
    int j = right;
    
    // 使用變量存儲(chǔ)最左邊的數(shù)做基準(zhǔn)數(shù)
    // 基準(zhǔn)數(shù)也可不使用最左邊的, 中間和最后一個(gè)當(dāng)然都可以
    int baseNumber = arr[left];
    
    // 當(dāng)i=j時(shí)意味著數(shù)列中所有數(shù)都與基準(zhǔn)數(shù)比較過(guò)了, 故結(jié)束比較
    while (i < j) {
        
        // 從右往左比較, 找到比基準(zhǔn)數(shù)小的數(shù)的下標(biāo)
        while (arr[j] > baseNumber && i < j) {
            j--;
        }
        arr[i] = arr[j];
        
        // 從左往右比較, 找到比基準(zhǔn)數(shù)大的數(shù)的下標(biāo)
        while (arr[i] < baseNumber && i < j) {
            i++;
        }
        arr[j] = arr[i];
    }
    // 將基準(zhǔn)數(shù)賦值給a[i](也可以是a[j], 此時(shí)i=j)
    arr[i] = baseNumber;
    
}

最后baseNumber賦值,arr[i] = baseNumber,可能會(huì)有人對(duì)這句疑惑, 為何可以直接賦值, 不會(huì)少一個(gè)數(shù)嗎?

答案是不會(huì), 從上面的代碼看出, 即便while (arr[i] < baseNumber && i < j)這個(gè)循環(huán)沒(méi)有走, arr[i]的值也會(huì)賦值給arr[j], 這樣arr[i]的值必定有兩個(gè), 當(dāng)然可以直接賦值.

接下來(lái)徹底完成遞歸調(diào)用:

void quickSort(int arr[], int left, int right){
    // 遞歸的結(jié)束條件, left=right, 也就是只剩一個(gè)數(shù)的時(shí)候
    if (left < right) {
        
        int i = left;
        int j = right;
        int baseNumber = arr[left];
        
        while (i < j) {  
            while (arr[j] > baseNumber && i < j) {
                j--;
            }
            arr[i] = arr[j];
            
            while (arr[i] < baseNumber && i < j) {
                i++;
            }
            arr[j] = arr[i];
        }
        
        arr[i] = baseNumber;
        
        // 遞歸調(diào)用
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    } 
}