【数据结构与算法】八大排序（下）剩下四大排序+基数排序的补充.什么，这还拿不下你？

🧸🧸🧸各位大佬大家好，我是猪皮兄弟🧸🧸🧸

今天带来的内容是八大排序后三个，归并排序，堆排序，计数排序，并且拓展一个基数排序

这里是下面要讲的知识内容🥳🥳🥳

---

一、⚽MergeSort归并排序递归&&时间复杂度分析

首先，归并排序需要数据对半分成很多小份，然后才去进行归并，所以，他算是一种后序遍历
归并排序和快速排序的模式很像，快速排序是将小的堆到左边，大的堆到右边进行分支，直到只有一个，而归并排序是分成若干小份，没份进行归并，它的时间复杂度为O(NlogN)，并且是严格的，他不像快排要考虑keyi的取值

//归并排序递归完整代码
void _MergeSort(int *a,int begin,int end,int *tmp)
{
	if(begin>=end)	
		return ;
	int mid = begin + (end- begin);
	_MergeSort(a,begin,mid,tmp);
	_MergeSort(a,mid+1,end,tmp);
	
	int begin1= begin,end1=mid;
	int begin2= mid+1,end2=end;
	int i=begin1;//因为进行归并的数组都是连着的，方便拷贝回原数组
	while(begin1<=end1&&begin2<=end2)
	{
		if(a[begin1]<a[begin2])
		{
			tmp[i++]=a[begin1++];
		}
		else
		{
			tmp[i++]=a[begin2++];
		}
	}
	while(begin1<=end1)
	{
		tmp[i++]=a[begin1++];
	}
	while(begin2<=end2)
	{
		tmp[i++]= a[begin2++];
	}
	
	memcpy(a+begin,tmp+begin,sizeof(int)*(end-begin+1))
	//拷贝回原数组
}

void MergeSort(int *a,int n)
{
	int *tmp=(int *)malloc(sizeof(int)*n);
	assert(tmp);
	_MergeSort(a,0,n-1,tmp);
	free(tmp);
	tmp=NULL;
}
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

几乎是完全的二分，所以非常的快，不过就是需要开辟一个新的数组出来，空间复杂度达到了O(N)
归并排序的递归实际上只是为了区间的划分，真正做事的是后面的代码

二、⚽MergeSort归并排序非递归

栈只适用于非递归前序遍历的东西，而归并排序是后序遍历，栈放在这里就不太合适了，所以，可以直接就倒着来，设置一个gap等于1 ，直接进行归并 ，然后再gap=gap*2
最大的问题在于边界的修正

void MergeSort(int *a,int n)
{
	int *tmp=(int *)malloc(sizeof(int)*n);
	assert(tmp);
	int gap=1;
	while(gap<n)
	{
		for(int i=0;i<n;i+=2*gap)
		{
			int begin1= i,end1=i+gap-1;
			int begin2=i+gap,end2=i+2*gap-1;
			
			int j=begin1;
			if(end1>=n)
			{
				end1=n-1;
				begin2=n;
				end2=n-1;
			}
			else if(begin2>=n)
			{
				begin=n;
				end2=n-1;
			}
			else if(end2>=n)
			{
				end2=n-1;
			}
			//边界修正


			while(begin1<=end1&&begin2<=end2)
			{
				if(a[begin1]<a[begin2])
				{
					tmp[j++]=a[begin1++];
				}
				else
				{
					tmp[j++]=a[begin2++];
				}
			}
		
			while(begin1<=end1)
			{
				tmp[j++]=a[begin1++];
			}
			while(begin2<=end2)
			{
				tmp[j++]= a[begin2++];
			}
		}
		memcpy(a,tmp,n*sizeof(int));
		gap*=2;
	}
	free(tmp);
	tmp=NULL;
	
}
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

三、⚽堆排序

1.🌈向上向下调整

void AdjustUp(HPDataType*a,int child)
{
	assert(a);
	int parent=(child-1)/2
	while(child>0)
	{
		if(a[child]<a[parent])
		{
			swap(&a[child],a[parent]);
			child=parent;
			parent=(child-1)/2;
		}
		else
		{
			break;
		}
	}
}



void AdjustDown(HPDataType*a,int size,int parent)
{
	assert(php->a);
	int child=parent*2+1;
	while(child<size)
	{
		if(child+1<size&&a[child]>a[child+1])
		{
			child++;
		}
		if(a[child]<a[parent])
		{
			Swap(&a[child],&a[parent]);
			parent=child;
			child=2*parent+1;
		}
		else
		{
			break;
		}
	}


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

2.🌈两种建堆方式

向上调整建堆和向下调整建堆

void HeapSort(int*a,int n)
{

	//建堆方式1：向上建堆
	for(int i=1;i<n;++i)
	{
		AdjustUp(a,i);
	}
	
	//因为向下调整建堆需要左右子树都是堆才能调整，所以，从下往上，并且，从有意义的开始，也就是最后一个数据的parent
	for(int i=(n-1-1)/2;i>=0;i--)
	{
		AdjustDown(a,n,i);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.🌈堆排序的时间复杂度分析

向下调整建堆O(N)
采用每一层的结点数*最坏轻快下的调整次数，然后错位相减
分析如下

向上调整建堆O(NlogN)
几乎每一个结点都需要向上调整，然后最坏情况下调整logN次，所以N*logN

四、⚽CountSort计数排序&&时间复杂度分析

计数排序
计数排序又称鸽巢原理，是通过对哈希直接定址法的变形应用
1.统计每个数据出现的次数
2.排序，按这个出现的次数把这个数写会原数组，出现几次就有几个

局限性：
1.如果是浮点数、字符串等等就不能玩了
2.如果数据范围很大，那么空间复杂度就会很高，相对不适合
如果使用绝对映射，只有几个数据，但是范围很广的话，很多空间没映射而浪费
所以使用相对映射，开辟几个空间（a[i]-min）

计数排序适合范围集中，重复数据多
时间复杂度O(MAX(range,N))
空间复杂福O(range)

void CountSort(int*a,int n)
{
	int min=a[0],max=a[0];
	for(int i=0;i<n;i++)
	{
		if(a[i]<min)
		{
			min=a[i];
		}
		if(a[i]>max)
		{
			max=a[i]
		}
	}
	int range =max-min+1;
	int *count=(int *)malloc(sizeof(int)*range);
	assert(count);
	memset(count,0,sizeof(int)*range);
	
	for(int i=0;i<n;i++)
	{
		count[a[i]-min]++;
	}
	int start=0;
	for(int i=0;i<range;i++)
	{
		while(count[i])
		{
			a[start++]=i+min;
			count[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

五、⚽稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字记录，若经过排序，这些记录的相对次序不变，那么原序列中，r[i]=r[j],r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的

解释：
1.堆排序最好最坏都是O(NlogN)因为堆中几乎不可能有序
2.冒泡排序最好是O(N)，是加了状态变量的时候，第一次遍历有序就跳出了，不然的话还是O(N^2)
3.快速排序受Keyi的影响很大，最坏是N+N-1+N-2+…
4.希尔排序不稳定原因：在预排的时候，相同的数在不同的gap组，保证不了位置
5.选择排序不稳定原因，比如 4 5 5 1 3 8
6.快排加入了三数取中之后出现时间复杂度O(N^2)的概率极低，空间复杂度 是因为参数压栈，空间是能够重复利用的，看深度，O(logN)

六、⚽基数排序

基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的办法
有两种基数排序
1.MSD最高位优先
2.LSD最低位优先

七、⚽总结

八大排序算法是很重要的基础思想，到这里就全部讲完了，感谢大家的支持！！