经典算法

排序算法

冒泡排序

冒泡排序，就跟金鱼吐泡泡一样，其原理就是，第一个数跟第二个数进行比较（从小到大），如果第一个比第二个大，那么他们两个数据就进行交换，然后第二个与第三个进行比较，如果不大于那么数据进行下一次排序

特点是第一次排序肯定会把最大的或者最小的数排出来

时间复杂度 空间复杂度 是否稳定
O(n^2) O(1) 稳定

代码

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
#include <stdio.h>

int main() {
    int a[10];

    for (int i = 0; i < 10; ++i) {
        printf("请输入第%d个元素数据:", i + 1);
        scanf("%d", &a[i]);
    }

    for (int i = 0; i < 10; ++i) {
        printf("%d ", a[i]);
    }

    printf("\n----------冒 泡 前----------\n");

    for (int i = 0; i < 10 - 1; ++i) {

        for (int j = 0; j < 10 - i - 1; ++j) {

            if (a[j] > a[j + 1]) {
                int temp;
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }

        }
        printf("第%d次冒泡：", i + 1);
        for (int j = 0; j < 10; ++j) {
            printf("%d ", a[j]);
        }
        printf("\n");
    }

    printf("----------冒 泡 后----------\n");

    for (int i = 0; i < 10; ++i) {
        printf("%d ", a[i]);
    }
}

运行结果：

这是很基础的冒泡，但是还有点瑕疵，比如10个数，可能排5次就排好了，但是这个他是一直运行，直到次数用尽，这就会做很多无用功，所以冒泡排序得优化一下

优化版

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
#include <stdio.h>

int main() {
    int a[10], t, flag = 1;

    for (int i = 0; i < 10; ++i) {
        printf("请输入第%d个数据:", i + 1);
        scanf("%d", &a[i]);
    }

    for (int i = 0; i < 10; ++i) {
        printf("%d ", a[i]);
    }

    printf("\n----------冒 泡 前----------\n");

    for (int i = 0; i < 10 - 1 && flag; ++i) {
        flag = 0;
        for (int j = 0; j < 10 - i - 1; ++j) {

            if (a[j] > a[j + 1]) {
                t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
                flag = 1;
            }

        }
        
        printf("第%d次冒泡：", i);
        for (int k = 0; k < 10; ++k) {
            printf("%d ", a[k]);
        }
        printf("\n");
    }

    printf("----------冒 泡 后----------\n");

    for (int i = 0; i < 10; ++i) {
        printf("%d ", a[i]);
    }
}

运行结果：

这次就是优化后的冒泡排序，比较之前，这次只是冒泡两次就冒泡成功，并停止冒泡，要是按照之前的写，还得进行9次冒泡才行

选择排序

选择排序是一种简单直接的排序算法，思想是先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾

动图演示

代码

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
#include <stdio.h>

int main() {
    int a[10];

    for (int i = 0; i < 10; ++i) {
        printf("请输入第%d个元素数据:", i + 1);
        scanf("%d", &a[i]);
    }

    for (int i = 0; i < 10; ++i) {
        printf("%d ", a[i]);
    }

    printf("\n----------排 序 前----------\n");

    for (int i = 0; i < 10 - 1; ++i) {

        for (int j = i + 1; j < 10; ++j) {

            if (a[i] > a[j]) {
                int temp;
                temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }

        }
        printf("第%d次排序：", i);
        for (int j = 0; j < 10; ++j) {
            printf("%d ", a[j]);
        }
        printf("\n");
    }

    printf("----------排 序 后----------\n");

    for (int i = 0; i < 10; ++i) {
        printf("%d ", a[i]);
    }
}

其运行结果是

但是这还有一种优化方法，就是先假设一个最小数，并把假设的最小数的下标赋值给一个元素，然后用那个最小数的下标进行排序，最后在进行判断，如果最小数的下标不等于赋值给它的值的下标，那么就进行交换

优化版

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
#include <stdio.h>

int main() {
    int a[10], t, minIdx;

    for (int i = 0; i < 10; ++i) {
        printf("请输入第%d个数据:", i + 1);
        scanf("%d", &a[i]);
    }

    for (int i = 0; i < 10; ++i) {
        printf("%d ", a[i]);
    }

    printf("\n----------排 序 前----------\n");

    for (int i = 0; i < 10 - 1; ++i) {
        minIdx = i;

        for (int j = i + 1; j < 10; ++j) {

            if (a[minIdx] > a[j]) {
                minIdx = j;
            }

        }

        if (minIdx != i) {
            t = a[i];
            a[i] = a[minIdx];
            a[minIdx] = t;
        }
        printf("第%d次排序：", i);
        for (int k = 0; k < 10; ++k) {
            printf("%d ", a[k]);
        }
        printf("\n");
    }

    printf("----------排 序 后----------\n");

    for (int i = 0; i < 10; ++i) {
        printf("%d ", a[i]);
    }
}

