十大排序算法笔记(C语言)（二）归并排序、堆排序、计数排序、桶排序、基数排序

十大排序算法笔记(C语言)（二）归并排序、堆排序、计数排序、桶排序、基数排序 排序算法最好情况最坏情况平均时间复杂度空间复杂度稳定性归并排序O(n*logn)O(n*logn)O(n*logn)O(n)稳定堆排序O(n*logn)O(n*logn)O(n*logn)O(1)不稳定计数排序O(n+k)O(n+k)O(n+k)O(n+k)稳定桶排序O(n+k)O(n^2)O(n+k)O(n+k)稳定基数排序O(n*k)O(n*k)O(n*k)O(n+k)稳定

---

文章目录

• • 一、归并排序
  • • 1.1 归并排序基础
    • 1.2 代码演示
    • 1.3 归并排序的复杂度、稳定性以及使用场景
    • • 1.3.1 时间复杂度
      • 1.3.2 空间复杂度
      • 1.3.3 稳定性
      • 1.3.4 使用场景
  • 二、堆排序
  • • 2.1.堆排序的基础
    • 2.2 代码演示
    • 2.3 堆排序的复杂度、稳定性以及使用场景
    • • 2.3.1 时间复杂度
      • 2.3.2 空间复杂度
      • 2.3.3 稳定性
      • 2.3.4 使用场景
  • 三、计数排序
  • • 3.1 计数排序基础
    • 3.2 代码演示
    • 3.3 计数排序的复杂度、稳定性以及使用场景
    • • 3.3.1 时间复杂度
      • 3.3.2 空间复杂度
      • 3.3.3 稳定性
      • 3.3.4 使用场景
  • 四、桶排序
  • • 4.1 桶排序基础
    • 3.2 代码演示
    • 3.3 桶排序的复杂度、稳定性以及使用场景
    • • 3.3.1 时间复杂度
      • 3.3.2 空间复杂度
      • 3.3.3 稳定性
      • 3.3.4 使用场景
  • 五、基数排序
  • • 5.1 基数排序的基础
    • 5.2 代码演示
    • 5.3 基数排序的复杂度、稳定性以及使用场景
    • • 5.3.1 时间复杂度
      • 5.3.2 空间复杂度
      • 5.3.3 稳定性
      • 5.3.4 使用场景

---

一、归并排序 1.1 归并排序基础

工作原理：若n 为1，算法终止，否则将n个待排序元素分割成k(k = 2)个大致相同的子集合分别递归排序，再将排好序的子集归并为一个集合。
动画演示过程：

1.2 代码演示

//封装进行排序的函数，方便用于递归
void Merge(int a[],int start,int mid,int end){
		int result[20];
		int i,j,k;
		i = start;
		j = mid+1;
		k = 0;
		while(i <= mid && j <= end){
			if(a[i] < a[j]){
				result[k++] = a[i++];
			}else {
				reslut[k++] = a[j++];
			}
		}
		if(i == mid+1){
			while(j <= end){
				result[k++] = a[j++];
			}
		}
		if(j == end+1){
			while(i <= end){
				result[k++] = a[i++];
			}
		}
		for(i = 0,j = start;i < k;i++,j++){
			a[j] = result[i];
		}
}

void MergeSort(int a[],int start,int end){
	if(start >= end) return;
	int mid = (start+end)/2;
	//先分成最小的部分（即不能继续分下去为止）
	MergeSort(a,start,mid);
	MergeSort(a,mid+1,end);
	Merge(a,start,mid,end);
}

1.3 归并排序的复杂度、稳定性以及使用场景 1.3.1 时间复杂度

归并排序涉及到递归调用，所以归并排序的时间复杂度需要从递归算法的复杂度说起。
递归算法的时间复杂度为：T(n) = aT[n/b]+f(n)。
T[n] = 2T[n/2] + n ----------------第一次递归
令：n = n/2 = 2 { 2 T[n/4] + (n/2) } + n ----------------第二次递归
= 2^2 T[ n/ (2^2) ] + 2n
令：n = n/( 2^(m-1) ) = 2^m T[1] + mn ----------------第m次递归(m次后结束)
当最后平分的不能再平分时，也就是说把公式一直往下跌倒，到最后得到T[1]时，说明这个公式已经迭代完了（T[1]是常量了）。 .
得到：T[n/ (2^m) ] = T[1] ===>> n = 2^m ====>> m = logn；
T[n] = 2^m T[1] + mn ；其中m = logn;
T[n] = 2^(logn) T[1] + nlogn = n T[1] + nlogn = Cn + nlogn ；其中n为元素个数
而且，归并排序不管是最坏情况或者还是最好情况时间复杂度都为O(nlogn)。

