抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

排序合集 5 种 - 插入、冒泡、归并、选择、快排

秃头王
基础数据结构

发布于：2022年1月19日
次浏览

排序算法分类

稳定 ：( 插入、冒泡、归并)

非稳定 (不稳定) ：(选择、快排)

内部 ：(整体一次性的加入到内存当中,整体的去排序)

外部 ： (对一个数据文件排序的话可以不将整个文件都加载到内存里面进行排序 - 归并！ )

在这里插入图片描述

插入排序 (insert_Sort)

口诀 :

  1. 将数组分成【已排序区】 和 【待排序区】
  2. 将【待排序区】第一个元素，向前插入到【已排序区】
  3. 直到【待排序区】没有元素为止

动图显示

时间复杂度分析

最好 ：0 次

最坏 ：n - 1 次

平均复杂度 ：( 最好 + 最坏 ) / 2 : $\frac{(n - 1)}{2} * N$ : $O(N^2)$

代码实现 - 模块

1
2
3
4
5
6
7
8
9
// 插入排序
void insert_Sort(int *num, int n) {
    for(int i = 1; i < n; i++) {
        for(int j = i; j > 0 && num[j] < num[j - 1]; j--) {
            swap(num[j], num[j - 1]);
        }
    }
    return ;
}

冒泡排序 (bubble_Sort)

口诀 :

  1. 将数组分成【已排序区】 和 【待排序区】
  2. 从头到尾扫描【待排序区】，若前面元素比后面元素大，则交换
  3. 每一轮都会将【待排序区】中最大的放到【已排序区】的开头
  4. 直到【待排序区】没有元素为止

小优化 ： 如果一轮中一次交换都没有就证明序列已经有序可以提前结束

动图显示

时间复杂度

平均复杂度 ： $O(N^2)$

代码实现 - 模块

1
2
3
4
5
6
7
8
9
10
11
12
13
// 冒泡排序
void bubble_Sort(int *num, int n) {
    int falg = 1;
    for(int i = 1; i < n && falg; i++) {
        falg = 0;
        for(int j = 0; j < n - i; j++) {
            if(num[j] <= num[j + 1]) continue;
            swap(num[j], num[j + 1]);
            falg++;
        }
    }
    return ;
}

归并排序 - 二路归并 (merge_Sort)

核心思想分治

将【待排序数组】分为两个部分

如 ： 9 7 8 5 4 1 2 3 6 5

分为 : 9 7 8 5 4 — 1 2 3 6 5

再分：9 7 — 8 5 4 — 1 2 — 365

达到足够小并且立马能拿到答案的规模

上一层 ： 【 — 我是空数组 — 】

可以得到 7 9 — 4 5 8 — 1 2 — 3 5 6 组内有序组间无序

一个指向👆 ____👆 合并成一个有序数组 - 在拷贝到原数组

他们两个比较谁小就插入到上面数组

动图显示

image

时间复杂度

平均复杂度 ： $O(Nlog^N)$

代码实现 - 模块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 归并排序
void merge_Sort(int *num, int l, int r) {
    if(r - l <= 1) {
        if(r - l == 1 && num[r] < num[l]) {
            swap(num[r], num[l]);
        }
        return ;
    }

    int mid = (r + l) >> 1;
    merge_Sort(num, l, mid);
    merge_Sort(num, mid + 1, r);
    int *temp = (int *)malloc(sizeof(int) * (r - l + 1));
    int p1 = l, p2 = mid + 1, cnt = 0;
    while(p1 <= mid || p2 <= r) {
        if(p2 > r || (p1 <= mid && num[p1] <= num[p2])) {
            temp[cnt++] = num[p1++];
        } else {
            temp[cnt++] = num[p2++];
        }
    }
    memcpy(num + l, temp, sizeof(int) * (r - l + 1));
    free(temp);
    return ;
}

