插入、冒泡、歸并、選擇、快速排序算法以及二分、三分查找算法

醉人說夢 2020-04-13

展開全文

六種排序與兩種查找算法

一排序算法（此處的排序均為升序排列）

???排序算法總的來說可以分成內(nèi)部排序和外部排序 (內(nèi)外是相對內(nèi)存而言的，對于內(nèi)部排序算法，它需要將數(shù)據(jù)全部加載入內(nèi)存，才可以進行排序，而外部排序可以將數(shù)據(jù)分批加載進入內(nèi)存，進行排序，比如：歸并排序)；
????此外排序算法還可以分為穩(wěn)定排序和非穩(wěn)定排序 (若之前A(i) == A(j) && i < j,那么在排序之后A(i)依舊在A(j)的前面，此時我們稱該排序算法是穩(wěn)定的)。

????穩(wěn)定排序有：插入排序，冒泡排序，歸并排序

????非穩(wěn)定排序有：選擇排序，快速排序, 堆排序，希爾排序

穩(wěn)定排序

1. 插入排序

插入排序在這里插入圖片描述
???正如口訣所說的那樣，我們將數(shù)組分為已排序和未排序兩部分，我們要做的就是把已排序區(qū)域后面的一個元素插入到前面已排序區(qū)域的恰當位置，這樣直到數(shù)組有序，算法結(jié)束
???對應的實現(xiàn)代碼為：

void insert_sort(int *arr, int n) {
    for (int i = 1; i < n; i++) {
        for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
            swap(arr[j], arr[j - 1]);
        }
    }
}

2. 冒泡排序

冒泡排序1 冒泡排序2
???冒泡排序同樣是將數(shù)組分成已排序和未排序兩部分，其中已排序的部分是在數(shù)組的后方 (注意區(qū)分這和插入和選擇排序是不同的)，我們要做的就是在前面沒有排序的部分中，找到最大的一個元素 (通過不斷的交換實現(xiàn))，并將該元素放在已排序部分的前面，如此循環(huán)，直至未排序部分的元素個數(shù)為0，此時算法結(jié)束
???對應的代碼為：

void bubble_sort(int *arr, int n) {
    for (int i = 1; i < n; i++) {
       int flag = 0;
        for (int j = 0; j < n - i; j++) {
            if (arr[j] <= arr[j + 1]) continue;
            swap(arr[j], arr[j + 1]);
            flag = 1;
        }
        if (!flag) break;
    }
}

???此時需要注意的是：存在這樣的一種情況，在內(nèi)部循環(huán)中并沒有進行交換，也就是說，此時數(shù)組已經(jīng)有序，不需要再排序，直接退出即可，為此我們引入標記位flag，當存在交換時flag = 1，若一次內(nèi)部循環(huán)之后，flag沒有改變，此時直接跳出循環(huán)，算法結(jié)束。

3. 歸并排序

? ???歸并排序是目前自己知曉的最快的穩(wěn)定排序，并且重要的是它的時間復雜度穩(wěn)定在O(N * log N)，歸并排序充分的利用了分治的思想，將原來的數(shù)組對半劃分，并分別對這兩個子數(shù)組進行排序，如此不斷的遞歸下去，當子數(shù)組的只有一個或兩個元素的時候，此時我們可以處理 (這也是遞歸的出口)，之后我們將數(shù)組之間兩兩之間合并 (只需要兩個指針就可實現(xiàn))，這樣我們就可以使整個數(shù)組有序了。

? ???我們將數(shù)組劃分為兩個子數(shù)組，但其實這只是一種，我們稱之為2路歸并，除此之外，我們還有多路歸并，只不過這樣排序后合并數(shù)組就會比之前麻煩

? ???歸并排序還有一個重要的性質(zhì)：那就是可以實現(xiàn)外部排序，這個算法本身實現(xiàn)的過程有關，比如對于一個32G的數(shù)據(jù)文件，顯然我們不可以全部加載進內(nèi)存，因此我們可以分8次，每次載入4G的數(shù)據(jù)進行排序，之后我們得到8個部分有序的子數(shù)組，剩下的就是不斷地讀取數(shù)組，將他們合并到一塊（我們可以將兩個排好序的4G的數(shù)據(jù)文件，各讀取一部分進入內(nèi)存，邊合并邊將數(shù)據(jù)不斷的寫到外存里面）

歸并排序1
歸并排序2
實現(xiàn)代碼如下：