1.3.2 空间复杂度

递归代码的空间复杂度不能和时间复杂度一样累加，因为尽管每次合并都需要申请额外数组，但是合并完后就释放了，到下次合并时才会再次申请。所以每个时间点只有一份n个数据的额外空间，空间复杂度为O(n)。

1.3.3 稳定性

从上面的代码可以看出来，如果前后有相同的元素时，只要控制前半部分的元素放入总的数组就好，这样归并排序也就是稳定的。

1.3.4 使用场景

待排序序列中元素较多，并且要求较快的排序速度时

二、堆排序 2.1.堆排序的基础

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

2.2 代码演示

//交换数值
void swap(int*a,int*b){
	int temp = *a;
	*a = *b;
	*b = temp;
}

//堆排序
void HeapSort(int a[],int len){
	//堆的最后一个非叶子节点
	int f；
	if(len%2 == 0){
		f = len/2-1;
	}else {
		f = (len-1)/2-1;
	}
	//由下至上构建大堆
	for(int i = f;i >= 0;i--){
		swap_heap(a,i,len);
	}
	//循环构建大堆
	for(int j = len-1;j>0;j--){
		//交换首尾元素
		swap(&a[0],&a[j]);
		swap_heap(a,0,j);
	}
}

//构建堆
void swap_heap(int a[],int i,int len){
	//左子节点
	int left = 2*i+1;
	//右子节点
	int right = 2*i+2;
	//父节点
	int k = i;
	//对比left，k,和right三者中的最大值下标
	if(left < len&&a[left]>a[k]){
			k = left;
	}
	if(right < len&&a[right]>a[k]){
		k = right;
	}
	//如果父节点的值不是最大值
	if(k != i){
		//最大值与父节点交换
		swap(&a[k],&a[i]);
		//位置发上变化需要继续校验子节点
		swap_heap(a,k,len);
	}
}

2.3 堆排序的复杂度、稳定性以及使用场景 2.3.1 时间复杂度

初始化建堆的时间复杂度为O(n)，排序重建堆的时间复杂度为nlog(n)，所以总的时间复杂度为O(n+nlogn)=O(nlogn)

2.3.2 空间复杂度

堆排序通过简单的交换就能把数据就地排成堆，不需要辅助空间，所以空间复杂度为O(1)。

2.3.3 稳定性

堆排序是一种不稳定的排序，原因是：在非堆顶元素在向堆顶移动的过程中，经历着堆层次的改变，这就有可能导致相等元素相对位置的改变。
因此，堆排序是一种不稳定的排序方式。

2.3.4 使用场景

适合用于数比较多的时候，因为堆排序效率高

三、计数排序 3.1 计数排序基础

工作原理:计数排序不是一个比较算法，而是牺牲空间来换取时间的一种算法。
(1) 找出原数组中元素值中最大，记为max
(2)创建一个新数组count，其长度为max+1，其元素默认值为0
(3)遍历数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值
(4)创建结果数组result，起始索引index
(5)遍历count数组，找出其中元素值大于0的元素，将其对应的索引作为元素值填充到result数组中，每处理一次，count中的该元素值减1，直到该元素值为0，依次处理count中剩下的元素
动画演示过程：

3.2 代码演示

void CountSort(int a[],int n){
	int i,k,max;
	int* count,*result;
	max = 0;
	//找出a数组中的最大值
	for(i = 1;i < n;i++){
		if(a[i]>max){
			max = a[i];
		}
	}
	k = max+1;
	count = (int*)malloc(sizeof(int)*k);
	result = (int*)malloc(sizeof(int)*n);
	//初始c数组的值都为0
	for(i = 0;i < k;i++){
		c[i] = 0;
	}
	//统计数组a中每个值为i的元素出现的次数
	for(i = 0;i < n;i++){
		c[a[i]]++;
	}
	//确定值为i的元素在数组c中出现的位置
	for(i = 0;i < k;i++){
		c[i] += c[i-1];
	}
	//如果从后往前的顺序，则为稳定的，相反则为不稳定的
	for(i = n-1;i >= 0;i++){
		result[c[a[i]]-1] = a[i];
		c[a[i]]--;
	}
	for(i = 0;i < n;i++){
		a[i] = result[i];
	}
	free(result);
	free(c);
}

3.3 计数排序的复杂度、稳定性以及使用场景 3.3.1 时间复杂度

计数排序的时间复杂度为O(n+k)[所有情况都是],k指的是数组的最大值

3.3.2 空间复杂度

计数排序的空间复杂度为O(n+k),k指的是数组的最大值

3.3.3 稳定性

计数排序是稳定的

3.3.4 使用场景

