前言

​ 在我刚学数据结构的时候，我觉得这些算法很死板，大不了直接背会了不就完了。但后来我发现我根本记不住，过一阵子就会忘记，更别提算法的思想了。所以我总结这十大基本算法。其中代码只是载体，最重要的是其中的思想。这些思想无一不展现了早期计算机科学家的智慧。当然对于我来说即使是公认为最简单的冒泡排序也是很难的。但我还是觉得这些东西还是很值得琢磨的。

​ 10大排序简称"堆雪插炮击，统计快归西"，分别为堆排序、选择排序、插入排序、冒泡排序、基数排序、桶排序、计数排序、归并排序、希尔排序。

冒泡排序

主要思想

冒泡排序字如其名不做过多解释，假设我们使用数组来作为载体，其中数组长度为MAX。

大体思路（排序从小到大): 首先对数组遍历，使其每一次遍历都会使最大的元素到数组的末尾，实现方法就是将像第一次样的遍历，只不过其中上一次最大的已经是数组中最大的，这一次就不用将其考虑在内，比较相邻两个元素，将较大的往后移。

实现方式

这里我使用到了随机数，为了避免运行时的偶然性，其中数组大小可以更改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
49
50
51
52
53
54
55
56
#include	<stdio.h>
#include	<stdlib.h>
#include	<time.h>
#define MAX 10
void 
swap(int *,int *);
void
bubble(int *,int );
void
print_arr(int *,int );
main()
{
	srand((unsigned)time(NULL));
	int 	i,n;
	int a[MAX] = {0};
	
	for(i=0;i<MAX;i++){
		a[i] = rand()%100; //生成0-99的随机数
	}
	n=MAX;
	print_arr(a,n);
	bubble(a,n);
	printf("after bubble sort\n");
	print_arr(a,n);
		
	
	return 0;
}
void
swap(int *a,int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void
bubble(int a[],int n)
{
	int 	i,j;
	for(i = 0;i<n;i++){
		for(j = 0;j<n-i-1;j++){
			if(a[j]>a[j+1]){
				swap(&a[j],&a[j+1]);
			}
		}
	}
}
				
void
print_arr(int a[],int n)
{
	int	 i;
	for(i=0;i<n;i++)
		printf("a[i] = %d\n",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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include	<stdio.h>
#include	<stdlib.h>
#include	<time.h>
#define MAX 10
void
swap(int *,int *);
void
select_sort(int *,int );
void
init_arr(int *,int );
void
print_arr(int *,int );
int
main()
{
	int 	a[MAX]={0};
	int 	n = MAX;
	init_arr(a,n);
	print_arr(a,n);
	select_sort(a,n);
	printf("----after select sort----\n");
	print_arr(a,n);
}
void
init_arr(int a[],int n)
{
	srand((unsigned)time(NULL));
	int 	i;
	for(i=0;i<n;i++)
		a[i] = rand()%100;

}	
void
print_arr(int a[],int n)
{
	int	 i;
	for(i=0;i<n;i++)
		printf("a[%d] = %d\n",i,a[i]);
}
void
swap(int *a,int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
void
select_sort(int a[],int n)
{
	int 	i,j;
	for(i=0;i<n-1;i++){//由于前n-1个元素都是排好序的最小值，所以最后一个元素一定是最大
		int min_position = i;	//把当前位置当做最小值下标
		for(j = i+1;j<n;j++){
			 if(a[min_position]>a[j])
				min_position = j;
		}
		swap(&a[i],&a[min_position]);
	}
}

插入排序

主要思想

​ 插入排序的工作方式是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

实现方式

  1. 外层循环 for(i=0;i<n-1;i++)：这个循环是为了遍历数组中的每一个元素，除了最后一个。这是因为最后一个元素已经“在其应该在的位置上”。
  2. if(a[i]>a[i+1])：这个判断是为了找到不正确的元素对。换句话说，它找到当前元素与其后面的元素之间的不匹配。
  3. 内部循环 for(j=i;j>=0;j--)：这个循环的目的是为了找到不正确的元素应该插入的位置。
  4. a[j+1] = a[j];：这个语句将所有大于或等于tmp的元素向后移动一位，为tmp腾出空间。
  5. a[j+1] = tmp;：这个语句将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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include	<stdio.h>
#define 	MAX 10
void
insert_sort(int *,int );
void
init_arr(int *,int );
void
print_arr(int *,int);

int 
main()
{
	int 	a[MAX]={0};
	int 	n = MAX;
	init_arr(a,n);
	print_arr(a,n);
	insert_sort(a,n);
	printf("----after sort----\n");
	print_arr(a,n);
}
void
init_arr(int a[],int n)
{
	srand((unsigned)time(NULL));
	int 	i;
	for(i=0;i<n;i++)
		a[i] = rand()%100;

}	

void
insert_sort(int a[],int n)
{
	int 	i,j;
	for(i=0;i<n-1;i++){
		if(a[i]>a[i+1]){//找到合适的位置插入
			int tmp = a[i+1];
			for(j=i;j>=0;j--){//不要忘记等于零的情况
				if(a[j]<tmp) break;
				else a[j+1] = a[j];	
			}
			a[j+1] = tmp;//到合适的位置
		}
	}
}
			
void
print_arr(int a[],int n)
{
	int	 i;
	for(i=0;i<n;i++)
		printf("a[%d] = %d\n",i,a[i]);
}

希尔排序(缩小增量排序)

主要思想

先将整个待排序的记录序列分割成为若干子序列，使得每个子序列的元素较少，然后对各个子序列分别进行插入排序。随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

实现方式

该方法实质上是一种分组插入方法，是对插入排序的改进，总所周知插入排序在排序有序序列时性能最好，希尔排序就是使其排序时尽可能有序减少移动次数

比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。算法先将要排序的一组数按某个增量gap分成若干组，每组中记录的下标相差gap.对每组中全部元素进行排序，然后再用一个较小的增量对它进行分组，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。

一般的初次取序列的一半为增量，以后每次减半，直到增量为1。

我在实现希尔排序时是根据插入排序改进的，当希尔排序增量为1的时候自然就是插入排序。我把插入排序的逻辑添加了增量从而简化希尔排序的代码逻辑。其实呢，希尔排序逻辑就是确定增量，主要逻辑就是插入排序，我也不过是改变了插入排序的步长。例如原来的i++改为i=i+gap，这样理解起来是不是简单些呢。

希尔排序的增量

for(i=0;i<n-gap;i++)代表有序的个数，我选的增量是[n/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
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
#include	<stdio.h>
#define 	MAX	10
void
print_arr(int *,int);
void
init_arr(int *,int );
void
insert_sort_gap(int *,int ,int);
void
shell_sort(int *,int);
int
main()
{
	int 	a[MAX]={0};
	int 	n = MAX;
	init_arr(a,n);
	print_arr(a,n);
	shell_sort(a,n);
	printf("----after sort----\n");
	print_arr(a,n);
	return 0;
}
void
init_arr(int a[],int n)
{
	srand((unsigned)time(NULL));
	int 	i;
	for(i=0;i<n;i++)
		a[i] = rand()%100;

}
void
print_arr(int a[],int n)
{
	int	 i;
	for(i=0;i<n;i++)
		printf("a[%d] = %d\n",i,a[i]);
}
void
shell_sort(int a[],int n)
{
	int 	gap=n/2;
	while(gap){
		insert_sort_gap(a,n,gap);
		gap=gap/2;	
	}
}
void
insert_sort_gap(int a[],int n,int gap)
{
	int 	i,j;
	for(i=0;i<n-gap;i++){
		if(a[i]>a[i+gap]){//找到合适的位置插入
			int tmp = a[i+gap];
			for(j=i;j>=0;j-=gap){//不要忘记等于零的情况
				if(a[j]<tmp) break;
				else a[j+gap] = a[j];	
			}
			a[j+gap] = tmp;//到合适的位置
		}
	}
}

希尔排序和插入排序性能对比

接下来我们简单测试一下两种不同的排序的性能差多少。

这里排序10000个随机数,我们只需要更改MAX宏就可以。

这是插入排序代码改进(源代码去除输出):

这里是希尔排序代码改进(去除输出):

这里我们使用Linux系统自带的time命令来测试程序执行时间。

其中插入排序性能

其中希尔排序性能

性能的区别是不是很明显

快速排序

主要思想(默认升序)

​ 快速排序采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素pivot，利用pivot将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到将无序序列排列成有序序列。其实快速排序属于对于冒泡排序的改进，因为原理都是将较大的数往后移

实现方式

这里使用挖坑填坑的实现方法

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
47
48
49
50
51
52
53
54
#include	<stdio.h>
#include	<stdlib.h>
#include	<time.h>
#define MAX 10
void
print_arr(int *,int );
void
quick_sort(int *,int ,int);
int
main()
{
	srand((unsigned)time(NULL));
	int 	i,n;
	int a[MAX] = {0};
	
	for(i=0;i<MAX;i++){
		a[i] = rand()%100; //生成0-99的随机数
	}
	n=MAX;
	print_arr(a,n);
	quick_sort(a,0,n-1);
	printf("after sort\n");
	print_arr(a,n);
		
	
	return 0;
}
				
void
print_arr(int a[],int n)
{
	int	 i;
	for(i=0;i<n;i++)
		printf("a[%d] = %d\n",i,a[i]);
}
void
quick_sort(int a[],int low,int high)
{
	if(low<high){//递归判断条件 
		int 	pivot = a[low];
		int 	high_tmp = high;//暂存low和high变量
		int 	low_tmp = low;
		while(low_tmp<high_tmp){
			while(low_tmp<high_tmp&&pivot<=a[high_tmp]) high_tmp--;//这里不要忘记等于号 
			a[low_tmp] = a[high_tmp];
			while(low_tmp<high_tmp&&pivot>=a[low_tmp]) low_tmp++; 
			a[high_tmp]=a[low_tmp];
		}
		a[low_tmp] = pivot;
		quick_sort(a,low_tmp+1,high);
		quick_sort(a,low,low_tmp-1);	
	}
}

性能测试

使用和上面算法相同的测试方法，排序100000个随机数(不同电脑结果不同)

这里只是粗略的计算，大概比希尔排序快上一倍左右。

总结

从代码上很明显看出，算法消耗的时间主在分区上。你也可以明显发现快速排序不适合用于相等元素过的的情况。

归并排序(二路归并)

主要思想

​ 归并排序（Merge Sort）是一种基于分治思想的排序算法，它将一个大问题分解成小的部分来解决。在归并排序中，一个无序的数组被分割成若干个子数组，每个子数组都是有序的，然后再将这些有序的子数组合并成一个大的有序数组。什么又是分治思想呢，简单来讲就是将一个大问题分成无数小问题，通过解决小问题来解决大问题。该方法适用于问题规模小到一定程度就能解决的问题。

实现方式

  1. 分解：将当前待排序的区间一分为二（或者说，每次通过中点将待排序序列分割为两部分）。
  2. 这里使用merge_sort递归将数组分成最小。
  3. 然后使用merge合并两个有序数组
  4. 其中分成的子数组还是在原来的数组中，也就是说要合并的子数组在整个数组上是相邻的，所以我们需要确定其位置，又因为两个子数组长度未必相等，所以我们需要知道low：其中一个子数组的开始。mid：该子数组的结束，另一个子数组的开始high：另一个子数组的结束。

图示

​ 这里简单演示归并排序。

​

代码实现(递归)

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
#include	<stdio.h>
#include	<stdlib.h>
#define 	MAX 10
void
print_arr(int *,int );

void
merge(int a[],int low,int mid,int high);
void
merge_sort(int a[],int low,int high);
void
init_arr(int *,int );

int
main()
{
	int 	a[MAX]={0};
	int 	n = MAX;
	init_arr(a,n);
	print_arr(a,n);
	merge_sort(a,0,n-1);
	printf("----after sort----\n");
	print_arr(a,n);
	return 0;

}

void//治
merge(int a[],int low,int mid,int high){
	int 	*tmp = (int *)malloc(sizeof(int)*(high-low+1));
	int 	i = low;
	int 	j = mid+1;
	int 	k = 0;
	while(i<=mid&&j<=high){
		if(a[i]<=a[j])	tmp[k++] = a[i++];
		else		tmp[k++] = a[j++];
	}
	while(i<=mid) 		tmp[k++] = a[i++];
	while(j<=high)		tmp[k++] = a[j++];
	for(k=0,i=low;k<=high-low;k++){
		a[i++] = tmp[k];
	}
	free(tmp);
}
void//分
merge_sort(int a[],int low,int high){
	if(low<high){
		int 	mid = (low+high)/2;
		merge_sort(a,low,mid);
		merge_sort(a,mid+1,high);
		merge(a,low,mid,high);
	}
}
void
init_arr(int a[],int n)
{
	srand((unsigned)time(NULL));
	int 	i;
	for(i=0;i<n;i++)
		a[i] = rand()%100;

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

性能测试

这里依然测试排序100000个随机数。

总结

​ 归并排序，是分治法典型的例子，这里要注意有时候分割后的两个数组可能并不相等，当一遍数组比较完毕后要将后面的元素依次添加到辅助数组后。归并排序主要的空间都浪费在临时数组上，虽说其中涉及到递归但递归的空间复杂度在O(log⁡2n\log_2 n)，而数组需要O(n)。排序速度仅次于快速排序，从实验中可以明显看出。

​ 归并排序为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。由于需要开辟大量空间，所以更适合用于大规模数据情况。

堆排序

什么是堆

​ 堆(Heap)是计算机科学中一类特殊的数据结构，是最高效的优先级队列。堆通常是一个可以被看作一棵完全二叉树的数组对象。

堆的性质

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

  • 堆中某个结点的值总是不大于或不小于其父结点的值；
  • 堆总是一棵完全二叉树。

将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

堆的物理结构本质上是顺序存储的，是线性的。但在逻辑上不是线性的，是完全二叉树的这种逻辑储存结构。 堆的这个数据结构，里面的成员包括一维数组，数组的容量，数组元素的个数，有两个直接后继。

堆的定义如下：n个元素的序列k1,k2,ki,…,kn{k_1,k_2,k_i,…,k_n}当且仅当满足下关系时，称之为堆。

(ki≤k2ik_i \le k_{2i} 且 ki≤k2i+1k_i \le k_{2i+1})或者(ki≥k2ik_i \ge k_{2i} 且 ki≥k2i+1k_i \ge k_{2i+1})

其中 i=[1,n2]其中\ i=[1,\frac{n}{2}]

​ 若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,knk_1,k_2,…,k_n}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值)（或最大值）。

主要思想

​ 堆排序是选择排序的一种，主要思想都是将最选择最大(最小)值放在数组最大(最小)位置。

​ 主要步骤如：

  1. 将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。
  2. 将其与末尾元素进行交换，此时末尾就为最大值。
  3. 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

实现方法

  1. 创建一个堆H[0…n-1]；
  2. 把堆首（最大值）和堆尾互换；
  3. 把堆的尺寸缩小1，并调用max_heap方法调整堆；
  4. 重复步骤2，直到堆的尺寸为1。

这里介绍一下如何确定叶子节点，我们假设完全二叉树共有n层，那么所有的节点最多有 2n−12^n-1 个其中叶子节点最多有 2n−12^{n-1} 个，那么可以使用(2n−1)/2(2^n-1)/2 来确定非叶子节点个数，只有非叶子节点才有子节点。

代码实现

在heap_sort中第一个for循环目的是初始化堆也就是父节点大于子节点，其中max_heap目的是为了构建大顶堆，将较小元素向下坠。

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
#include	<stdio.h>
#include	<stdlib.h>
#include	<time.h>
#define MAX 10
void
max_heap(int a[],int low,int high);
void
heap_sort(int a[],int n);
void
swap(int *,int *);
void
init_arr(int *,int );
void
print_arr(int *,int );
int
main()
{
	int 	a[MAX]={0};
	int 	n = MAX;
	init_arr(a,n);
	print_arr(a,n);
	heap_sort(a,n);
	printf("----after sort----\n");
	print_arr(a,n);
	return 0;
}
void
init_arr(int a[],int n)
{
	srand((unsigned)time(NULL));
	int 	i;
	for(i=0;i<n;i++)
		a[i] = rand()%100;

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

void//将较小值向下坠
max_heap(int a[],int low,int high){
	int dad = low;
	int son = dad*2+1;
	while(son <=high){
		if(son+1<=high&&a[son] <a[son+1]) son++;
		if(a[son]>a[dad]){
			swap(&a[dad],&a[son]);
			dad = son;
			son = dad*2+1;
		}else 
			break;
	}
}
void
heap_sort(int a[],int n){
	int i;
	for(i = n/2-1;i>=0;i--)//初始化大顶堆
		max_heap(a,i,n-1);
	for(i=n-1;i>0;i--){//首尾交换继续堆排序
		swap(&a[0],&a[i]);
		max_heap(a,0,i-1);
	}
}

性能测试

总结

​ 堆排序是不稳定的排序方法，时间复杂度为O(nlogn)，空间复杂度为O(1)。堆排序适合用于n较大的情况，当n较小时，它并不优于简单排序（如插入排序）。堆排序的好处是，在给定的时间复杂度下，堆排序的常数项是所有基于比较的排序算法中最小的。此外，堆排序对于数据的局部特性并不敏感，因此它对于一些具有随机性的输入序列非常有效。

​ 但是，堆排序也有一些缺点。例如，堆排序在构建初始堆时，需要进行大量的比较和交换操作，这可能会导致算法在实际应用中的效率降低。此外，堆排序在处理具有某些特定模式的数据时，可能会表现出较差的性能。

​ 总的来说，堆排序是一种非常有效的排序算法，尤其适用于处理大量数据的情况。然而，在选择排序算法时，还需要考虑数据的特点以及实际需求，以便选择最适合的排序算法。

计数排序

主要思想

​ 计数排序是一种非基于比较的排序算法，于1954年由 Harold H. Seward 提出。它的基本思想是：对于给定的输入序列中的每一个元素x，确定该序列中值小于等于x的元素的个数，然后将x直接存放到最终的排序序列的正确位置上。

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

实现方式

  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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include	<stdio.h>
#include	<stdlib.h>
#include	<time.h>
#define MAX 10
void
counting_sort(int *,int );
void
init_arr(int *,int );
void
print_arr(int *,int );
int
main()
{
	int 	a[MAX]={0};
	int 	n = MAX;
	init_arr(a,n);
	print_arr(a,n);
	counting_sort(a,n);
	printf("----after sort----\n");
	print_arr(a,n);
	return 0;
}
void
init_arr(int a[],int n)
{
	srand((unsigned)time(NULL));
	int 	i;
	for(i=0;i<n;i++)
		a[i] = rand()%100;

}	
void
print_arr(int a[],int n)
{
	int	 i;
	for(i=0;i<n;i++)
		printf("a[%d] = %d\n",i,a[i]);
}
void
counting_sort(int a[],int n){
	int	i,j,min = a[0],max = a[0];
	int 	count = 0;
	for(i = 0;i<n;i++){
		if(a[i]>max) max = a[i];
		if(a[i]<min) min = a[i];
	}
	int 	length = max - min + 1;//确定临时数组长度
	int 	*tmp = (int *)malloc(sizeof(int )*length);//初始化临时数组
	for(i = 0;i<length;i++) 	tmp[i] = 0;
	for(i = 0;i<n;i++) 		tmp[a[i]-min]++;
	for(i = 0;i<length;i++){
		j = tmp[i];
		while(j>0){
			a[count++]= i+min; 
			j--;
		}
	}
	free(tmp);
}

总结

计数排序的优点主要包括：

  1. 速度快：对于一定范围内的整数排序，计数排序的时间复杂度为O(n+k)，其中k是整数的范围，比任何比较排序算法都要快。
  2. 稳定性好：计数排序是一种稳定的排序算法，即相等的元素在排序后保持原有的相对顺序。

然而，计数排序也存在一些缺点：

  1. 空间复杂度高：计数排序需要开辟一个额外的数组来存储计数结果，因此其空间复杂度为O(k)，其中k是整数的范围。当数据范围很大时，可能会造成空间的浪费。
  2. 适用范围有限：计数排序只能用于对整数进行排序，且数据范围需要提前确定。对于非整数或者数据范围不确定的输入，计数排序可能不适用。

​ 因此，选择计数排序还是其他排序算法，需要根据具体的需求和场景来决定。如果要求对一定范围内的整数进行快速排序，那么计数排序是一个不错的选择。

桶排序

主要思想

​ 桶排序是一种分布式排序算法，其基本思想是将待排序元素分到有限数量的桶中，然后分别对每个桶中的元素进行排序，最后按照顺序把各个桶中的元素合并得到最终的排序结果。

以下是桶排序的基本思想：

  1. 确定桶的数量： 首先确定分配的桶的数量，桶的数量可以根据待排序数据的分布情况来选择。
  2. 将元素分配到桶中： 遍历待排序的元素，根据元素的大小将其分配到相应的桶中。这个过程可以通过一个映射函数来实现，映射函数可以根据元素的大小将其分配到不同的桶中。
  3. 对每个桶中的元素进行排序： 对每个非空的桶中的元素进行排序。可以使用其他排序算法，如插入排序、快速排序等，或者递归地使用桶排序本身。
  4. 合并各个桶的结果： 将各个桶中排好序的元素按照顺序合并，得到最终的排序结果。

桶排序的优势在于可以有效地处理均匀分布的数据，而且在一定程度上可以实现并行化，因为每个桶可以独立地进行排序。然而，桶排序的性能受到数据分布的影响，如果数据分布不均匀，可能会导致某些桶的大小过大或过小，影响排序的效率。

实现方式

​ 实现桶排序需要根据数据的分布情况计算通的数量，其中每个桶总的元素需要使用排序算法排序，其中每个桶的大小并不是很好计算，使用数组只是简化了实现可能会大量浪费空间搞不好会数组越界，这里需要数学公式来映射数组中的元素与桶中的元素，其中桶的个数也需要映射函数。我们考虑每个元素的出现概率相同，那么我们要发挥桶排序的作用就要使桶的个数和桶中元素的个数大致相同。

​ 为了适应大数据的情况，我们动态计算桶的个数和中元素的个数其中桶中元素个数与桶的个数大致相同主要是为了能发挥桶中排序算法的性能和桶排序的性能。

​ 如何计算很简单就是开平方根，这里介绍一种近似计算平方根的算法，这里我们假设都是整数，如果涉及到浮点数可以考虑牛顿法，我们这里就不深入研究浮点数这种复杂情况。

​ 实现近似计算浮点数的算法如下：

1
2
3
4
5
6
7
8
9
int
sqrt_approximation(int x){
        long    approximation = x/2;
        while(approximation*approximation>x&&approximation>0){
                approximation--;
        }
        return approximation;
}

​ 这里有一点需要注意其中我使用了隐式强制转换，是应为平方很容易造成数据溢出。

​ 当划分完区域时我们明显能发现其中每个桶中的元素个数并不相同。可能有重复的元素出现，其实桶中的元素很难确定的，为了减少内存浪费，我们使用链表这种数据结构来作为桶中的元素。当然为了简单起见，我们使用冒泡排序对桶中的数据排序，用冒泡排序排序链表。其实还是很容易的因为冒泡排序需要比较相邻元素，而链表找相邻元素还是很容易的。

​ 这里是我们设计的链表数据结构跟常规的链表差不多。

1
2
3
4
5
6
7
8
typedef struct link_node{
	int data;
	struct link_node* next;
}link_node;
typedef struct 	link_list{
	link_node * head;
	int length;
}link_list;

代码实现

完整代码如下:

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
105
106
107
108
109
110
#include	<stdio.h>
#include	<stdlib.h>
#include	<time.h>
#define MAX 10
typedef struct link_node{
	int 	data;
	struct link_node* next;
}link_node;
typedef struct 	link_list{
	link_node * head;
	int 	length;
}link_list;
void
bucket_sort(int a[],int n);
void
bubble_sort(link_list linklist);
int
sqrt_approximation(int x);
void
init_arr(int *,int );
void
print_arr(int *,int );
int
main()
{
	int 	a[MAX]={0};
	int 	n = MAX;
	init_arr(a,n);
	print_arr(a,n);
	bucket_sort(a,n);
	printf("----after sort----\n");
	print_arr(a,n);
	return 0;
}
void
init_arr(int a[],int n)
{
	srand((unsigned)time(NULL));
	int 	i;
	for(i=0;i<n;i++)
		a[i] = rand()%100;

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

void
bucket_sort(int a[],int n){
	int min = a[0],max = a[0],i,j,k;
	for(i=1;i<n;i++){
		if(min>a[i]) 	min = a[i];
		if(max<a[i])	max = a[i];
	}
	int length = max - min + 1;
	int bucket_num = sqrt_approximation(length);
	link_list *bucket = (link_list*)malloc(sizeof(link_list)*length);
	for(i = 0;i<n;i++){
		k = a[i]/length;
		link_node *node = (link_node*)malloc(sizeof(link_node));
		node->data = a[i];
		node->next = bucket[k].head;
		bucket[k].head = node;
		bucket[k].length++;	
	}
	for(i = 0;i<length;i++){
		bubble_sort(bucket[i]);
	}
	j = 0;
	link_node *tmp;
	for(i = 0;i<length;i++){
		tmp = bucket[i].head;
		while(tmp!=NULL){
			a[j++] = tmp->data;
			tmp = tmp->next;
		}
	}
}
void
bubble_sort(link_list linklist)
{
	int 	i,j,temp;
	link_node *linknode;
	for(i = 0;i<linklist.length;i++){
		linknode= linklist.head;
		for(j = 0;j<linklist.length-i-1;j++){
			if(linknode->data>linknode->next->data){
				if(linknode->next!=NULL){
					int temp = linknode->data;
					linknode->data = linknode->next->data;
					linknode->next->data = temp;
				}
			}
			linknode=linknode->next;
		}
	}
}
int
sqrt_approximation(int x){
	long 	approximation = x/2;
	while(approximation*approximation>x&&approximation>0){
		approximation--;
	}
	return approximation;
}

​ 性能我就不测试了，因为其中排序时间主要还是在选择的排序算法上，而我选择的是冒泡排序算法对于大量数据性能并不是很理想，而桶排序是一种分布式排序算法它将大数据分成小数据，很明显在分割数据时就会花费一定时间，再加冒泡排序时间复杂度还是很高的。综上测试的结果不会比普通的冒泡排序快。排序算法可以自行选择。

​ 当你去实现桶排序的时候你就会发现，影响排序时间的主要在于如何分割数据和排序数据。我是选择一种比较中规中矩的方法求个开平方根，要如何分割数据涉及到数理统计的知识，如果想要深入研究就需要一定数学的功底了。

总结

​ 桶排序在小数据的情况下效率可能会不太理想，通常来讲桶排序的时间复杂度O(n),这是在数据比较均匀的情况下，如果数据具有毛刺肯定性能会下降。对于桶排序是不是稳定算法取决于选择的排序算法，桶排序会占用大量内存空间。

基数排序

主要思想

​ 基数排序类似桶排序，都需要适当的函数关系来确定桶的个数和大小，其中与桶排序不同的是，桶排序只确定一次桶的数量，然后将桶中的元素使用排序算法排序，而基数排序确定的桶本身就具有大小关系，也就是基数排序通过不断分配桶来改变元素位置达到排序效果。

实现方法

​ 如何能体现出基数排序的精髓还是比较复杂的，你需要考虑桶的个数和桶的容量，当然如果你使用固定的数组实现肯定会非常简单，但你会发现当数据足够大的时候会浪费大量空间。

​ 在基数排序中有很多术语和公式，在这里不过多介绍，其中我们需要知道关键字就是如何分配桶的个数，在LSD算法中其实关键字可以是变化的，但在这里我们只介绍关键字是K:0~9的情况。这对于整数排序足够了。

​ 基数排序有MSD(Most Significant Digit)和LSD(Least Significant Digit)两种排序算法，其中MSD操作类似于桶排序，这里我们介绍LSD。理解其主要思想很容易但实现起来就需要考虑如何分配桶的问题。

​ 这里我们使用链表来存储数据，将队列抽象成为桶的容量，将链表抽象成桶。这里我们设计一个特殊的队列，其中记录链表的头节点和尾结点，主要为了插入比较方便。细心的你会发现链表实现栈很容易，但是实现队列却很复杂，主要是因为链表无法随机访问。以下是数据结构的设计：

1
2
3
4
5
6
7
8
typedef struct queue_node{
	int 	data;
	struct queue_node* next;
}queue_node;
typedef struct queue{
	queue_node 	*head;
	queue_node 	*rear;
}queue;

​ 这里假设数据都是整数，所以桶的编号可以确定为0~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
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
#include	<stdio.h>
#include	<stdlib.h>
#include	<time.h>
#define MAX 10
typedef struct queue_node{
	int 	data;
	struct queue_node* next;
}queue_node;
typedef struct queue{
	queue_node 	*head;
	queue_node 	*rear;
}queue;
void
radix_sort(int *,int );
void
init_arr(int *,int );
void
print_arr(int *,int );
int
main()
{
	int 	a[MAX]={0};
	int 	n = MAX;
	init_arr(a,n);
	print_arr(a,n);
	radix_sort(a,n);
	printf("----after sort----\n");
	print_arr(a,n);
	return 0;
}
void
init_arr(int a[],int n)
{
	srand((unsigned)time(NULL));
	int 	i;
	for(i=0;i<n;i++)
		a[i] = rand()%100;

}	
void
print_arr(int a[],int n)
{
	int	 i;
	for(i=0;i<n;i++)
		printf("a[%d] = %d\n",i,a[i]);
}
void
radix_sort(int a[],int n){
	int 	max = a[0];
	int 	i,j,radix,count,index;//i,j用于循环，radix基数用于判断桶的位置，count用于数组下标
	for(i=1;i<n;i++) if(max<a[i]) max = a[i];
	int 	d = 0;//最高位的位数
	while(max){
		d++;
		max/=10;
	}
	radix = 10;			
	queue* bucket = (queue*)malloc(sizeof(queue)*10);//创建桶
	for(i = 0;i < d;i++){
		//初始化桶
		for(j = 0;j<10;j++){
			bucket[j].head= NULL;
			bucket[j].rear = NULL;
		}
		for(j = 0;j<n;j++){
			index = a[j]%radix/(radix/10);//判断元素插入哪个桶
			queue_node *node = (queue_node*)malloc(sizeof(queue_node));
			node->data = a[j];
			node->next = NULL;
			if(bucket[index].head == NULL)
				bucket[index].head = node;
			else 
				bucket[index].rear->next = node;
			bucket[index].rear= node;
		}
		count = 0;
		for(j = 0;j<10;j++){
			while(bucket[j].head!=NULL){
				a[count++] = bucket[j].head->data;
				queue_node* tmp = bucket[j].head;
				bucket[j].head = bucket[j].head->next;
				free(tmp);
			}
		}
		radix*=10;
	}
	free(bucket);
}

性能测试

​ 测试100000个随机数排序。(不同电脑不同)

总结

​ 基数排序属于分布式排序体现的是分治思想。由于排序基于非比较所有打破了传统基于比较的排序算法O(nlog⁡n)O(n\log n) 的限制，但代价就是需要大量的空间。这里只是简单的介绍，如果了解更多可以查阅相关文献。

10大排序总结

​ 排序算法思想很好理解，实现起来却要考虑很多，仔细的你可能发现算法的效率需要权衡时间和空间的。这需要了解数据的分布，没错这就是数学。要了解数据的分布需要数理统计的知识来作为支撑。在这个10个算法中我特意的做出了测试，可以然你切身体验算法的乐趣。在这里你不会因为枯燥的概念而烦恼，相反你可以通过实践去深入其境。

时间复杂度总结

​ 这里是10大算法的时间复杂度总结

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 排序排序方式 稳定性
冒泡排序 O(n2)O(n^2) O(n)O(n) O(n2)O(n^2) O(1)O(1) In-place 稳定
选择排序 O(n2)O(n^2) O(n2)O(n^2) O(n2)O(n^2) O(1)O(1) In-place 不稳定
插入排序 O(n2)O(n^2) O(n)O(n) O(n2)O(n^2) O(1)O(1) In-place 稳定
希尔排序 O(nlog⁡n)O(n\log n) O(nlog⁡2n)O(n\log^2 n) O(nlog⁡2n)O(n\log^2 n) O(1)O(1) In-place 不稳定
归并排序 O(nlog⁡n)O(n\log n) O(nlog⁡n)O(n\log n) O(nlog⁡n)O(n\log n) O(n)O(n) Out-place 稳定
快速排序 O(nlog⁡n)O(n\log n) O(nlog⁡n)O(n\log n) O(n2)O(n^2) O(log⁡n)O(\log n) In-place 不稳定
堆排序 O(nlog⁡n)O(n\log n) O(nlog⁡n)O(n\log n) O(nlog⁡n)O(n\log n) O(1)O(1) In-place 不稳定
计数排序 O(n+k)O(n+k) O(n+k)O(n+k) O(n+k)O(n+k) O(k)O(k) Out-place 稳定
桶排序 O(n+k)O(n+k) O(n+k)O(n+k) O(n2)O(n^2) O(n+k)O(n+k) Out-place 稳定
基数排序 O(n×k)O(n\times k) O(n×k)O(n\times k) O(n+k)O(n+k) O(n+k)O(n+k) Out-place 稳定

算法性能评估语：

稳定：如果a原本在b前面，而a=b时，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b时，排序之后a可能出现在b的后面。

内排序(In-place)：所有排序操作都在内存中完成。
外排序(Out-place)：通常是由于数据太大，不能同时存放在内存中，根据排序过程的需要而在外存与内存之间 数据传输才能进行。

时间复杂度：时间频度，一个算法执行所耗费的时间。算法中通常用数据比较次数与数据移动次数 进行衡量。
空间复杂度：算法执行所需要的内存大小。