本篇内容本着先自己弄明白，然后再写出程序，最后总结的顺序编写的，因此更新时间应该会很慢。
最后编辑时间：2020年8月19日23:20:58
To be Continued…
つづく

写在前边

之前教カレシーC语言的是否，我抽风出了一道给数组排序的题目，然后就发现排序算法，那是什么，为什么我一点印象都没有？

再加上，在这之前，第一次面试的时候，对方问我能举出多少种排序算法的例子，我：？？？

除了冒泡排序，我竟然说不出来第二种排序算法了。（捂脸.jpg

我一年级时候学的C语言难道都还给老师了么，还有二年级学的数据结构，我哭辽

还有，我已经好多年（才1年多不到两年）没有使用C语言了，如果不是为了教レシー的话，我应该不会再碰来着。。

所以同时为了恢复这项技能，我决定这篇文章，我全部使用C语言去实现（才。。才不是因为手里有写好的代码呢，别误会了）

于是就有了今天这篇文章，我只是尽量地总结一下我所了解的排序算法，不保证全面。

正文部分

废话说完了，那么我们开始进入正题吧。

默认代码部分

本文章默认使用下述部分代码作为测试代码，所以下边再写就只写函数啦。

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>
//导入 stdbool.h 来使用布尔类型
#include <stdbool.h>

#define N 10

void InputArray(int *arr)
{
    for (int i = 0; i < N; i++)
    {
        scanf("%d", arr + i);
    }
}
void OutputArray(int *arr)
{
    for (int i = 0; i < N; i++)
    {
        printf("%d", *(arr + i));
        if (i < N - 1) printf(", ");
    }
}

void Swap(int *x, int *y)
{
    int temp = *x; // 做两个值交换的时候必要的临时变量。
    *x = *y;
    *y = temp;
    return;
}

void Sort(int *arr, void (*method)(int *))
{
    method(arr);
    OutputArray(arr);
}

// ··· 其他函数的实现

int main()
{
    // int arr[N];
    int arr[N] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    //InputArray(arr);
    Sort(arr, SortName); // 这里的SortName代表选择的排序方法
}

冒泡排序（Bubble Sort）

废话部分

首先来说说这个冒泡排序是什么

我依稀记得老师讲过，这个排序算法的效果像是水中的鱼吐出的气泡，越靠近水面，气泡越大，因此有了这个名字。

对应到程序的话，就是按顺序遍历数组，将i与i+1位置的元素进行比较，按照排序顺序交换元素。

  • 从i元素开始，比较相邻元素。令j = i如果arr[i] > arr[i + 1]，则交换两元素（对与升序排序）。如果arr[i] < arr[i + 1]，则交换两元素（对与降序排序）
  • 每次检查完数组后，可以保证最大（最小）值在数组最后依次排序。
  • 继续步骤1，从元素i + 1开始。
  • 重复步骤1~3，直至遍历完数组。

Show me code time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void BubbleSort(int *arr)
{
    bool isChanged; // 记录遍历过程中是否有变换
    for (int i = 0; i < N - 1; i++)
    {
        isChanged = false;
        for (int j = 0; j < N - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                Swap(arr + j, arr + j + 1);
                isChanged = true;
            }
        }
        if(!isChanged) return; // 如果循环过程中没有变换则代表已经有序，后续循环可以不用做了
    }
}

复杂度

时间复杂度

最好情况： O(n)

最坏情况： O(n2)

平均复杂度：O(n2)

空间复杂度

O(1)

选择排序（Selection Sort）

这个选择排序曾经被我自己当做冒泡排序写出来过。。我好厉害呀（不要脸

废话部分

选择排序，顾名思义 看名字就知道了，要有选择。

那么究竟选择的是什么呢？

个人理解来说，选择的是最小值。即在剩余的数组中选择最小的值与当前值进行交换。

如果我记得没错的话，这个排序方法在数据结构课上有讲过，这个算法可以看成有序区为空，然后依次选择最小（最大）值按序放入有序区。

但是我的想法是从第一位开始，直接依次比较每一位，找到最小的数据，直接和当前位置进行交换，依次进行。

Show me code time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void SelectionSort(int *arr)
{
    for (int i = 0; i < N; i++)
    {
        int tmp = i; // tmp means temporary 记录下标
        for (int j = i + 1; j <= N - i; j++)
        {
            // 按顺序依次比较每一个元素和后边所有元素的大小，找到剩余元素的最小值，记录数组下标（也叫数组索引）
            if (arr[tmp] > arr[j])
            {
                tmp = j; // 找到最小的值的下标
            }
        }
        // swap(&arr[i], &arr[tmp]);
        if (i != tmp)
            Swap(arr + i, arr + tmp); // 交换当前扫描到的元素和记录下来的最小值下标对应的值
    }
}

插入排序（Insertion Sort）

废话部分

根据记忆和参考链接的内容，插入排序的思想是，从左向右遍历数组，对于每个元素，每次找到最合适的位置进行插入。

但是个人理解，和选择排序差不多，也是从第一位开始，依次对于每一位待排序元素在前边已排序元素中找到一个最适合自己的位置扔进去，然后后续内容直接平移数组。

要实现这个想法，可以对于已排序部分从右向左依次和待插入元素进行比较，如果不满足则直接移动，这样可以省去后期二次移动的麻烦

Show me code time

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 InsertionSort(int *arr)
{
    for (int i = 1; i < N; i++)
    {
        int tmp = arr[i];
        int tmpIndex = i - 1;
        // while(tmpIndex >= 0)
        // {
        //     if (tmp < arr[tmpIndex])
        //     {
        //         arr[tmpIndex + 1] = arr[tmpIndex];
        //     }
        //     tmpIndex--;
        // }
        for (int j = i - 1; j >= 0; j--)
        {
            if (tmp < arr[j])
            {
                arr[j + 1] = arr[j];
            }
            tmpIndex = j;
        }
        arr[tmpIndex] = tmp;
    }
}

参考链接

冒泡排序算法及其两种优化 : https://blog.csdn.net/yanxiaolx/article/details/51622286

十大经典排序算法（动图演示）: https://www.cnblogs.com/onepixel/p/7674659.html