void merge_sort(int *arr, int head, int tail) {
    if (tail - head <= 1) {
        if (tail - head == 1 && arr[head] > arr[tail]) {
            swap(arr[head], arr[tail]);
        }
        return ;
    }
    int mid = (head + tail) >> 1;
    merge_sort(arr, head, mid);
    merge_sort(arr, mid + 1, tail);
    int *num = (int *)malloc(sizeof(int) * (tail - head + 1));
    int p1 = head, p2 = mid + 1, ind = 0;
    while (p1 <= mid || p2 <= tail) {
        if (p2 > tail || (p1 <= mid && arr[p1] <= arr[p2])) {
            num[ind++] = arr[p1++];
        } else {
            num[ind++] = arr[p2++];
        }
    }
    memcpy(arr + l, num, sizeof(int) * (tail - head + 1));
    free(num);
}

其中對于兩個子數(shù)組的合并，感覺判斷條件之間存在交叉和部分獨立，但是不影響最后的結(jié)果

不穩(wěn)定排序

1. 選擇排序?

??選擇排序?qū)?shù)組分為已排序和未排序兩部分，我們要做的就是在后面未排序的數(shù)組中找到最小的一個元素，將他放在已排序部分的后面，如此循環(huán)，直到未排序部分元素的個數(shù)為0，算法結(jié)束。
???實現(xiàn)代碼如下：

void select_sort(int *arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        int ind = i;
        for (int j = i; j < n; j++) {
            if (arr[i] < arr[ind]) ind = i;
        }
        if (ind == i) continue;
        swap(arr[ind], arr[i]);
    }
}

2. 快速排序

???快排算法的基本思路就是選取基本元素，并根據(jù)首尾兩個指針將數(shù)組分成兩部分，其中前面部分數(shù)據(jù)均小于基準元素，后面部分均大于基準元素，之后繼續(xù)對劃分后的兩個子數(shù)組進行劃分即可。

快排1

快排2
快排3
???注意：首先前移的一定是尾指針，之后再首尾指針相互移動
???對應代碼為：

void quick_sort(int *arr, int l, int r) {
    if (l > r) return ;
    int head = l, tail = r, tmp = arr[head];
    while (head != tail) {
        while (head < tail && arr[tail] >= tmp) tail--;
        while (head < tail && arr[head] <= tmp) head++;
        if (tail != head) {
            swap(arr[head], arr[tail]);
        }
    }
    arr[l] = arr[head];
    arr[head] = tmp;
    quick_sort(arr, l, head - 1);
    quick_sort(arr, head + 1, r);
}

???快排算法的時間復雜性雖然為(n * log n)，但是他并不穩(wěn)定，當數(shù)組是逆序排列時，此時會退化成冒泡排序時間復雜度變?yōu)镺(n * n)，所以基準值的選取十分重要，這回直接影響算法的效率，為此，我們可以優(yōu)化為隨機化快排，也就是將最壞事件轉(zhuǎn)換為概率事件，我們在數(shù)組中隨即選擇數(shù)字作為劃分基準，所以，算法的一般時間復雜性依舊為O(n * log n);

二查找算法

1. 二分查找

???之前最普通的查找算法就是在一個有序的數(shù)組中，找到待查找數(shù)字的下標，若找不到則返回-1
二分查找
對應代碼如下：

void binarySearch(int *arr, int n, int x) {
    int head = 0, tail = n - 1, mid;
    while (head <= tail) {
        mid = (head + tail) >> 1;
        if (arr[mid] == x) return mid;
        else if (arr[mid] < head) head = mid + 1;
        else tail = mid - 1;
    }
    return -1
}

此外，二分查找還有兩種特殊的情況，如下：

二分特殊1
???在如1111110000000的數(shù)組中，找到最后一個1，首先我們了解max和min是如何變化的，之后我們來考慮一種情況：那就是當這是一個全0的序列，程序結(jié)束后min和max均會指向下標為0的元素，所以程序最后的返回將會是0，但這顯然是錯誤的，為了解決這個問題，我們引入了一個虛擬頭指針，一開始min指向 -1，現(xiàn)在我們來解釋為什么mid = (min + max + 1) >> 2，而不是mid = (min + max) >> 1，因為存在這樣一種情況，當最后min和max指向相鄰的兩個元素時，此時求mid之后，會陷入死循環(huán)中，程序無法跳出循環(huán)。最后需要注意的是：函數(shù)最后返回的是head的值，也就是最后一個1所在的下標，此外有實際出發(fā)推演，while循環(huán)的條件是min < max沒有等號。

二分查找特殊2
???第二種特殊情況，這里就不再多說，相似理解，我們直接上代碼