其运行结果是

插入排序

插入排序，特点是从左往右开始排序

第一次排序：第一个不动，从第二个开始，跟第一个比较如果第二个比第一个小（从大到小），那么就进行交换，然后第一次排序结束

第二次排序：从第三个开始跟第二个比较如果第三个小那么什么都不做，第二次排序结束，如果比第二个大，那么就和第二个进行交换，然后交换过后的第二个（原来的第三个）跟第一个比较，大则交换，否则排序结束

后面的排序都是如此

时间复杂度 空间复杂度 是否稳定
O(n^2) O(1) 稳定

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>

int main() {
    int a[15] = {47, 4, 68, 61, 6, 87, 6, 37, 5, 86, 7, 61, 11, 65, 46}, j;

    for (int i = 1; i < 15; ++i) {
        int current = a[i];

        for (j = i - 1; j >= 0 && current < a[j]; j--) {
            a[j + 1] = a[j];
        }
    
        a[j + 1] = current;

        printf("第%d次的排序结果:", i);
        for (int k = 0; k < 15; ++k) {
            printf("%d ", a[k]);
        }
        printf("\n");
    }
}

希尔排序

希尔排序的本质其实还是插入排序，不过不再是顺序的从左到右依次排列，而是先进行分组，然后取每组的第一个数进行比较并交换，比较完成之后进行第二组比较，然后是第三组（这里比较几次取决于你定义了几个组），最后一组一定是 1

时间复杂度 空间复杂度 是否稳定
O(n^1.3) O(1) 不稳定

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>

int main() {
    int a[10] = {0, 1, 4, 7, 8, 5, 2, 3, 6, 9};
    int b[3] = {5, 3, 1};  // 分三组
    int len = sizeof(a) / sizeof(int);

    for (int x = 0; x < 3; ++x) {
        int idx = b[x];
        for (int i = idx; i < len; ++i) {
            int prive = a[i], j;
            for (j = i - idx; j >= 0 && prive < a[j]; j = j - idx) {
                a[j + idx] = a[j];
            }
            a[j + idx] = prive;
        }
    }

    for (int i = 0; i < 10; ++i) {
        printf("%d ", a[i]);
    }
}

快速排序

快速排序思想是先通过一次排序找到一个基准值，此时通过排序找到的基准值左边都是比基准值小的数右边都是比基准值大的数，然后先对左边的数进行排序，还是一样，先找个基准值然后跟前面的一样，左边的都是比基准值小的右边都是比基准值大的这样还是对左边进行排序直至有序为止，然后开始对右边的内容进行分排序

时间复杂度 空间复杂度 是否稳定
O(n^1.3) O(1) 不稳定

代码

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
#include <stdio.h>

void fun(int a[], int low, int high);

int kp(int a[], int low, int high);

int main() {
    int a[10] = {0, 1, 4, 7, 8, 5, 2, 3, 6, 9};
    int len = sizeof(a) / sizeof(int);

    fun(a, 0, len - 1);

    for (int i = 0; i < 10; ++i) {
        printf("%d ", a[i]);
    }
}

void fun(int a[], int low, int high) {
    if (low < high) {
        int mid = kp(a, low, high);
        fun(a, low, mid - 1);
        fun(a, mid + 1, high);
    }
}

int kp(int a[], int low, int high) {
    int pivot = a[low];
    int i = low;
    int j = high;

    while (i < j) {
        while (i < j && pivot <= a[j]) j--;
        a[i] = a[j];
        while (i < j && pivot >= a[i]) i++;
        a[j] = a[i];
    }
    a[i] = pivot;

    return i;
}

查找算法

顺序查找

从头到尾或者从未到头进行遍历，找到既终止遍历

查找算法 时间复杂度 空间复杂度
顺序查找 O(n) O(1)

代码

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
#include <stdio.h>

int cz(int a[]);

int main() {
    int a[10] = {2, 5, 6, 8, 9, 1, 0, 3, 7, 4};

    int k = cz(a);

    if (k == -1) {
        printf("没找到");
    } else {
        printf("下标为%d", k);
    }
}

int cz(int a[]) {
    int b;
    printf("请输入要查找的数:");
    scanf("%d", &b);

    for (int i = 0; i < 10; ++i) {
        if (a[i] == b) {
            return i;
        }
    }

    return -1;
}