适用于数较少，且要大于0，并且最好几个数字是连在一起的

四、桶排序 4.1 桶排序基础

工作原理:桶排序是计数排序的升级版，先把数组里面的数分成几个桶，然后在桶里面进行排序。
动画演示过程：

3.2 代码演示

 
typedef struct node {
	int num;
	struct node *next;
}KeyNode;
 
void bucket_sort(int a[],int size,int bucket_size) {
	int i,j;
    //这是一个结构体指针的数组，数组内都是指针，还要分配内存，为结构体指针数组分配大小为bucket_size的内存空间
	//使用二维指针表示二维数组，动态分配内存空间
	KeyNode **bucket_num = (KeyNode **)malloc(bucket_size * sizeof(KeyNode*));    //分配行所用的空间
	for(i = 0;i < bucket_size;i++) {
		bucket_num[i] = (KeyNode*)malloc(sizeof(KeyNode));      //为每个桶分配内存空间，分配列所用的空间
		bucket_num[i]->num = 0;   //记录当前桶中的数量，初始化桶中数量为0
		bucket_num[i]->next = NULL;   //为结构体中的结构体指针变量初始化为空
	}
	for(j = 0;j < size;j++) {
		KeyNode *node = (KeyNode *)malloc(sizeof(KeyNode));     //定义一个结构体变量的指针
		node->num = a[j];    
		node->next = NULL;
		int index = a[j]/100;  //映射函数计算桶号
		KeyNode *p = bucket_num[index];   //初始化P成为桶中数据链条的头指针
        //该桶中还没有数据
		if(p->num == 0){
			bucket_num[index]->next = node;
			(bucket_num[index]->num)++;
		}else{
       		//链表结构的插入排序
			while(p->next != NULL && p->next->num <= node->num)
			{
				p = p->next;
			}	
			node->next = p->next;
			p->next = node;
			(bucket_num[index]->num)++;
		}
	}

3.3 桶排序的复杂度、稳定性以及使用场景 3.3.1 时间复杂度

N个数据平均的分配到M个桶中，这样每个桶就有[N/M]个数据量。对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为：
O(N)+O(M*(N/M)log(N/M))=O(N+N(logN-logM))=O(N+NlogN-NlogM)
当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。

3.3.2 空间复杂度

桶排序的空间复杂度为O(n+k)

3.3.3 稳定性

一般都以为是稳定的

3.3.4 使用场景

数据均匀分布在一个区间内。

五、基数排序 5.1 基数排序的基础

工作原理: 基数排序是一种非比较型排序算法。基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较
(1)将所有要比较的数值统一为同样的数位长度，数位较短的数前面补零。
(2)从最低位开始，依次进行一次排序
(3)依次从最低位排序一直到最高位排序完成以后，数列就变成一个有序数列
动画演示过程：

5.2 代码演示

转载至:https://blog.csdn.net/hitwhylz/article/details/9970451

int GetNumInPos(int num,int pos)
{
	int temp = 1;
	for (int i = 0; i < pos - 1; i++)
		temp *= 10;
    
	return (num / temp) % 10;
}
 
 
//基数排序  pDataArray 无序数组；iDataNum为无序数据个数
void RadixSort(int* pDataArray, int iDataNum)
{
	int *radixArrays[RADIX_10];    //分别为0~9的序列空间
	for (int i = 0; i < 10; i++)
	{
		radixArrays[i] = (int *)malloc(sizeof(int) * (iDataNum + 1));
		radixArrays[i][0] = 0;    //index为0处记录这组数据的个数
	}
	
	for (int pos = 1; pos <= KEYNUM_31; pos++)    //从个位开始到31位
	{
		for (int i = 0; i < iDataNum; i++)    //分配过程
		{
			int num = GetNumInPos(pDataArray[i], pos);
			int index = ++radixArrays[num][0];
			radixArrays[num][index] = pDataArray[i];
		}
        
		for (int i = 0, j =0; i < RADIX_10; i++)    //收集
		{
			for (int k = 1; k <= radixArrays[i][0]; k++)
				pDataArray[j++] = radixArrays[i][k];
			radixArrays[i][0] = 0;    //复位
		}
	}
}

5.3 基数排序的复杂度、稳定性以及使用场景 5.3.1 时间复杂度

每次排序时间复杂度O(n)，那么如果有k位，则时间复杂度为O(k*n),如果k不大比如手机号11位，那么时间复杂度就是O(n)。

5.3.2 空间复杂度

基数排序的空间复杂度为O(n+k)。

5.3.3 稳定性

基数排序是稳定的排序方法。

5.3.4 使用场景

基数排序的适用场景和计数排序类似，即待排序序列是在一定范围内的整数。