基础排序算法分析与总结

插入类排序

直接插入排序

算法思想：
(1)将第i个记录插入到前面i-1个已经排序好的记录中
(2)插入过程为依次比较后移，直到找到比第i个记录小的数为止，插入。


算法实例：
待排序列｛48，62，35，77，55，14，35，98｝
A）｛48｝ 62 35 77 55 14 35 98
B）｛48 62｝ 35 77 55 14 35 98
C）｛35 48 62｝ 77 55 14 35 98
D）｛35 48 62 77｝ 55 14 35 98
E）｛35 48 55 62 77｝ 14 35 98
F）｛14 35 48 55 62 77｝ 35 98
G）｛14 35 35 48 55 62 77｝ 98
H）｛14 35 35 48 55 62 77 98｝
以下是用插入排序对30个元素的数组进行排序的动画：

对序列{6, 5, 3, 1, 8, 7, 2, 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

#include<iostream>
using namespace std;
#define n 10
int a[10]={10,43,13,0,90,44,67,23,16,88};
void insertsort(int a[])           //直接插入排序
{
	int pre,key;
	for(int i=1;i<n;i++)
	{
		key=a[i];
		pre=i-1;
		while(pre>=0&&a[pre]>key)
		{
			a[pre+1]=a[pre];
			pre--;
		}
		a[pre+1]=key;
	}
}
int main()
{
	insertsort(a);
	for(int i=0;i<n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	return 0;
}

算法分析
1.空间复杂度：O（1）
2.平均时间复杂度：O（n²）
最差情况：反序，需要移动n×(n-1)/2个元素 ，运行时间为O(n^2)。 　
最好情况：正序，不需要移动元素，运行时间为O(n)．
3.稳定的排序算法
4.该排序与选择排序的区别是：选中已经排好序列的后一个数来进行插入操作，没有从未排序数中选择的过程
5.该排序与折半插入排序的区别：减少比较次数，直接插入排序为挨个比较，折半插入排序为二分比较，效率更高

折半插入排序

算法思想
与直接插入排序类似，只是通过二分查找找到需要插入的位置，直接插入，而非一个一个比较查找
算法实例

A）｛48｝ 62 35 77 55 14 35 98
B）｛48 62｝ 35 77 55 14 35 98
C）｛35 48 62｝ 77 55 14 35 98
D）｛35 48 62 77｝ 55 14 35 98
E）｛35 48 55 62 77｝ 14 35 98
F）｛14 35 48 55 62 77｝ 35 98
G）｛14 35 35 48 55 62 77｝ 98
H）｛14 35 35 48 55 62 77 98｝
算法实现

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

#include<iostream>
using namespace std;
#define n 10
int a[10]={10,43,13,0,90,44,67,23,16,88};
int low=0,high=9;
void binsertsort(int a[])          //折半插入排序
{
	for(int i=1;i<n;i++)
	{
		int key=a[i];
		int low=0,high=i;
		while(low<=high)
		{
			int mid=(low+high)/2;
			if(a[mid]<key)
				low=mid+1;
			else
				high=mid-1;
		}
		for(int j=i;j>=low+1;j--)
			a[j]=a[j-1];
		a[low]=key;
	}
}
int main()
{
	binsertsort(a);
	for(int i=0;i<n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	return 0;
}

算法分析
1.空间复杂度：O（1）
2.平均时间复杂度：O（n²）
3.折半插入排序是一种稳定的排序算法
4.折半插入排序并没有改变时间复杂度，而是把比较次数的数量级降到了O（n*logn）
5.当n较大时 折半插入排序的比较次数要比直接插入排序的最差情况要好很多 但比其最好情况要差

希尔排序

算法思想
希尔排序法(缩小增量法) 属于插入类排序，是将整个无序列分割成若干小的子序列分别进行插入排序的方法。
把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
(1)插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
(2)但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
算法实例
假设有这样一组数[13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，
这样他们就应该看起来是这样：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我们对每列进行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
将上述四行数字，依序接在一起时我们得到：[10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45].这时10已经移至正确位置了，然后再以3为步长进行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后变为：
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以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

#include<iostream>
using namespace std;
#define n 10
int a[10]={10,43,13,0,90,44,67,23,16,88};
//******************************希尔排序******************************
void shellsort(int a[])
{
	int j;
	for(int gap=n/2;gap>0;gap/=2)
		for(int i=gap;i<n;i++)
		{
			int temp=a[i];
			for(j=i-gap;j>=0&&a[j]>temp;j-=gap)
				a[j+gap]=a[j];
			a[j+gap]=temp;
		}
}
int main()
{
	shellsort(a);
	for(int i=0;i<n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	return 0;
}

算法分析
1.空间复杂度：O（1）
2.时间复杂度：平均 O(n^1.5)或O(n^1.3)
　　　　　　　最好 O(n)
　　　　　　　最坏 O(n^2)
3.希尔排序是一种不稳定的排序算法
4.希尔排序对于中等规模（n≤1000）的序列具有较高的效率，而且希尔排序算法简单，容易执行，因此很多排序应用程序都选用了希尔排序
5.关于增量d的取法，最初Shell提出取d=n[n/2]–下取整，再取d=d=n[n/2]，直到d=1为止。
该思路的缺点是，奇数位置的元素在最后一步才会与偶数位置的元素进行比较，使得希尔排序效率降低
后来Knuth提出d=[n/3]+1
本文代码采用的是d=n[n/2]的增量取法

交换类排序

冒泡排序

算法思想
冒泡排序通过重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来，直到没有再需要交换的元素为止（对n个项目需要O(n^2)的比较次数）
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。　
2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。　
算法实例
对序列{6, 5, 3, 1, 8, 7, 2, 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

#include<iostream>
using namespace std;
#define n 10
int a[10]={10,43,13,0,90,44,67,23,16,88};
void exchange(int &a,int &b)
{
	a=a^b;
	b=a^b;
	a=a^b;
}
//*****************************冒泡******************************
void bubble()
{
	int *b=a;
	for(int i=1;i<n;i++)
		for(int j=0;j<n-i;j++)
			if(a[j]>a[j+1])
				exchange(b[j],b[j+1]);
	for(int i=0;i<n;i++)
		cout<<b[i]<<" ";
	cout<<endl;
}
int main()
{
	bubble();
	return 0;
}

算法分析
1.空间复杂度：O（1）
2.时间复杂度： 平均O (n²)
最好O(n)
3.冒泡排序是一种稳定的排序算法
4.冒泡两层for循环外层表示进行n-1趟排序 内层表示每趟要进行n-i次比较
5.冒泡排序的改进：
思路：增加一个标识位 当某一趟冒泡排序没有进行元素交换 即元素已经有序时 冒泡结束
核心部分改为以下即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int flag=1;
for(int i=1;i<=n-1&&flag;i++)
	for(int j=0;j<n-1;j++)
	{
		flag=0;
		if(a[j]>=a[j]+1)
		{
			a[j]=a[j]^a[j+1];
			a[j+1]=a[j]^a[j+1];
			a[j]=a[j]^a[j+1];
			flag=1;
		}
	}
}

快速排序

算法思想
快速排序（Quicksort）是对冒泡排序的一种改进，又称划分交换排序（partition-exchange sort。
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）
1.从数列中挑出一个元素，称为”基准”（pivot）
2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列
的中间位置。这个称为分区（partition）操作。
3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
算法实例

算法实现

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

#include<iostream>
using namespace std;
#define n 10
int a[10]={10,43,13,0,90,44,67,23,16,88};
int low=0,high=9;
//*****************************快排(int)****************************
int getmid(int list[],int low,int high)
{
	int temp=list[low];
	while(low<high)
	{
		while(low<high&list[high]>=temp)
			high--;
		list[low]=list[high];
		while(low<high&&list[low]<=temp)
			low++;
		list[high]=list[low];
	}
	list[low]=temp;
	return low;
}
void quicksort(int a[],int low,int high)
{
	if(low<high)
	{
		int mid=getmid(a,low,high);
		quicksort(a,low,mid-1);
		quicksort(a,mid+1,high);
	}
}
int main()
{
	quicksort(a,low,high);
	for(int i=0;i<n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	return 0;
}

算法分析
1.平均空间复杂度：O（logn）
2.平均时间复杂度：O（nlogn）
最差：O(n²)
最好：O(nlogn)
3.快排是一种不稳定的排序算法
4.当数据趋近于无序时 快排的时间复杂度最优
当数据趋近于有序有 快排就会退化为一般的排序算法 时间复杂度退化为O(n²)
5.快排使用了递推 因此需要栈的辅助 空间复杂度较别的算法略高
6.优化（一）
枢轴的选取十分重要 选取的枢轴越接近中间值 算法的效率越高
正常算法的枢轴选取为数组的首元素
因此具体优化可以：每次选取避免选取到最值 可采用取平均值的方法求得尽可能靠中间的值
7.优化二（二）
获取枢轴的一般步骤为：
（1）确定枢轴
（2）从最高位开始找到第一个小于枢轴的数 与枢轴交换
（3）从最低位开始找到第一个大于枢轴的数 与枢轴交换
（4）直到high=low停止 实现枢轴的坐标均小于它 右边均大于它
针对两次交换操作 可以做如下优化：

1
2
3

list[low]=list[high];  //temp为枢轴
list[high]=list[low];
list[low]=temp;       //当low=high时退出while循环执行该步

如上优化可以避免进行两次交换操作
哪怕使用空间复杂度为1的位运算来交换两个数也会额外增加代码书写难度

选择类排序

简单选择排序

算法思想
每趟在n-i+1个记录中选取最小的关键字作为有序列中的第i个记录
算法实例
待排序列｛48，62，35，77，55，14，35，98｝
A）14｛62 35 77 55 48 35 98｝
B）14 35｛62 77 55 48 35 98｝
C）14 35 35｛77 55 48 62 98｝
D）14 35 35 48｛55 77 62 98｝
E）14 35 35 48 55｛77 62 98｝
F）14 35 35 48 55 62｛77 98｝
G）14 35 35 48 55 62 77｛98｝
H）14 35 35 48 55 62 77 98
选择排序的比较过程如下：

动画效果如下：

算法实现

1
2
3
4
5
6
7
8
9
10
11
12

void selectsort(int a[],int n)
{
	for(int i=1;i<=n-1;i++)
	{
		int k=i;
		for(int j=i+1;j<=n;j++)
			if(a[j]<a[k])
				k=j;
		if(k!=i)
			swap(r[i],r[k]);
	}
}

算法分析
1.空间复杂度：O（1）
2.时间复杂度：O(n²)
3.简单选择排序是不稳定的排序算法

树形选择排序

算法思想
又成锦标赛排序
基本思想是先把待排序的n个记录的关键字两两比较 取出最小者 然后在[n/2]个较小者中 采用同样的方法进行比较 直至选出最小的关键字为止
这一过程可以用一颗满二叉树来表示 不满时的结点用正无穷来填补
重复以上操作 直到所有的关键字全被取出为止
算法实例

算法分析
1.时间复杂度为：O（n*logn）

堆排序

算法思想
堆是一种数据结构，最好的理解堆的方式就是把堆看成一棵完全二叉树，这个完全二叉树满足任何一个非叶节点的值，都不大于（或不小于）其左右孩子节点的值。
若父亲大孩子小，则这样的堆叫做大根堆；若父亲小孩子大，这样的堆叫做小根堆。根据堆的定义，其根节点的值是最大（或最小），因此将一个无序序列调整为一个堆，
就可以找出这个序列的最大（或最小）值，然后将找出的这个值交换到序列的最后（或最前），这样有序序列元素增加1个，无序序列中元素减少1个，对新的无序序列重
复这样的操作，就实现了序列排序。堆排序中最关键的操作是将序列调整为堆，整个排序的过程就是通过不断调整使得不符合堆定义的完全二叉树变为符合堆定义的完全
二叉树的过程。
堆排序执行过程（大根堆）：
（1）从无序序列所确定的完全二叉树的第一个非叶子节点开始，从右至左，从下至上，对每个节点进行调整，最终将得到一个大根堆。
将当前节点（a）的值与其孩子节点进行比较，如果存在大于a值的孩子节点，则从中选出最大的一个与a交换。
当a来到下一层的时候重复上述过程，直到a的孩子节点值都小于a的值为止。
（2）将当前无序序列中第一个元素，在树中是根节点（a）与无序序列中最后一个元素（b）交换。a进入有序序列，到达最终位置，
无序序列中元素减少1个，有序序列中元素增加1个，此时只有节点b可能不满足堆的定义，对其进行调整。
算法实例
初始化动画如下：

堆排序动画如下：

算法实现

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

#include<iostream>
using namespace std;
#define n 10
void exchange(int &a,int &b)
{
	a=a^b;
	b=a^b;
	a=a^b;
}
//******************************堆排序******************************
void heapsort(int b[])
{
	creat_heap(b);
	for(int i=n;i>=1;i--)
	{
		exchange(b[1],b[i]);
		sift(b,1,i-1);
	}
}
void creat_heap(int b[])
{
	for(int i=n/2;i>=1;i--)
		sift(b,i,n);
}
void sift(int b[],int k,int m)
{
	int t=b[k];
	bool flag=false;
	int i=k,j=2*i;
	while(j<=m&&!flag)
	{
		if(b[j]<b[j+1]&&j+1<=m)
			j=j+1;
		if(t>=b[j])
			flag=true;
		else
		{
			b[i]=b[j];
			i=j;
			j=2*i;
		}
	}
	b[i]=t;
}
int main()
{
	int b[100];
	for(int i=1;i<=n;i++)
		cin>>b[i];
	heapsort(b);
	for(int i=1;i<=n;i++)
		cout<<b[i]<<" ";
	cout<<endl;
	return 0;
}

算法分析
1.空间复杂度：O（1）
2.时间复杂度为：O（nlogn）
最差时间复杂度：O（nlogn）
3.堆排序是一种不稳定的排序算法
4.由于堆排序的最差时间复杂度依然为O（n*logn） 这是堆排序最大的优点
5.它并不适用于n个数较小的情况 对于n较大的文件非常有效 如从1000000个记录中选出前10个最小的 这种情况用堆排序最好
6.堆中定义的三种操作
（1）创建大根堆（Build_Max_Heap）：将堆所有数据重新排序
（2）大根堆调整（Max_Heapify）：将堆的节点作调整，使得子节点永远小于父节点
（3）堆排序（HeapSort）：移除位在第一个数据的根节点，并做大根堆调整的递归运算
7.由于堆排序运用了子节点与父节点的关系 所以数组最好从a[1]开始存储数据 方便运算
8.堆的存储：

归并排序

算法思想
其核心就是“两两归并”，首先将原始序列看成每个只含有单独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

#include<iostream>
using namespace std;
#define n 10
int a[10]={10,43,13,0,90,44,67,23,16,88};
void Merge_array(int a[],int low,int mid,int high,int temp[])
{
	int i=low,m=mid,j=mid+1,h=high;
	int k=0;
	while(i<=m&&j<=h)
	{
		if(a[i]<=a[j])
			temp[k++]=a[i++];
		else
			temp[k++]=a[j++];
	}
	while(i<=m)
		temp[k++]=a[i++];
	while(j<=h)
		temp[k++]=a[j++];
	for(int i=0;i<k;i++)
		a[low+i]=temp[i];
}
void Merge_sort(int a[],int low,int high,int temp[])
{
	if(low<high)
	{
		int mid=(low+high)/2;
		Merge_sort(a,low,mid,temp);
		Merge_sort(a,mid+1,high,temp);
		Merge_array(a,low,mid,high,temp);
	}
}
int main()
{
	int temp[10];
	Merge_sort(a,low,high,temp);
	for(int i=0;i<n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	return 0;
}

算法分析
1.空间复杂度：O（n）
2.时间复杂度为：O（n*logn）
3.归并排序是一种稳定的排序算法
4.归并排序运用了二分递归的方法实现两两排序 把两个子表合成一个总表的方法类似于单链表的合并操作
5.参加网上测试样例：对于5万个随机数 归并排序几乎不需要时间 对于20万个随机数 仅耗时62ms 而快排需要78ms

三大线性时间排序算法

计数排序

算法思想
计数排序用到一个额外的计数数组C，根据数组C来将原数组A中的元素排到正确的位置。
计数数组C用来统计比数组中每个数字小的数有多少个 例如有个17个小于x的元素 那么C[x]=17 x可直接放在第18个位置
1.统计数组A中每个值A[i]出现的次数，存入C[A[i]]
2.从前向后，使数组C中的每个值等于其与前一项相加，这样数组C[A[i]]就代表了数组A中小于等于A[i]的元素个数
3.反向填充目标数组B：将数组元素A[i]放在数组B的第C[A[i]]项（即B[C[A[i]] - 1]），每放一个元素就将C[A[i]]递减
算法实例
下图给出了对{4, 1, 3, 4, 3}进行计数排序的简单演示过程

再给出一个实现图解：

算法实现

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

#include<iostream>
using namespace std;
#define n 10
int a[10]={10,43,13,0,90,44,67,23,16,88};
//******************************计数排序****************************
void Counting_sort(int a[])
{
	int b[11],c[100];
	memset(c,0,sizeof(c));
	for(int i=0;i<n;i++)
		c[a[i]]++;
	for(int i=1;i<100;i++)
		c[i]+=c[i-1];
	for(int i=n-1;i>=0;i--)
	{
		b[c[a[i]]]=a[i];
		c[a[i]]--;
	}
	for(int i=1;i<=n;i++)
		cout<<b[i]<<" ";
	cout<<endl;
}
int main()
{
	Counting_sort(a);
	return 0;
}

算法分析
1.空间复杂度:O(n+k)
2.时间复杂度：O(n+k)–k为数据的范围
平均时间复杂度：O(n+k)
最差时间复杂度：O(n+k)
3.计数排序是一种稳定的排序算法
4.如果在面试中有面试官要求你写一个O(n)时间复杂度的排序算法，你千万不要立刻说：这不可能！虽然前面基于比较的排序的下限是O(nlogn)。
但是确实也有线性时间复杂度的排序，只不过有前提条件，就是待排序的数要满足一定的范围的整数，而且计数排序需要比较多的辅助空间。
其基本思想是，用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。
5.计数排序的时间复杂度和空间复杂度取决于数组A的数据范围(等于A中元素的最大值与最小值的差加上1)，因此对于数据范围很大的数组，计数排序需要大量时间
和内存 所以计数排序并不适用与数据范围很大的数组
6.计数排序经常用作基数排序算法的一个子过程，其稳定性对于基数排序的正确性来说非常关键
7.计数排序不是比较排序，排序的速度快于任何比较排序算法

桶排序

算法思想
工作原理是将数组分解到有限数量的桶里，每个桶再分别进行排序。桶内排序有可能使用其他排序算法或是以递归的方式继续使用桶排序
1.在数组中查找数值的最大值和最小值；
2.初始化一个数组当作空桶，长度为 (MaxValue - MinValue + 1)。
3.遍历被排序数组，并把数值逐个放入对应的桶中。
4.对每个不是空的桶进行排序。
5.从不是空的桶里把数值再放回原来的数组中。
算法实例
下图给出了对{29, 25, 3, 49, 9, 37, 21, 43}进行桶排序的简单演示过程


算法实现

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

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define n 10
int a[10]={10,43,13,0,90,44,67,23,16,88};
//******************************桶排序******************************
//*****快排的源码已给出 不再复制
struct node
{
	int data[10];
	int count;
};
void Bucket_sort(int a[])
{
	int Max=a[0],Min=a[0],num;
	for(int i=1;i<n;i++)
	{
		Max=max(Max,a[i]);
		Min=min(Min,a[i]);
	}
	num=(Max-Min+1)/10+1;
	struct node *p;
	p=new struct node[num];
	for(int i=0;i<num;i++)
		p[i].count=0;
	for(int i=0;i<n;i++)
	{
		int k=(a[i]-Min+1)/10;
		p[k].data[p[k].count]=a[i];
		p[k].count++;
	}
	int pos=0;
	for(int i=0;i<num;i++)
	{
		quicksort(p[i].data,0,p[i].count-1);
		for(int j=0;j<p[i].count;j++)
			a[pos++]=p[i].data[j];
	}
}
int main()
{
	Bucket_sort(a);
	for(int i=0;i<n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	return 0;
}

算法分析
1.空间复杂度：O(k×n)
2.时间复杂度：O(n+k) （k=N*(logN-logM)–N为待排数据 M为桶的数量）
平均时间复杂度：O(n+k)
最差时间复杂度：O(n²)
3.桶排序是一种稳定的排序算法
4.当要被排序的数组中的数值是均匀分布时 桶排序的运行时间为线性时间O(n)。桶排序不是比较排序，它不受O(nlogn)下界的影响
5.在桶排序中找到正确的映射函数f(k)是关键 他可以把N个数据尽可能平均的分配到M个桶中
其作用就相当于快排中的划分 希尔排序中的子序列 归并排序中的子问题 已经把大量数据分割成了基本有序的数据块
例如上述图解的映射函数为f(k)=k/10
6.每个桶中可以根据情况使用各种排序函数 本文使用的是快排 也可以使用计数排序 堆排等等
7.桶排序算是计数排序的一种改进和推广 但是网上有许多资料把计数排序和桶排序混为一谈 其实桶排序要比计数排序复杂许多
8.代码中的结构体模拟了vector的作用 算出最大值-最小值后使用指针p动态分配空间 使得空间消耗最优

基数排序

算法思想
基数排序又是一种和前面排序方式不同的排序方式 基数排序不需要进行记录关键字之间的比较 基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法
所谓的多关键字排序就是有多个优先级不同的关键字 比如说成绩的排序 如果两个人总分相同 则语文高的排在前面 语文成绩也相同则数学高的排在前面
如果对数字进行排序 那么个位、十位、百位就是不同优先级的关键字 如果要进行升序排序 那么个位、十位、百位优先级一次增加
基数排序是通过多次的收分配和收集来实现的 关键字优先级低的先进行分配和收集
原理是将整数值按相同的有效位进行分组，然后在有效位区间内进行排序
1.获得值的最右侧的最小的位。
2.根据该位的值将数组内的元素值进行分组，但仍然保持元素的顺序。(以此来保持算法稳定性)
3.重复上述分组过程，直到所有的位都已被处理。
算法实例
下图给出了对{ 329, 457, 657, 839, 436, 720, 355 }进行基数排序的简单演示过程

再给出链式基数排序的实现过程


数排序中可以选择采用
最低有效位基数排序(LSD Radix Sort：Least Significant Digit Radix Sort)或最高有效位基数排序(MSD Radix Sort：Most Significant Digit Radix Sort)
LSD 的排序方式由值的最低位也就是最右边开始,而 MSD 则相反 由值的最高位也就是最左边开始

但由于MSD比LDS复杂 所以一般采用从低位开始排序的算法
例如，如下这个无序的数列需要排序：
　　170, 45, 75, 90, 802, 2, 24, 66
使用 LSD 方式从最低位开始（个位）排序的结果是：
　　170, 90, 802, 2, 24, 45, 75, 66
再继续从下一位（十位）继续排序的结果是：
　　802, 2, 24, 45, 66, 170, 75, 90
再继续从下一位（百位）继续排序的结果是：
　　2, 24, 45, 66, 75, 90, 170, 802
算法实现

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

//******************************基数排序****************************
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define n 10
int a[10]={10,43,13,0,90,44,67,23,16,88};
void Radix_sort(int a[])
{
	int Max=a[0],count=0;
	for(int i=0;i<n;i++)
		Max=max(Max,a[i]);
	while(Max&10)
	{
		Max/=10;
		count++;
	}
	for(int i=1;i<=count;i++)
	{
		int k=0;
		vector<int>v[10];
		for(int j=0;j<n;j++)
		{
			int flag=(int)pow(10.0,count-1);
			int temp=(a[j]/flag)%10;
			v[temp].push_back(a[j]);
		}
		for(int j=0;j<10;j++)
		{
			if(!v[j].size())
				continue;
			quicksort(v[j],0,v[j].size()-1);
		}
		for(int j=0;j<10;j++)
		{
			if(!v[j].size())
				continue;
			for(int m=0;m<v[j].size();m++)
				a[k++]=v[j][m];
		}
	}
}
int main()
{
	Radix_sort(a);
	for(int i=0;i<n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	return 0;
}

算法分析
1.空间复杂度:O(d×n)
2.时间复杂度:O(d×n)
3.基数排序是一种稳定的排序算法
4.基数排序的时间复杂度是O(n*dn)，其中n是排序元素个数，dn是数字位数。这个时间复杂度不一定优于O(nlogn)，dn的大小取决于数字位的选择(比如比特位数)
和待排序数据所属数据类型的全集的大小；dn决定了进行多少轮处理，而n是每轮处理的操作数目。
5.由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数，所以基数排序并不是只能用于整数排序
　如果考虑和比较排序进行对照 基数排序的形式复杂度虽然不一定更小 但由于不进行比较 因此其基本操作的代价较小 而且如果适当的选择基数
　dn一般不大于logn 所以基数排序一般要快过基于比较的排序 比如快速排序
6.基数排序类似于桶排序的思想 把数字按照位数放到10个桶中 每个桶中可以使用计数排序 因为在数据量较小时计数排序具有较高的效率
7.由于分块(桶)的数量是确定 所以可以使用vector来动态在每个桶中存放数字 即较少了内存消耗也减少了书写难度

总结

1.稳定性
指待排序的序列中有两个或两个以上相同的项，在排序前和排序后看这些相同项的相对位置有没有发生变化，如果没有发生变化，即该排序方法是稳定的，
如果发生变化，则说该排序方法是不稳定的。
2.在是三种排序算法中
稳定：直接插入排序 折半插入排序 冒泡排序 归并排序 基数排序 计数排序 桶排序
不稳定：希尔排序 快速排序 简单选择排序 堆排序
即除了“快些（希）选堆”以外 其余都是稳定的排序算法
3.经过一趟排序能够保证一个元素到达最终位置的是冒泡排序、快速排序、简单选择排序、堆排序
4.元素比较次数和原始序列无关的是简单选择排序、折半插入排序。
5.排序趟数和原始序列有关的是交换类排序（冒泡排序 快速排序）。
6.快速排序、归并排序、堆排序的平均时间为O(nlogn) 希尔排序复杂度为O(n^1.3)或O(n^1.5)。
7.对于选择排序 给定含n个元素的输入序列 任何比较排序在最坏情况下都需要Ω(nlogn)次比较来进行排序。
归并排序和堆排序在最坏情况下达到上界O(nlogn) 它们都是渐进最优的排序算法 快速排序在平均情况下达到上界 O(nlogn)。
而三种线性时间排序算法（基数排序 计数排序 桶排序）将突破O(nlogn)的下界 以线性时间运行
8.三种线性时间排序算法是非比较排序 在特定条件下速度快过所有比较排序
9.没有最优的排序算法 根据数据的特性以及大小选择合适的排序算法才是关键
10.最后总结下几种较优排序算法的实用情况：
选择排序
　直接插入排序：在数据基本有序时有较高的性能
　希尔排序：在中等数据量规模(n<1000)具有较高的效率 但不稳定
　快排排序: 在数据量较大且数据趋于无序时具有较高效率 但不稳定且过多递归容易爆内存
　堆排序： 适用于数据量非常大的情况 最差时间复杂度依然为O(n×logn) 这是堆排序最大的优点 但不稳定
　归并排序：和前三种排序算法不同的是归并排序是一种稳定的排序算法 且综合性能很强 在要求稳定性时优先使用归并排序
非选择排序
　计数排序: 适用于数据范围较小的情况 线性时间O(n)运行 稳定 但耗空间较大
　桶排序： 适用于数据是均匀分布的情况 线性时间O(n)运行 稳定 但映射函数的选择对性能的影响巨大
　基数排序：线性时间O(n)运行 稳定 但数据的位数过大时不宜使用