算法>排序算法大合集
翻了翻很久以前写的算法报告，现在整理一下。
由难度从简单到难排序。
桶排序、冒泡排序、选择排序、快速排序。
最简单粗暴——桶排序
（一）桶排序原理
桶排序，是一个目前速度最快的一种排序
基本思想是将无序列数依次装进一个按元素名命名数组中
最后挨个判断每个“桶”中有没有数
有的话将其输出的一种快速排序
优点：速度最快
缺点：只限用于小数据排序，通常会造成巨大的空间损失
适用于小规模且有一定数据范围的数据排序
（二）复杂度分析
时间复杂度：O(n)
空间复杂度：依数据范围而定，一般较大
（三）代码实现
#include<iostream>
#include<cstdio>
using namespace std;
int n;//有n个数要进行排序
int maxn=-1;//设定一个代表着输入数据最大的变量，初始值设为-1
int minn=100010; //设定一个代表着输入数据最小的变量，初始值设为100010
int a[100005];//假设数据大小不超过十万
int main(){cin>>n;for(int i=1;i<=n;i++){int k;//定义一个临时变量cin>>k;//输入 a[k]++;//桶排序重要的一点，将每个元素都装在相应的桶中 if(minn>k)//打擂台 {minn=k;}if(maxn<k)//打擂台 {maxn=k;}}for(int i=minn;i<=maxn;i++)//从数据的最小至大上限依次判断 {while(a[i]!=0)//如果该桶中还存有数据，就将它输出，并将该桶中元素的数量-1，直至数量为0 {cout<<i<<" ";//输出 a[i]--;//数量-1 }}cout<<endl;//随意换行一下 return 0;
}
（四）模拟过程
假设我们要为15个数进行排列：
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5
输入第一个1时，a[1]从0开始+1，结果为1
a[1]=1
输入第一个2时，a[2]从0开始+1，结果为1
a[2]=1
输入第一个3时，a[3]从0开始+1，结果为1
a[3]=1
输入第一个4时，a[4]从0开始+1，结果为1
a[4]=1
输入第一个5时，a[5]从0开始+1，结果为1
a[5]=1
输入第一个6时，a[6]从0开始+1，结果为1
a[6]=1
输入第一个7时，a[7]从0开始+1，结果为1
a[7]=1
输入第一个8时，a[8]从0开始+1，结果为1
a[8]=1
输入第一个9时，a[9]从0开始+1，结果为1
a[9]=1
输入第一个10时，a[10]从0开始+1，结果为1
a[10]=1
输入第二个1时，a[1]从1开始+1，结果为2
a[1]=2
输入第二个2时，a[2]从1开始+1，结果为2
a[2]=2
输入第二个3时，a[3]从1开始+1，结果为2
a[3]=2
输入第二个4时，a[4]从1开始+1，结果为2
a[4]=2
输入第一个5时，a[5]从1开始+1，结果为2
a[5]=2
最后，按所有存在数据的数组的顺序排序，输出，即可得到一串有序的数据，即：
1 1 2 2 3 3 4 4 5 5 6 7 8 9 10
（五）总结
桶排序基本上是一种“不用动脑筋”的排序，直接将数据存储在数组内，最后输出的一个过程，虽时间复杂度最快，但往往会浪费巨大的空间复杂度，仅仅适用于小规模的数据排序。
有趣的排序——冒泡排序
（一）冒泡排序原理
重复访问未排序的元素序列，依次审查相应两个元素，若顺序错误，则将其交换，最后得到一个已排序的序列
优点：原理简单，易于理解
缺点：效率低
适用于小规模数据排序
（二）复杂度分析
时间复杂度：O(n*n)
空间复杂度：O(1)
（三）代码实现
#include<iostream>
#include<cstdio>
using namespace std;
int n;//定义一个变量，设有n个数
int a[100005];//假设数量不超过10的5次方
int main(){cin>>n;//输入 for(int i=1;i<=n;i++)//输入数据 {cin>>a[i]
