【排序】|归并排序|桶排序|冒泡排序|堆排序|算法详解+分析_归并排序和堆排序可能遇到的问题及解决方案

一，桶排序

1，算法思想

桶排序处理一群数值的时候的操作就是先把这一群数值首先的存入到先开好的一群桶中，这些桶一般使用数组进行模拟，当这些数值被存入数组之中之后，我们对这些桶进行遍历，从小到大，每次当这些桶内存在元素的时候我们就把这些元素弹出来，这样出来的序列就能保证从小到大的排序。

2，代码实现

#include <iostream>
using namespace std ;

const int N = 100010 ;

int q[N] ;

int main ()
{
	int n ;
	cin >> n ;
	for(int i = 0 ; i < n ; i ++ )
	{
		int x ;
		cin >> x ;
		q[x] ++ ;
	}
	for(int i = 0 ; i < N ; i ++ )
	{
		while(q[i])
		{
			cout << i << " ";
			q[i] -- ;
		}
	}
	return 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

3,桶排序的局限性

桶排序局限性主要原因是因为数组不能开过大，第一是每次遍历的时候会导致时间超时TLE，他的时间复杂度是一个O（N），整个N不是输入数据个数上的n,这个操作是整个的数据范围上的N，当数据范围过大的时候无论从算法的兼容性还是运行速率这个算法都不是一个好的选择

另一方面当数组开的过大的时候可能造成数组越界。也就是常说的RE,当然在数组越界的同时TLE是绝对发生的。

基于这种局限性，我们在数据范围比较大的时候一般不选用这个算法进行排序，但是在这个数据范围比较小，但数据比较多的时候，这个算法可以说是时间复杂度最优的一个算法。

二，冒泡排序

1,算法思想

冒泡排序就是一种朴素算法，他采用的是一种遍历的思想，首先我们把这些数值存进一个数组中，我们再对这个数组中的每次排序他的一个最大值或者是最小值，这种方法我们可以在时间复杂度O(n²)中完成操作。

2，代码实现

#include <iostream>
using namespace std ;

const int N = 100010 ;

int q[N] ;

int main ()
{
	int n ;
	cin >> n ;
	for(int i = 0 ; i < n ; i ++ )
		cin >> q[i] ;
	for(int i = 0 ; i < n ; i ++ )
		for(int j = 0 ; j < n - i - 1 ; j ++ )
		{
			if(q[j] > q[j + 1])
				swap(q[j] , q[j + 1]);
		}
	for(int i = 0 ; i < n ; i ++ )
		cout << q[i] << " ";
	puts("");
	return 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

3,算法的局限性

我们知道这个排序算法分复杂度是O(n²)的，但是这个复杂度在很多时间还是不能完美的适应这个一些算法题的解决，于是我们就提出了时间复杂度更低的快速排序和归并排序

三, 归并排序

1，算法思想

归并排序跟快速排序相同，他们都是一个递归操作，首先我们要思考这个归并排序的递归操作是怎么进行的？我们归并之中涉及到的递归操作是先递归再排序，同样的我们递归的时候把这个数组分成两个小数组，完成接下来的操作，首先这个递归就像快速排序的递归完整的搬了过来，而且这次递归的模型一定会变成一个完全的二叉树。

当我们完成递归操作之后，我们会从下向上进行一次比大小的排序操作，从下向上，当到达 n(小数组的元素个数) == 1 ，我们进行向上比较，每次比较完成之后形成一个大数组的内部都是存在完整的顺序，然后我们进行逐步递归操作（使用双指针的思想）完成整个数组的排序

2，代码实现

首先我们要完成的是一个递归操作，整个递归操作，只要把他们从中间分开就行，每次都从中间分开，再加上一个当 n == 1 的弹出的操作

#include <iostream>
using namespace std ;

const int N = 100010 ;

void merge_sort (int a[] , int l , int r)
{
	if(l >= r ) return ;
	//当整个数组中剩下一个的时候，我们就停止递归
	int mid  = (l + r ) >> 1 ;
	merge_sort(a , l , mid);
	merge_sort(a , mid + 1 , r) ;
	//完成递归操作，每次都要取得中间的值分成两半。
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

完成上面的递归操作之后，我们想到每次合并的两个数组都是在数组内部已经排序好的小数组，就像上文所说的我们在这个两个数组都没有被取完的情况下使用双指针的思想，完成这个整个数组的排序,当然完成整个操作我们还需要提前开一个数组来储存数据temp[N]

int i = l , j = mid + 1, k = 0;
while ( i <= mid && j <= r ) 
{
	if(a[i] < a[j]) temp[k ++] = a[i ++];
	else temp[k ++ ] = a[j ++ ] ;
}
1
2
3
4
5
6

然后我们会发现我们在这两数组中肯定会有一些剩下的元素这些都是完全比另一个数组大的，我们直接把这些值存入数组就行 ；

while (i <= mid)
	temp[k ++ ] = a[i ++ ];
while ( j <= r) 
	temp[k ++ ] = a[j ++ ];
1
2
3
4

最后我们要把这些数组存到原来的函数中 ；

for(int i = 0 j = l ; j <= r ;i ++ ,j ++)
	a[j] = temp[i];
1
2

完成这些分步操作之后我们总结一下，下面是完整的代码

#include <iostream>

using namespace std ;

const int N = 100010 ;

int temp[N] ;

void merge_sort(int q[], int l , int r) 
{
	if(l >= r) return ;
	int mid = (r + l ) >> 1; 
	merge_sort(q ,  l , mid );
	merge_sort(q, mid + 1 , r) ;
	int i = l ,j = mid + 1 , k = 0 ;
	while ( i <= mid && j <= r)
		if(q[i] < q[j])	temp[k ++ ] = q[i ++ ];
			else temp[k ++ ] = q[j ++ ];
	while ( i <= mid )
		temp[k ++ ] = q[i ++ ];
	while ( j <= r)
		temp[k ++ ] = q[j ++ ];
	for(int i = 0 , j = l ; j <= r ;j ++ ,i ++ )
		q[j] = temp[i] ;
}

int main ()
{
	int q[N] ;
	int n ;
	cin >> n ;
	for(int i = 0 ; i < n ; i ++)
		cin >> q[i] ;
	merge_sort(q , 0 , n - 1);
	for(int i = 0 ; i < n ; i ++ )
		cout << q[i] << " ";
	puts("");
	return 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
37
38
39

3,算法分析

当前的归并排序可以理解为快速排序的再次升级，他的时间复杂度真正的达到了O(nlog₂n),这个时间复杂度已经能完美的适应绝大多数的算法环境了。

四,堆排序

1,前言

这个排序涉及到一些数据结构方面的知识，初学者可以直接跳过，等数据结构小成之后回来再看也不迟.本小节需要掌握堆这类数据结构的基础知识和一些二叉树的基础知识.

2，算法思想

堆这一类的数据结构，我们可以知道他的最小值永远都在头部，我们可以利用这一类数据结构来使用堆进行简单的数据排序，首先我们可以由简单的算法结构可以知道堆的一个建立

堆的建立：首先把堆存储在一个 数组中，使用堆的下压操作，从下n/2 开始向上遍历向下压

当堆被建立出来之后，我们思考怎么才能每次的输出堆中的最小值，并且把他的最大值输出来，其实这一点在堆数据结构中早早的被讲解过，但是我们还是再次指出这个操作

堆的弹出：弹出最小值之后，我们把最末尾的值赋到这个堆的顶部。

这个算法就只有这两