折半查找（二分查找）

从中间一分为二，利用中间值的大小判断要找的元素在哪一边，然后继续折半，重复上述过程直至找到目标为止

要查找的数必须是有序的,无序的无法使用折半查找

查找算法 时间复杂度 空间复杂度
折半查找 O(log2^n) O(1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>

int main() {
    int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int num, low = 0, high = sizeof(a) / sizeof(int);
    scanf("%d", &num);

    while (low <= high) {
        int mid = (low + high) / 2;

        if (a[mid] == num) {
            printf("找到了");
            break;
        } else if (num < a[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    if (low > high) {
        printf("查找失败");
    }
}

代码（递归）

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
#include <stdio.h>

int fun(int a[], int num, int low, int high);

int main() {
    int a[5] = {68, 79, 81, 87, 99};
    int num = 99; // 要查找的数
    int low = 0;
    int high = sizeof(a) / sizeof(int);

    printf("%d", fun(a, num, low, high));
}

int fun(int a[], int num, int low, int high) {
    int idx = (low + high) / 2;
    int sum = -1;

    if (low <= high) {
        if (a[idx] == num) {
            return idx;
        } else if (a[idx] < num) {
            sum = fun(a, num, low + 1, high);
        } else {
            sum = fun(a, num, low, high - 1);
        }
    }

    if (a[sum] == num) {
        return sum;
    } else {
        return -1;
    }
}

分块查找

数据要有一定的顺序，要把一整个数组分成若干个块，而且块与块之间有顺序，分块里面的值不能超过设置的块值，如一下案例，数组共有十五个，分三块，第一个块值为 5 那么块里面的值不能超过 5

查找算法 时间复杂度 空间复杂度
分块查找 O(log2^n)~O(n) O(1)

代码

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
#include <stdio.h>

int main() {
    int a[15] = {5, 4, 3, 2, 1, 6, 7, 8, 9, 10, 15, 14, 13, 12, 11};
    int b[3] = {5, 10, 15};
    int sum;

    printf("请输入要查找的数:");
    scanf("%d", &sum);

    int i, j;
    for (i = 0; i < 3; ++i) {
        if (sum <= b[i]) {
            break;
        }
    }

    if (i == 3) {
        printf("数太大");
    } else {
        int idx = 5 * i;

        for (j = idx; j < idx + 5; ++j) {
            if (a[j] == sum) {
                printf("找到了");
                break;
            }
        }

        if (j == idx + 5) {
            printf("没找到");
        }
    }
}

算法总结

  • 算法的五大特征

    ​ 有穷性、确定性、可行性、输入项、输出项

  • 算法的四个目标

    ​ 正确性、健壮性、可读性、高效性

  • 时间复杂度 : O( )

    ​ 用来描述算法的运行时间

    ​ O(1) < O(logn) < O(n) < O(n ^ 2) < O(n ^ 3)

  • 空间复杂度 : O( )

    ​ 用来描述算法所耗费的存储空间

排序

排序方法 时间复杂度 空间复杂度 是否稳定
冒泡排序 O(n^2) O(1) 稳定
选择排序 O(n^2) O(1) 不稳定
插入排序 O(n^2) O(1) 稳定
希尔排序 O(n^1.3) O(1) 不稳定
快速排序 O(nlog2^n) O(n) 不稳定

如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的

用某排序方法对一个关键码序列进行递增排序时，对于其中关键码相同的元素，若该方法可保证在排序前后这些元素的相对位置不变，则称该排序方法是稳定的

  • 冒泡排序：每次把最大的或者最小的数据排出来
  • 选择排序：每次从数据中找到最大的或者最小的，将其放到前面的位置
  • 插入排序：从下标为1的数据开始；把后面的数与前面的进行比较找到合适的位置插入进去
  • 希尔排序：增量数组递减d[]，d[k]个数组为一组，每组的第一个数据进行插入排序
  • 快速排序：假设第一个数是基准值，将所有小于基准值的数放到基准值之前；大于基准值的数放到基准值之后

查找

查找算法 时间复杂度 空间复杂度
顺序查找 O(n) O(1)
折半查找 O(log2^n) O(1)
分块查找 O(log2^n)~O(n) O(1)
  • 顺序查找：在数组中，从第一个往后面挨个对比
  • 折半查找：从数组的中间开始对比，数小于待查找的，查后半部分；数大于待查找，查前半部分； 前提：数组有序，或从小到大，或从大到小
  • 分块查找：把数组分为若干个元素个数相同的块，且块间有序；首先找到块号，从块号里面进行顺序查找