冒泡排序

原理

从左到右依次比较相邻元素大小，将更大的元素放在右边，经过一组比较后最后一个元素一定是最大元素；

从头开始重新进行从左到右的比较，由于前一轮已经是最大的元素，故不需要参与比较，每轮结束都会减少一个参与比较的元素；

每轮结束都会得到一个最大值，并以从右往左从大到小确定元素的顺序，直到排序结束。

动图演示

冒泡排序

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void swap(int *a,int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void bubble_sort(int *arr, int n)
{
	int Cnt, Idx = 0;
	//n个数排n-1次
	for (Cnt = 0; Cnt < n - 1; Cnt++)
	{	//去除排序完成的末位数
		for (Idx = 0; Idx < n - Cnt - 1; Idx++)
		{
			if (arr[Idx] > arr[Idx + 1])
			{
				swap(arr, Idx, Idx + 1);
			}
		}
	}
}

算法分析

冒泡排序属于交换排序，是稳定排序。

平均时间复杂度为O(n²),最差为O(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
void swap(int *a,int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void selection_sort(int arr[], int len) 
{
    int i,j;

        for (i = 0 ; i < len - 1 ; i++) 
    {
        int min = i;
        for (j = i + 1; j < len; j++){
            if (arr[j] < arr[min])    //找到目前最小值
            min = j;    //记录最小值
            swap(&arr[min], &arr[i]);}   //做交换
    }
}

算法分析

选择排序是一种简单直观的排序算法；

任何数据的时间复杂度都是O(n²) ;

空间复杂度为O(1)。

插入排序

原理

插入排序类似于给扑克牌排序。通过构建有序数列，将未排序的元素从后往前找位置并插入。

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

动图演示

insertionSort

代码

1
2
3
4
5
6
7
8
9
10
11
12
void insertion_sort(int arr[], int len){
        int i,j,key;
        for (i=1;i<len;i++){
                key = arr[i];
                j=i-1;
                while((j>=0) && (arr[j]>key)) {
                        arr[j+1] = arr[j];
                        j--;
                }
                arr[j+1] = key;
        }
}

算法分析

**平均时间复杂度为O(n²)**，最差为O(n²)，最好为O(n);

空间复杂度O(1)。

希尔排序

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

原理

先将整个待排序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

子序列的构成不是简单地“逐段分割”，将相隔某个增量的记录组成一个子序列，让增量逐趟缩短，直到增量为 1 为止。

将数组中每间隔为d的元素划分为同一组，然后对每一组使用插入排序。d有多个值，但要求最后一个值为1，即最后一次要进行插入排序。例如数组：2 9 1 3 6 3，如果d为2，那么2、1、6为一组；9、3、3为一组；对每组都进行插入排序。

动图演示

希尔排序

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void shell_sort(int *arr, int len){
	int i, j, gap, tmp;
    //"len >> 1"表示将"len"二进制的值右移一位，相当于将"len"除以2并取整
	for (gap = len >> 1; gap > 0; gap = gap >> 1){//gap依次减小
		for (i = gap; i < len; i++){//每次插排右边待插入的数
			tmp = arr[i];
			//这段就是插排，只是每次和前面相距gap长的数比，不是和前面每一个比
			for (j = i; j >= gap && arr[j - gap] > tmp; j -= gap)//注意边界条件的判断
			{
				arr[j] = arr[j - gap];
			}
			arr[j] = tmp;
		}
	}
}

算法分析

*时间复杂度为O(nlogn)**，比O(n²) 更优；

空间复杂度为常数阶 O(1)。

快速排序

快速排序是冒泡排序的改进版，使用了分治法。它也属于交换排序，通过元素之间的位置交换来达到排序的目的。

原理

从数列中挑出一个元素，称为 “基准”;

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作；

递归地把小于基准值元素的子数列和大于基准值元素的子数列排序；

示例

选择基准并分区操作：

快速排序1

对子数列递归排序：

快速排序2

动图演示

快速排序

代码

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
void QuickSort(int arr[], int start, int end)
{
	int i = start, j = end;
	int temp = arr[start];  //基准数
	if (i < j)
	{
		while (i < j)
		{
			while (i<j && arr[j] >= temp)  //从右向左，找小于temp的
			{
				j--;
			}
			if (i < j)     //填坑
			{
				arr[i] = arr[j];
				i++;
			}
 
			while (i<j && arr[i] < temp)  //从左向右，找大于temp的
			{
				i++;
			}
			if (i < j)      //填坑
			{
				arr[j] = arr[i];
				j--;
			}
		}
		arr[i] = temp;                  //把基准数放到 i=j 位置
		QuickSort(arr, start, i - 1);   //左半部分快排 
		QuickSort(arr, i + 1, end);     //右半部分快排
	}
}

算法分析

*平均时间复杂度：O(nlogn)**；最坏情况：O(n²)；

快速排序O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

空间复杂度：O (logn)。

归并排序

归并排序是建立在归并操作上的有效排序算法，以分治法为特点。

原理

将两个或两个以上的有序表组合成一个新的有序表，简单操作就是将这几个有序表中的最小元素移入新数据段的末尾，使之有序。

假如初始序列含有 n 个记录，则可以看成是 n 个有序的子序列，每个子序列的长度为 1。然后两两归并，得到 n/2 个长度为 2 或 1 的有序子序列；再两两归并，……，如此重复，直到得到一个长度为 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
26
27
28
29
30
31
32
33
34
35
36
void merge(int *arr, int L, int M, int R){
	int LEFT_SIZE = M - L + 1;
	int RIGHT_SIZE = R - M;
	int *left = (int *)malloc(LEFT_SIZE * sizeof(int));//开辟左子数组
	memset(left, 0, LEFT_SIZE * sizeof(int));
	int *right = (int *)malloc(RIGHT_SIZE * sizeof(int));//开辟右子数组
	memset(right, 0, RIGHT_SIZE * sizeof(int));

	int i, j, k;
	// 以 M 为分割线，把原数组分成左右子数组
	for (i = L; i <= M; i++) {left[i - L] = arr[i];}
	for (j = M + 1; j <= R; j++) {right[j - M - 1] = arr[j];}
	// 再合并成一个有序数组（从两个序列中选出最小值依次插入）
	i = 0; j = 0; k = L;
	while (i < LEFT_SIZE && j < RIGHT_SIZE){arr[k++] = left[i] < right[j] ? left[i++] : right[j++];}
	while (i < LEFT_SIZE) {arr[k++] = left[i++];}
	while (j < RIGHT_SIZE) {arr[k++] = right[j++];}

	//释放内存
	free(left);
	left = NULL;
	free(right);
	right = NULL;
}

void merge_sort(int *arr, int L, int R){
	if (L == R) return; //递归终止条件，分无可分
	// 将 arr[L..R] 平分为 arr[L..M] 和 arr[M+1..R].
	int M = (L + R) >> 1;
	//（分别递归地将子序列排序为有序数列）先分割到最小子区间，再反过来一步步合并成一个完整有序数组
	merge_sort(arr, L, M);//左边
	merge_sort(arr, M + 1, R);//右边
	// 将两个排序后的子序列再归并到 arr
	merge(arr, L, M, R);
}

算法分析

归并排序是稳定排序，它和选择排序一样，性能不受输入数据的影响，但表现比选择排序更好；

时间复杂度始终为 O(nlogn)，但它需要额外的内存空间；

空间复杂度为 O(n)。

堆排序

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

  1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
  2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列。

原理

实现堆排序需要解决两个问题：

  • 如何将一个无序序列构建成堆？
  • 如何在输出堆顶元素后，调整剩余元素成为一个新的堆？

以升序为例，算法实现的思路为：

  1. 建立一个 build_heap 函数，将数组 tree[0,…n-1] 建立成堆，n 表示数组长度。函数里需要维护的是所有节点的父节点，最后一个子节点下标为 n-1，那么它对应的父节点下标就是 (n-1-1)/2。
  2. 构建完一次堆后，最大元素就会被存放在根节点 tree[0]。将 tree[0] 与最后一个元素交换，每一轮通过这种不断将最大元素后移的方式，来实现排序。
  3. 而交换后新的根节点可能不满足堆的特点了，因此需要一个调整函数 heapify 来对剩余的数组元素进行最大堆性质的维护。如果 tree[i] 表示其中的某个节点，那么 tree[2i+1] 是左孩子，tree[2i+2] 是右孩子，选出三者中的最大元素的下标，存放于 max 值中，若 max 不等于 i，则将最大元素交换到 i 下标的位置。但是，此时以 tree[max] 为根节点的子树可能不满足堆的性质，需要递归调用自身。

动图演示

堆排序

代码

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
//将数组转化成大顶堆/小顶堆的形式，然后每次把堆顶元素放在数组最后，再堆化，循环至数组完全有序
//已知父节点下标i,则左子节点下标2*i+1,右子节点下标2*i+2；
//已知孩子节点下标i,则其父节点下标为(i-1)/2 结果直接取整(小数位丢弃)

//调整剩余元素，构成大顶堆(全是根据遍历父节点来调整每一个二叉部分)
void heapify(int tree[], int n, int parent){
	//n 表示序列长度，i 表示父节点下标
	if (parent >= n) return;
	//左侧子节点下标
	int left = 2 * parent + 1;
	//右侧子节点下标
	int right = 2 * parent + 2;

	int max = parent;
	if (left < n && tree[left] > tree[max]) max = left;
	if (right < n && tree[right] > tree[max]) max = right;
	if (max != parent){//如果最大值不是当前父节点，则交换最大值到上面，并继续递归调用调整下面相连的子二叉树
		swap(tree, max, parent);
		heapify(tree, n, max); //递归调整被交换的下一个父亲节点
	}
}

//将数组下标当作完全二叉树每个节点下标来处理（从左至右，从上至下排序号）
void build_heap(int tree[], int n){
	//树最后一个节点下标
	int last_node = n - 1;
	//确定最后一个节点 的 父节点下标
	int parent = (last_node - 1) / 2;
	//开始从最后一个父节点开始，往前遍历每个父节点，并调整值的顺序，最终当前最大值会到堆顶
	int i;
	//第一次构建大顶堆需要遍历所有父节点，后面每次调整只要传入根节点即可（里面会递归调整发生值改变的所在子二叉树）
	for (i = parent; i >= 0; i--){
		heapify(tree, n, i);
	}
}

void heap_sort(int tree[], int n){
	//构建堆
	build_heap(tree, n);
	int i; //i代表最后一个元素下标，也是当前未调整的数组长度
	//每次将堆化好的堆顶元素放到最后，并调整剩下的元素
	for (i = n - 1; i >= 0; i--){
		// 将堆顶元素与最后一个元素交换
		swap(tree, i, 0);
		//调整大顶堆（剩下的元素），永远保证大顶堆有序
		heapify(tree, i, 0); //构建好堆以后 每次调整，只要传入根节点0即可
	}
}

算法分析

堆排序是不稳定排序，适合数据量较大的序列；

**平均时间复杂度为Ο(nlogn)**；

空间复杂度为O(1)。

计数排序

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

原理

找出待排序数组的最大最小元素

统计数组中每个值为i的元素出现的次数，存入数组C的第i项；

统计完成后，将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去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
42
43
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

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

void counting_sort(int *ini_arr, int *sorted_arr, int n) {
        int *count_arr = (int *) malloc(sizeof(int) * 100);
        int i, j, k;
        for (k = 0; k < 100; k++)
                count_arr[k] = 0;
        for (i = 0; i < n; i++)
                count_arr[ini_arr[i]]++;
        for (k = 1; k < 100; k++)
                count_arr[k] += count_arr[k - 1];
        for (j = n; j > 0; j--)
                sorted_arr[--count_arr[ini_arr[j - 1]]] = ini_arr[j - 1];
        free(count_arr);
}

int main(int argc, char **argv) {
        int n = 10;
        int i;
        int *arr = (int *) malloc(sizeof(int) * n);
        int *sorted_arr = (int *) malloc(sizeof(int) * n);
        srand(time(0));
        for (i = 0; i < n; i++)
                arr[i] = rand() % 100;
        printf("ini_array: ");
        print_arr(arr, n);
        counting_sort(arr, sorted_arr, n);
        printf("sorted_array: ");
        print_arr(sorted_arr, n);
        free(arr);
        free(sorted_arr);
        return 0;
}

算法分析

当输入的元素是 n 个 0 到 r 之间的整数时，它的时间复杂度为 O(n + r)。计数排序不是比较排序。计数排序是稳定排序，适合数据范围不显著大于数据数量的序列。

占用额外内存，还需要 r 个桶，因此空间复杂度是 O(n+r)，计数排序快于任何比较排序算法，但这是通过牺牲空间换取时间来实现的。

桶排序

桶排序是计数排序的升级版。

原理

假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序。最后拼接非空的桶内数据，得到最终结果。

动图演示

桶排序

代码

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
void bucket_sort(int arr[], int n, int r) {
    if (arr == NULL || r < 1) return;

    // 根据最大/最小元素和桶数量，计算出每个桶对应的元素范围
    int max = arr[0], min = arr[0];
    int i, j;
    for (i = 1; i < n; i++) {
        if (max < arr[i]) max = arr[i];
        if (min > arr[i]) min = arr[i];
    }
    int range = (max - min + 1) / r + 1;

    // 建立桶对应的二维数组，一个桶里最多可能出现 n 个元素
    int buckets[r][n];
    memset(buckets, 0, sizeof(buckets));
    int counts[r];
    memset(counts, 0, sizeof(counts));
    for (i = 0; i < n; i++) {
        int k = (arr[i] - min) / range;
        buckets[k][counts[k]++] = arr[i];
    }

    int index = 0;
    for (i = 0; i < r; i++) {
        // 分别对每个非空桶内数据进行排序，比如计数排序
        if (counts[i] == 0) continue;
        counting_sort(buckets[i], counts[i]);
        // 拼接非空的桶内数据，得到最终的结果
        for (j = 0; j < counts[i]; j++) {
            arr[index++] = buckets[i][j];
        }
    }
}

算法分析

桶排序是稳定排序，但仅限于桶排序本身，假如桶内排序采用了快速排序之类的非稳定排序，那么就是不稳定的；

桶排序的时间复杂度和桶内的排序方法相关。

桶排序占用额外内存，需要创建 r 个桶的额外空间，以及 n 个元素的额外空间，所以桶排序的空间复杂度为 O(n+r)；

基数排序

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

原理

基数排序将整数每一位拆开，从个位数向高位展开，依次比较并排序。

示例

第一次排序比较个位：

基数排序1

第二次排序比较十位，由于在第一次排序中确定了个位的大小排序位置为从上往下从小到大，第二次比较后，同一个桶中的结果排序一定是正确的，因为桶中的元素十位相同，个位排列从上往下从小到大。排序完成后十位后面有序：

基数排序2

第三次排序比较百位，百位后面有序：

基数排序3

而最后一次的时候进行处理的时候，千位有的数字需要补零，这次完毕后后千位及以后都有序，即整个序列排序完成。

基数排序4

动图演示

基数排序

代码

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
// 基数，范围0~9
#define RADIX 10

void radix_sort(int arr[], int n) {
    // 获取最大值和最小值
    int max = arr[0], min = arr[0];
    int i, j, l;
    for (i = 1; i < n; i++) {
        if (max < arr[i]) max = arr[i];
        if (min > arr[i]) min = arr[i];
    }
    // 假如序列中有负数，所有数加上一个常数，使序列中所有值变成正数
    if (min < 0) {
        for (i = 0; i < n; i++) arr[i] -= min;
        max -= min;
    }
    // 获取最大值位数
    int d = 0;
    while (max > 0) {
        max /= RADIX;
        d ++;
    }
    int queue[RADIX][n];
    memset(queue, 0, sizeof(queue));
    int count[RADIX] = {0};
    for (i = 0; i < d; i++) {
        // 分配数据
        for (j = 0; j < n; j++) {
            int key = arr[j] % (int)pow(RADIX, i + 1) / (int)pow(RADIX, i);
            queue[key][count[key]++] = arr[j];
        }
        // 收集数据
        int c = 0;
        for (j = 0; j < RADIX; j++) {
            for (l = 0; l < count[j]; l++) {
                arr[c++] = queue[j][l];
                queue[j][l] = 0;
            }
            count[j] = 0;
        }
    }
    // 假如序列中有负数，收集排序结果时再减去前面加上的常数
    if (min < 0) {
        for (i = 0; i < n; i++) arr[i] += min;
    }
}

算法分析

基数排序是稳定排序，适用于关键字取值范围固定的排序；

假设给定 n 个数，它的最高位数是 d，基数（也就是桶的个数）为 r，那么可以这样理解：共进行 d 趟排序，每趟排序都要对 n 个数据进行分配，再从 r 个桶中收集回来。所以算法的时间复杂度为 O(d(n+r))，在整数的排序中，r = 10，因此可以简化成 O(dn)，是线性阶的排序。

需要创建 r 个桶的额外空间，以及 n 个元素的额外空间，所以基数排序的空间复杂度为 O(n+r)。

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

  • 基数排序：根据键值的每位数字来分配桶，适用于非负整数间的排序，且最大值和最小值尽可能接近；
  • 计数排序：每个桶只存储单一键值，适用于最大值和最小值尽可能接近的排序；
  • 桶排序：每个桶存储一定范围的数值，适用于元素尽可能分布均匀的排序。


参考资料:

【基础知识】十大排序算法详解（C语言版）_大排序算法 c语言-CSDN博客

1.0 十大经典排序算法 | 菜鸟教程 (runoob.com)