void binarySearch_2(int *arr, int n) {  //找到最后一個1所在的下標
    int head = -1, tail = n - 1, mid;
    while (head < tail) {
        mid = (head + tail + 1) >> 1;
        if (arr[mid] == 1) head = mid;
        else tail = mid - 1;
    }
    return head;
}
void binarySearch_3(int *arr, int n) {  //找到第一個1所在的下標
    int head = 1, tail = n, mid;
    while (head < tail) {
        mid = (head + tail) >> 1;
        if (arr[mid] == 1) tail = mid;
        else head = mid + 1;
    }
    return head == n ? -1 : head;
}

???擴大來說，這里的1并不僅僅是1，其實更多指的是一種性質(zhì)，我們要找的是找到第一個或者是最后一個滿足這種性質(zhì)的元素下標，這樣我們可以避免使用低效的線性搜索，可以使用更高效的二分查找。

三分查找

?三分查找這里我們用來求的是二次函數(shù)極值點的問題，當然對于這個問題我們還可以用求導，使用牛頓迭代法進行求解

三總代碼獻上

穩(wěn)定排序

#include <iostream>
#include <cstring>
#include <ctime>
using namespace std;

//穩(wěn)定排序有：插入排序，冒泡排序，歸并排序

#define swap(a, b) { \  //宏定義 交換a和b的值
    __typeof(a) __tmp = a;     a = b, b = __tmp; }
