十大经典排序算法及其C语言实现--带动图展示

排序算法大概算起来有以下十种

一、冒泡排序（Bubble Sort）

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

1.1、动画演示

1.2、代码

void swap(int* a, int* b) {
     int temp = *a;
     *a = *b;
     *b = temp;
}

void Bubble_sort(int *nums, int length) {
    for (int i=1; i<length; i++) {
        for (int j=0; j<length-i; j++) {
            if (nums[j] > nums[j+1]) {
                swap(&nums[j],&nums[j+1]);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1.3、评价

最快就是当输入的数据是正序时。

最慢就是当输入的数据是反序时。

由于复杂度很高，所以数据量大时几乎不可以使用，但是算法简单，且为原地排序算法。

二、选择排序（Selection Sort）

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

2.1、动画演示

2.2、代码

void Selection_sort(int *nums, int length) {
    for (int i=0; i<length-1; i++) {
        int flag = i;
        for (int j=i+1; j<length; j++) {
            if (nums[j] < nums[flag]) flag = j;
        }
        swap(&nums[i],&nums[flag]);
    }
}
1
2
3
4
5
6
7
8
9

2.3、评价

优势是简单直观，选一个最小的放在前面

劣势是时间复杂度高，不适合大规模数据，不适合部分排序

三、插入排序（Insertion sort）

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

3.1、动画演示

3.2、代码

/* 写法1 */
void Insert_sort(int *nums, int length) {
    for (int i=1; i<length; i++) {
        for (int j=i; j>=1; j--) {
            if (nums[j] < nums[j-1]) {
                swap(&nums[j],&nums[j-1]);
            } else {
                break;
            }
        }
    }
}

/* 写法2 */
void Insert_sort2(int *nums, int length) {
    for (int i=1; i<length; i++) {
        int temp = nums[i];
        int j;
        for (j=i; j>=1 && nums[j-1] > temp; j--) {
            nums[j] = nums[j-1];
        }
        nums[j] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3.3、评价

插入排序是稳定的排序算法，即相同元素的相对位置在排序后不会改变。

时间复杂度高，不适合大规模数据，且每次插入都需要大量移动数据。

四、希尔排序（Shell sort）

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先选定一个整数gap，把待排序文件中所有元素分成gap组，即所有距离为gap的分在同一组内，并对每一组内的元素进行直接插入排序（本质是进行预排序，使数组更接近有序，目的是使最后一次直接插入排序提高效率）。然后取gap=gap/2或者gap=gap/3+1重复上述分组和排序的工作。当gap到达1时，数组是已经接近有序的，而对于直接插入排序在顺序有序或者接近顺序有序的数组内的时间复杂度为O(N)，效率很高，当gap=1，即以一个元素为一组，就相当于对整个数组进行直接插入排序了。得到的就是有序数组了。也就排好序了。

4.1、动画演示

1. 选择增量序列： 首先确定一个增量序列，这个序列决定了每次分割的步长。常见的增量序列有 Hibbard 增量序列、Sedgewick 增量序列等。增量序列的选择对算法的效率有很大影响。
2. 分割成子序列： 将原始序列分割成若干个子序列，每个子序列包含距离为增量序列中某个值的元素。通常是从第一个元素开始，每隔增量序列中的一个值取一个元素，这样依次形成子序列。
3. 对各个子序列进行插入排序： 对每个子序列分别进行插入排序。即对每个子序列内部的元素进行排序，使得子序列内部基本有序。这一步通常采用的是简单插入排序。
4. 逐步缩小增量： 重复上述步骤，但是每次使用的增量都会逐步缩小，直到增量为 1。
5. 最后一次插入排序： 当增量为 1 时，整个序列会被分割成一个个相邻的子序列，此时进行最后一次插入排序。这时候，相邻元素之间的距离变为 1，即实现了对整个序列的最终排序。

4.2、代码

void Shell_sort(int *nums, int length) {
    for (int gap = length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < length; i++) {
            int temp = nums[i];
            int j;
            for (j = i; j >= gap && nums[j - gap] > temp; j -= gap) {
                nums[j] = nums[j - gap];
            }
            nums[j] = temp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

4.3、评价

希尔排序的时间复杂度取决于增量序列的选择，一般情况下为 O(n^2) 到 O(n^(3/2)) 之间，其中 n 是数组的长度。尽管希尔排序的时间复杂度不稳定，但在实际应用中，其性能通常比简单插入排序要好很多，特别是对于中等大小的数组。

五、归并排序（Merge sort）

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

• 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）
• 自下而上的迭代

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

5.1、动画演示

5.2、代码

递归实现

void Merge(int *nums, int l, int r, int *tmp) {
    if (l >= r) return;
    int mid = (l + r) / 2;

    // 先分
    Merge(nums,l,mid,tmp);
    Merge(nums,mid+1,r,tmp);

    // 再合
    int l1 = l;
    int r1 = mid;
    int l2 = mid + 1;
    int r2 = r;
    int pos = 0;

    while (l1 <= r1 && l2 <= r2) {
        if (nums[l1] < nums[l2]) {
            tmp[pos++] = nums[l1++];
        } else {
            tmp[pos++] = nums[l2++];
        }
    }

    while (l1 <= r1) {
        tmp[pos++] = nums[l1++];
    }

    while (l2 <= r2) {
        tmp[pos++] = nums[l2++];
    }

    memcpy(nums+l,tmp,sizeof(int) * (pos));
}

void Merge_sort(int *nums, int length) {
    int* tmp = (int*)malloc(sizeof(int) * length);
    Merge(nums,0,length-1, tmp);
}
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

非递归实现

void MergeSortNonR(int *nums, int length) {
    int* tmp = (int*)malloc(sizeof(int) * length);
    // gep为每次需要归并的元素个数
    for (int gap = 1; gap < length; gap *= 2) {
        for (int i=0; i<length; i += 2*gap) {
            int l1 = i;
            int r1 = i + gap - 1;
            int l2 = i + gap;
            int r2 = i + 2 * gap - 1;
            r2 = r2 < length-1 ? r2 : length - 1;
            int pos = 0;

            while (l1 <= r1 && l2 <= r2) {
                if (nums[l1] < nums[l2]) {
                    tmp[pos++] = nums[l1++];
                } else {
                    tmp[pos++] = nums[l2++];
                }
            }

            while (l1 <= r1) {
                tmp[pos++] = nums[l1++];
            }

            while (l2 <= r2) {
                tmp[pos++] = nums[l2++];
            }
            memcpy(nums + i, tmp, sizeof(int) * (pos));
        }
    }
}
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

5.3、评价

归并排序是一种非常有效的排序算法。稳定的时间复杂度：归并排序的时间复杂度为 O(n log n)，其中 n 是待排序序列的长度。这意味着在最坏、平均和最好情况下，归并排序的时间复杂度都保持在这个级别，这使得它在各种情况下都能表现出良好的性能。稳定性：归并排序是一种稳定的排序算法，即相同元素的相对位置不会改变。这意味着如果原始序列中存在相同的元素，经过归并排序后，它们的相对顺序将保持不变。适合大规模数据：归并排序对于大规模数据的排序效率较高，因为其时间复杂度相对较低且稳定，不会受到数据分布的影响。

六、快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

6.1、动画演示

1. 从数列中挑出一个元素，称为 “基准”（pivot）;
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

6.2、代码

6.2.1、hoare法

void Quick(int *nums, int l, int r) {
    if (l >= r) return;

    int begin = l;
    int end = r;
    while (l < r) {
        while (l < r && nums[r] >= nums[begin]) r--;
        while (l < r && nums[l] <= nums[begin]) l++;
        swap(&nums[l], &nums[r]);
    }
    swap(&nums[begin],&nums[l]);

    Quick(nums,begin,l-1);
    Quick(nums,l+1,end);
}

void Quick_sort(int *nums, int length) {
    Quick(nums,0,length-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这种方法容易出bug

1. right找小和left找大的过程中，要保证left < right，否则可能出现数组越界，比如1,9,6,4,2,7,8,2 ；右边的值都比key大，会导致越界。
2. a[right] >= a[keyI]或者a[left] <= a[keyI]时，才能–right或者++left；如果是a[right] > a[keyI]或者a[left] < a[keyI]可能出现死循环，比如a[left] == a[right] == key时，交换完后不进入内部while，外部while陷入死循环。

6.2.2、挖坑法

void Quick(int *nums, int l, int r) {
    if (l >= r) return;

    int hole = l;
    int key = nums[l];

    while (l < r) {
        while (l < r && nums[r] >= key) r--;
        nums[hole] = nums[r];
        hole = r;

        while (l < r && nums[l] <= key) l++;
        nums[hole] = nums[l];
        hole = l;
    }

    nums[hole] = key;

    Quick(nums,l,hole-1);
    Quick(nums,hole+1,r);
}

void Quick_sort(int *nums, int length) {
    Quick(nums,0,length-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

6.2.3、前后指针法

void Quick(int *nums, int l, int r) {
    if (l >= r) return;

    int prev = l;
    int cur = l+1;
    int key = l;
    while (cur <= r) {
        if (nums[cur] < nums[key] && ++prev != cur) {
            swap(&nums[prev],&nums[cur]);
        }
        ++cur;
    }

    Quick(nums,l,prev-1);
    Quick(nums,prev+1,r);
}

void Quick_sort(int *nums, int length) {
    Quick(nums,0,length-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

6.3、评价

快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序。实际上确实非常快，使用场景也非常广泛

七、堆排序（Heap sort）

利用堆这种数据结构进行排序，堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

• 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；

• 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

7.1、动画演示

7.2、代码

// 调整堆，将以root为根的子树调整为最大堆
void heapify(int arr[], int n, int root) {
    int largest = root; // 初始化根节点为最大值
    int left = 2 * root + 1; // 左子节点
    int right = 2 * root + 2; // 右子节点

    // 如果左子节点比根节点大，则更新最大值
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 如果右子节点比根节点大，则更新最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大值不是根节点，则交换根节点和最大值节点，并递归调整子树
    if (largest != root) {
        swap(&arr[root], &arr[largest]);
        heapify(arr, n, largest);
    }
}

// 堆排序函数
void heapSort(int arr[], int n) {
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 依次取出堆顶元素，调整堆
    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]); // 将当前堆顶元素（最大值）与数组末尾元素交换
        heapify(arr, i, 0); // 调整堆
    }
}
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

7.3、评价

堆排序不稳定，但是时间复杂度稳定，适用于大规模数据。

• 堆排序通常需要随机访问数组元素，对于链式结构来说不太适用，因此在链表实现中可能效率较低。

• 如果待排序的数据分布不均匀，堆排序的性能可能会下降，因为堆排序是一种基于比较的排序算法，而数据分布不均可能导致比较次数增多。

• 相对于其他简单的排序算法（如插入排序、冒泡排序），堆排序的实现相对复杂，需要对堆的概念和操作有一定的了解。

八、计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

8.1、动画演示

8.2、代码

void Counting_sort(int *nums, int length) {
    int *cache = (int *)malloc(sizeof(int) * 20);
    memset(cache,0,sizeof(int) * 20);

    for(int i=0;i<length;i++) {
        cache[nums[i]] ++;
    }

    int pos = 0;
    for(int i=0;i<20;i++) {
        while (cache[i]) {
            nums[pos++] = i;
            cache[i]--;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

8.3、评价

计数排序具有线性复杂度，简单易实现，对于范围有限的数据非常友好。

九、桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

• 在额外空间充足的情况下，尽量增大桶的数量
• 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

其主要是先把序列中的数据划分为一个个的范围，每个范围相当一个桶，将数据放入桶中，每个桶分别进行排序，然后取出拼接即可。计数排序不适用于序列中max-min范围较广或者序列中的数据不是整数的情况，但是桶排序没有这些限制，其主要步骤是将数据放入桶中，桶中的数据自己排序。

桶排序是一种针对大数据的排序方式,数据量越大,桶排序的优势越大

十、基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

10.1、动画演示

10.2、评价

基数排序适用于待排序元素为非负整数，并且数值范围不是很大的情况。它将整数按位数划分，并依次进行排序，适用于范围较小的整数排序。

基数排序可扩展到外部排序，即处理大规模数据的排序问题。例如，可以将数据分块读入内存，然后使用基数排序对每个数字位进行排序，再将结果写回磁盘。

基数排序的这些优势使得它在某些特定的排序需求中具有较好的性能和适用性。然而，基数排序的缺点是需要额外的存储空间来存储中间结果，且对待排序元素的数据类型有一定要求（通常是非负整数）。

基数排序不需要比较