稳定排序代码合集 - 插入、冒泡、归并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/*************************************************************************
        > File Name: 稳定排序合集-插入、冒泡、归并.c
        > Author: 秃头王
        > Mail: 1658339000@qq.com
        > Created Time: 2022年01月19日 星期三 17时02分43秒
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

// typeof(a) 相当于获取 a 的类型 在定义一个变量 __temp
#define swap(a, b) {\
    __typeof(a) __temp = a;\
    a = b, b = __temp;\
}

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


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

// 冒泡排序
void bubble_Sort(int *num, int n) {
    int falg = 1;
    for(int i = 1; i < n && falg; i++) {
        falg = 0;
        for(int j = 0; j < n - i; j++) {
            if(num[j] <= num[j + 1]) continue;
            swap(num[j], num[j + 1]);
            falg++;
        }
    }
    return ;
}

// 归并排序
void merge_Sort(int *num, int l, int r) {
    if(r - l <= 1) {
        if(r - l == 1 && num[r] < num[l]) {
            swap(num[r], num[l]);
        }
        return ;
    }

    int mid = (r + l) >> 1;
    merge_Sort(num, l, mid);
    merge_Sort(num, mid + 1, r);
    int *temp = (int *)malloc(sizeof(int) * (r - l + 1));
    int p1 = l, p2 = mid + 1, cnt = 0;
    while(p1 <= mid || p2 <= r) {
        if(p2 > r || (p1 <= mid && num[p1] <= num[p2])) {
            temp[cnt++] = num[p1++];
        } else {
            temp[cnt++] = num[p2++];
        }
    }
    memcpy(num + l, temp, sizeof(int) * (r - l + 1));
    free(temp);
    return ;
}

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

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

int main() {
    srand(time(0));
    #define MAX_N 20
    int arr[MAX_N];
    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);
    #undef MAX_N
    return 0;
}
分界线👇不稳定了

选择排序 (select_Sort)

口诀 :

  1. 将数组分成【已排序区】 和 【待排序区】
  2. 每一轮从【待排序区】中选择一个最小的元素方到【已排序区】的尾部
  3. 直到【待排序区】没有元素为止

在这里插入图片描述

时间复杂度

平均复杂度 ： $O(N^2)$

代码实现 - 模块

1
2
3
4
5
6
7
8
9
10
11
// 选择排序
void select_Sort(int *num, int n) {
    for(int i = 0; i < n - 1; i++) {
        int ind = i;
        for(int j = i + 1; j < n; j++) {
            if(num[ind] > num[j]) ind = j;
        }
        swap(num[i], num[ind]);
    }
    return ;
}

快速排序 (quick_Sort)

口诀 :

  1. 选择基准数 ： 一般选择序列的第一个数 (基准值)
  2. 进行（partition）操作：作用就是使得待排序的序列分为了两部分
  3. 前部分都小于基准值 — 后面一部分都大于基准值 (一轮partition 操作)
  4. head = 第一个数(基准值) tail = 最后一个元素
  5. tail 操作
  6. 从后往前找第一个小于基准值的数 - 找到之后填到头指针的位置
  7. head 操作
  8. 从前往后找到找到一个大于基准值的数 - 找到之后填到尾针的位置

image-20220119213003097

image-20220119213010221

时间复杂度

平均复杂度 ： $O(Nlog^N)$

完全逆序 ： $ O(N^2)$ - (就变成了选择排序)

代码实现 - 模块 - 未优化 - 填坑法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 快排 — 第一版
void quick_Sort(int *num, int l, int r) {
    if(l > r) return ;
    int x = l, y = r, z = num[l];
    while(x < y) {
        // 先从后往前扫因为第一个位置是空着可以覆盖掉
        while(x < y && num[y] > z) y--;
        if(x < y) num[x++] = num[y];
        while(x < y && num[x] < z) x++;
        if(x < y) num[y--] = num[x];
    }
    // 头尾指针重合
    num[x] = z;
    quick_Sort(num, l, x - 1);
    quick_Sort(num, x + 1, r);
    return ;
}

代码实现 - 模块 - 优化 - 基准值两点取中法、无监督优化(去掉x < y)、单边递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 快排 — 第二版 基准值两点取中法、无监督优化(去掉x < y)、单 边递归法

void quick_Sort1(int *num, int l, int r) {
    while(l < r) {
    int x = l, y = r, z = num[(l + r) >> 1];
        do {
            while(num[x] < z) x++;
            while(num[y] > z) y--;
            if(x <= y) {
                swap(num[x], num[y]);
                x++, y--;
            }
        } while(x <= y);
        quick_Sort1(num, l, y);
        l = x;
    }
    return ;
}

不稳定排序代码合集 - 选择、快速、快速优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/*************************************************************************                   [0]
        > File Name: 稳定排序合集-插入、冒泡、归并.c
        > Author: 秃头王
        > Mail: 1658339000@qq.com
        > Created Time: 2022年01月19日 星期三 17时02分43秒
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

// typeof(a) 相当于获取 a 的类型 在定义一个变量 __temp
#define swap(a, b) {\
    __typeof(a) __temp = a;\
    a = b, b = __temp;\
}

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

// 选择排序
void select_Sort(int *num, int n) {
    for(int i = 0; i < n - 1; i++) {
        int ind = i;
        for(int j = i + 1; j < n; j++) {
            if(num[ind] > num[j]) ind = j;
        }
        swap(num[i], num[ind]);
    }
    return ;
}

// 快排 — 第一版
void quick_Sort(int *num, int l, int r) {
    if(l > r) return ;
    int x = l, y = r, z = num[l];
    while(x < y) {
        // 先从后往前扫因为第一个位置是空着可以覆盖掉
        while(x < y && num[y] > z) y--;
        if(x < y) num[x++] = num[y];
        while(x < y && num[x] < z) x++;
        if(x < y) num[y--] = num[x];
    }
    // 头尾指针重合
    num[x] = z;
    quick_Sort(num, l, x - 1);
    quick_Sort(num, x + 1, r);
    return ;
}

// 快排 — 第二版 基准值两点取中法、无监督优化(去掉x < y)、单 边递归法

void quick_Sort1(int *num, int l, int r) {
    while(l < r) {
    int x = l, y = r, z = num[(l + r) >> 1];
        do {
            while(num[x] < z) x++;
            while(num[y] > z) y--;
            if(x <= y) {
                swap(num[x], num[y]);
                x++, y--;
            }
        } while(x <= y);
        quick_Sort1(num, l, y);
        l = x;
    }
    return ;
}


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

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

int main() {
    srand(time(0));
    #define MAX_N 20
    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);
    TEST(arr, MAX_N, quick_Sort1, num, 0, MAX_N - 1);
    #undef MAX_N
    return 0;
}

有趣的知识

1
2
3
4
5
g++ test.cpp
time ./a.out > out_1

// 比较两个文件是否相等
diff out_1  out_2

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://tutouwang.vercel.app/2022/01/19/%E5%9F%BA%E7%A1%80%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/%E6%8E%92%E5%BA%8F%E5%90%88%E9%9B%86/

更新于：2022年5月22日

排序

评论