#define TEST(arr, n, func, args...) { \  //宏定義 調(diào)用排序函數(shù)并打印輸出
    int *num = (int *)malloc(sizeof(int) * n);     memcpy(num, arr, sizeof(int) * n);     printf("%s:\n", #func);     output(num, n);     func(args);     output(num, n);     printf("\n");     free(num); }

void insert_sort(int *arr, int n) {  //插入排序
    for (int i = 1; i < n; i++) {
        for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {
            swap(arr[j - 1], arr[j]);
        }
    }
}

void bubble_sort(int *arr, int n) {  //冒泡排序
    for (int i = 1; i < n; i++) {
        int flag = 0;
        for (int j = 0; j < n - i; j++) {
            if (arr[j] <= arr[j + 1]) continue;
            swap(arr[j], arr[j + 1]);
            flag = 1;
        }
        if (!flag) break;
    }
}

void merge_sort(int *arr, int head, int tail) {  //歸并排序
    if (tail - head <= 1) {
        if (tail - head == 1 && arr[head] > arr[tail]) {
            swap(arr[head], arr[tail]);
        }
        return ;
    }
    int mid = (head + tail) >> 1;
    merge_sort(arr, head, mid);
    merge_sort(arr, mid + 1, tail);
    int *num = (int *)malloc(sizeof(int) * (tail - head + 1));
    int p1 = head, p2 = mid + 1, ind = 0;
    while (p1 <= mid || p2 <= tail) {
        if (p2 > tail || (p1 <= mid && arr[p1] <= arr[p2])) {
            num[ind++] = arr[p1++];
        } else {
            num[ind++] = arr[p2++];
        }
    }
    memcpy(arr + head, num, sizeof(int) * (tail - head + 1));
    free(num);
}

void output(int *arr, int n) {
    printf("[");
    for (int i = 0; i < n; i++) {
        if (i) printf(", ");
        printf("%d", arr[i]);
    }
    printf("]\n");
}

void randInt(int *a, int n) {
    while (n--) a[n] = rand() % 100;
}

int main() {
    #define MAX_N 20
    srand(time(0));
    int arr[MAX_N] = {0};
    randInt(arr, MAX_N);
    TEST(arr, MAX_N, insert_sort, num, MAX_N);
    TEST(arr, MAX_N, bubble_sort, num, MAX_N);
    TEST(arr, MAX_N, merge_sort, num, 0, MAX_N - 1);
    return 0;
}

/* 對應輸出
insert_sort:
[83, 1, 2, 39, 70, 96, 37, 7, 32, 40, 44, 14, 56, 35, 52, 64, 23, 15, 12, 15]
[1, 2, 7, 12, 14, 15, 15, 23, 32, 35, 37, 39, 40, 44, 52, 56, 64, 70, 83, 96]

bubble_sort:
[83, 1, 2, 39, 70, 96, 37, 7, 32, 40, 44, 14, 56, 35, 52, 64, 23, 15, 12, 15]
[1, 2, 7, 12, 14, 15, 15, 23, 32, 35, 37, 39, 40, 44, 52, 56, 64, 70, 83, 96]

merge_sort:
[83, 1, 2, 39, 70, 96, 37, 7, 32, 40, 44, 14, 56, 35, 52, 64, 23, 15, 12, 15]
[1, 2, 7, 12, 14, 15, 15, 23, 32, 35, 37, 39, 40, 44, 52, 56, 64, 70, 83, 96]
*/

非穩(wěn)定排序

#include <iostream>
#include <cstring>
#include <ctime>
using namespace std;

#define swap(a, b) {     __typeof(a) __tmp = a;     a = b, b = __tmp; }
#define TEST(arr, n, func, args...) {     int *num = (int *)malloc(sizeof(int) * n);     memcpy(num, arr, sizeof(int) * n);     printf("%s:\n", #func);     output(num, n);     func(args);     output(num, n);     printf("\n");     free(num); }

void select_sort(int *arr, int n) {  //選擇排序
    for (int i = 0; i < n - 1; i++) {
        int ind = i;
        for (int j = i; j < n; j++) {
            if (arr[j] < arr[ind]) ind = j;
        }
        if (ind == i) continue;
        swap(arr[ind], arr[i]);
    }
}

void quick_sort(int *arr, int head, int tail) {  //快排
    if (head > tail) return ;
    int left = head, right = tail;
    int tmp = arr[head];
    while (left != right) {
        while (left < right && arr[right] >= tmp) right--;
        while (left < right && arr[left] <= tmp) left++;
        if (left != right) swap(arr[left], arr[right]);
    }
    arr[head] = arr[left];
    arr[left] = tmp;
    quick_sort(arr, head, left - 1);
    quick_sort(arr, left + 1, tail);
}

void randInt(int *arr, int n) {
    while (n--) arr[n] = rand() % 100;
}

void output(int *arr, int n) {
    printf("[");
    for (int i = 0; i < n; i++) {
        if (i) printf(", ");
        printf("%d", arr[i]);
    }
    printf("]\n");
}

int main() {
    #define MAX_N 20
    srand(time(0));
    int arr[MAX_N];
    randInt(arr, MAX_N);
    TEST(arr, MAX_N, select_sort, num, MAX_N)
    TEST(arr, MAX_N, quick_sort, num, 0, MAX_N - 1)
    return 0;
}

/* 代碼輸出
select_sort:
[2, 89, 16, 82, 58, 73, 61, 91, 59, 79, 18, 62, 81, 70, 31, 89, 82, 46, 27, 71]
[2, 16, 18, 27, 31, 46, 58, 59, 61, 62, 70, 71, 73, 79, 81, 82, 82, 89, 89, 91]

quick_sort:
[2, 89, 16, 82, 58, 73, 61, 91, 59, 79, 18, 62, 81, 70, 31, 89, 82, 46, 27, 71]
[2, 16, 18, 27, 31, 46, 58, 59, 61, 62, 70, 71, 73, 79, 81, 82, 82, 89, 89, 91]
*/

二分查找

#include <iostream>
using namespace std;

#define P(func, args...) {     printf("%s = %d\n", #func, func(args)); }

int binarySearch_1(int *arr, int n, int x) {
    int head = 0, tail = n - 1, mid;
    while (head <= tail) {
        mid = (head + tail) >> 1;
        if (arr[mid] == x) return mid;
        else if (arr[mid] < x) head = mid + 1;
        else tail = mid - 1;
    }
    return -1;
}

//1111100000 找到最后一個1
int binarySearch_2(int *arr, int n) {
    int head = -1, tail = n - 1;
    while (head < tail) {
        int mid = (head + tail + 1) >> 1;
        if (arr[mid] == 1) head = mid;
        else tail = mid - 1;
    }
    return head;
}

//000000111111找到第一個1
int binarySearch_3(int *arr, int n) {
    int head = 0, tail = n, mid;
    while (head < tail) {
        mid = (head + tail) >> 1;
        if (arr[mid] == 1) tail = mid;
        else head = mid + 1;
    }
    return head == n ? -1 : head;
}

int main() {
    int arr1[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int arr2[10] = {1, 1, 1, 1, 1, 1, 1, 1, 0, 0};
    int arr3[10] = {0, 0, 0, 0, 0, 0, 0, 1, 1, 1};
    printf("num %d's index = %d\n", 7, binarySearch_1(arr1, 10, 7));
    P(binarySearch_2, arr2, 10);
    P(binarySearch_3, arr3, 10);
    return 0;
}
/* 對應輸出為：
num 7's index = 6
binarySearch_2 = 7
binarySearch_3 = 7
*/