排序算法目录
- 桶排序（Bucket Sort）
- 冒泡排序（Bubble Sort）
- 选择排序（Selection Sort）
- 插入排序（Inserction Sort）
- 快速排序（Quick Sort）
- 归并排序（Merge Sort）
- （挖个坑以后再补）
桶排序（Bucket sort）
桶排序是将若干个数经过某种函数映射关系，把这若干个数分到几个不同的桶（区间）中，再在区间内部再进行排序（可以继续递归进行桶排序，也可以利用其他排序算法）。
桶排序的关键在于
1. 在有限的空间内设置较多的桶
2. 通过合适的函数映射关系使得每个数都映射到一个桶中，并且使得这若干个数据可以均匀分布在这几个桶中
举个很简单的例子
假设有一系列整数：29,25,3,49,9,37,21,43.
0-9区间内有：3,9
10-19区间内有：
20-29区间内有：29,25,21
30-39区间内有：37
40-49区间内有：49,43
通过将整数分为[0,9]，[10,19]，[20,29]等区间的映射关系就将这若干个整数分到一系列桶内
再在桶内进行排序
0-9区间内有：3,9
10-19区间内有：
20-29区间内有：21,25,29
30-39区间内有：37
40-49区间内有：43,49
之后再遍历这五个桶就得到排序完成的整数数列：3,9,21,25,29,37,43,49
联系图片便于理解
将这几个数字按照映射关系放入桶中
再将这几个桶按照数字大小关系排序
最简单的桶排序
C++代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,a[N],b[N];
void bucket_sort(int a[],int l,int r)//桶排序（一一对应型）
{
for(int i=l;i<=r;i++)//映射到数组b
{
b[a[i]]++;
}
for(int i=0,j=0;i<N;i++)//顺序遍历桶b恢复到原数组a
{
while(b[i]--)
{
a[j]=i;
j++;
}
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);//输入数组
bucket_sort(a,0,n-1);//进行桶排序
for(int i=0;i<n;i++) printf("%d ",a[i]);//打印数组
return 0;
}
这种桶排序算法我将其称为一一对应型（映射数组b相对a总有一个相同的数值对应）
（这应该都可以看懂吧！好啦要加难度啦！
取最高位数字分类的桶排序
C++代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,a[N];
void bucket_sort(int a[],int l,int r)
{
int max=a[0];
for(int i=1;i<=r-l;i++)
{
if(a[i]>max) max=a[i];
}//找到输入数组中的最大数值
const int bucketnum=10;
vector<int> b[bucketnum]; //确定10个桶(10个二维数组)
int bucketsize=1;
while(max)
{
max/=10;
bucketsize*=10;
}
bucketsize/=10; //确定桶的最大尺寸
//如果数据最大值为99，则桶的尺寸为10
//同理数据最大值为999，桶的尺寸为100
for(int i=0;i<n;i++)
{
int dim=a[i]/bucketsize; //根据最高位数字与桶的对应关系映射到相应的桶
//映射函数公式 a[i]/bucketsize
b[dim].push_back(a[i]); //入桶
for(int j=b[dim].size()-1;j>0;j--) //每次入桶后随即进行插入排序
{
if(b[dim][j]<b[dim][j-1]) swap(b[dim][j],b[dim][j-1]);
}
}
for(int i=0,k=0;i<bucketnum;i++)
{
for(int j=0;j<b[i].size();j++)
{
a[k++]=b[i][j];
}
}//遍历桶b恢复到原数组a
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);//输入数组
bucket_sort(a,0,n-1);//进行桶排序
for(int i=0;i<n;i++) printf("%d ",a[i]);//打印数组
return 0;
}
建议桶排序和插入排序一同食用更佳！
冒泡排序（Bubble Sort）
冒泡排序是一种将若干个数从前到后依次遍历每一个数，并且在遍历过程中将该数与其余个数进行顺序判断。若顺序正确，则顺序向下；若顺序有误，则交换两数位置的排序方法。
（ 该算法名称由来是因为每次最小的元素会像可乐中的气泡一样浮到最上层，故名“冒泡排序”）
联系图片便于理解
C++代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,a[N];
void bubble_sort(int a[],int l,int r)
{
for(int i=0;i<=r-l;i++) //前驱遍历变量
{
for(int j=i;j<=r-l;j++) //比较遍历变量
{
if(a[i]>a[j]) swap(a[i],a[j]); //如果顺序不一致则交换位置
}
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);//输入数组
bubble_sort(a,0,n-1);
for(int i=0;i<n;i++) printf("%d ",a[i]);//打印数组
return 0;
}
时间复杂度 O(n2) （所以我很少用）
选择排序（Selection Sort）
选择排序是一种重复在未排序元素中寻找最大（最小）元素并放在首位置（尾位置）的排序方法
（该算法名称由于每次会挑选出最大（最小）的元素，故称“选择排序”）
联系图片便于理解
C++代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,a[N];
void selection_sort(int a[],int l,int r)
{
for(int i=0;i<=r-l;i++) //前驱遍历变量
{
int min=i; //最小元下表变量
for(int j=i;j<=r-l;j++) //比较遍历变量
{
if(a[min]>a[j]) swap(a[min],a[j]); //将最小元排在前
}
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);//输入数组
selection_sort(a,0,n-1);
for(int i=0;i<n;i++) printf("%d ",a[i]);//打印数组
return 0;
}
时间复杂度 O(n2) （所以我基本不用）
插入排序（Inserction Sort）
插入排序是一种将未排序部分元素按照自身与已排序部分元素大小关系来插入已排序部分的一种排序算法
(有点类似打扑克牌发牌时将扑克牌抓在手上有序摆放的味道)
联系图片便于理解
C++代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,a[N];
void inserction_sort(int a[],int l,int r)
{
for(int i=0;i<=r-l;i++) //
{
int key=a[i],j=i-1;
while((j>=0) && key<a[j])
{
a[j+1]=a[j];
j--;
}
a[j+1]=key;
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);//输入数组
inserction_sort(a,0,n-1);
for(int i=0;i<n;i++) printf("%d ",a[i]);//打印数组
return 0;
}
不过我还是喜欢STL写法 （STLnb！）
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,a[N];
void inserction_sort(int a[],int l,int r)
{
multiset<int> b;
for(int i=0;i<=r-l;i++) b.insert(a[i]); //将数组中元素插入set中
multiset<int>::iterator it; //迭代器
int i=0;
for(it=b.begin();it!=b.end();it++) //将set中自动排好的元素反插回数组
{
a[i]=*it;
i++;
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);//输入数组
inserction_sort(a,0,n-1);
for(int i=0;i<n;i++) printf("%d ",a[i]);//打印数组
return 0;
}
快速排序（Quick Sort）
快速排序是一种采用分治的思想进行排序的算法(快排YYDS!)
基本步骤
1.从数组中挑选出一个数字作为基准（不过我一般挑选中间的数,这样鲁棒性更强）
2.将小于该基准数的元素放在左边，大于该基准数的元素放在右边
3.重复在基准数两侧区间递归以上步骤直到区间长度为1
4.将各个小区间合并
联系图片便于理解
但是实际码的时候还是这张图好使
C++代码
#include<bits/stdc++.h>
using namespace std;
void quick_sort(int q[],int l,int r)
{
if(l==r) return;
int x= q[l+r>>1], i=l-1, j=r+1; //定义i,j两指针
while ( i < j )
{
do i++; while (q[i]<x);
do j--; while (q[j]>x); //分别移动两指针
if(i<j) swap(q[i],q[j]); //当左侧大于基准值，右侧小于基准值时
} //交换两数
quick_sort(q,l,j);
quick_sort(q,j+1,r); //分别递归以上操作
}
int main()
{
int n;
scanf("%d",&n);
int q[n];
for(int i=0;i<n;i++) scanf("%d",&q[i]);
quick_sort(q,0,n-1);
for(int i=0;i<n;i++) printf("%d ",q[i]);
return 0;
}
归并排序（Merge Sort）
归并排序和快排类似同样是采用分治思想的排序算法
基本步骤
1.取一个合并数组
2.将原数组分为平分为两部分，对两部分分别进行递归操作使其排序完成
3.同时遍历该数组的两部分，并比较遍历时的对应元素，从中将较小的元素放在合并数组中
4.将最后数组遍历时剩余的元素放在合并数组中
联系图片便于理解
C++代码
#include<bits/stdc++.h>
using namespace std;
const int N = 10e5+10;
int q[N],tmp[N];
void merge_sort(int q[],int l,int r)
{
if(l<=r) return;
int mid= l+r>>1;
merge_sort(q,l,mid);
merge_sort(q,mid+1,r); //将数组分为两部分并排好序
int k=0,i=l,j=mid+1;
while(i<=mid && j<=r)
{
if(q[i]<=q[j]) tmp[k++]=q[i++];
else tmp[k++]=q[j++];
} //遍历数组的两部分并同时比较其大小
while (i<=mid) tmp[k++]=q[i++];
while (j<=r) tmp[k++]=q[j++]; //将两部分数组未比较大小的剩余元合并到新数组内
for(i=l,j=0;i<r;i++,j++) q[i]=tmp[j]; //将新数组的顺序关系恢复到原数组
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&q[i]);
merge_sort(q,0,n-1);
for(int i=0;i<n;i++) printf("%d ",q[i]);
return 0;
}
Referces:
[1]Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein.Introduction to Algorithms.
[2] 快速排序算法的证明与边界分析
[3]Ronald L. GrahamDonald E. KnuthOren Patashnik.Concrete Mathematics: A Foundation for Computer Science
Orz
# tql