归并的
```cpp
void msort(int s,int t)
{
if(s==t) return; //如果只有一个数字则返回，无须排序
int mid=(s+t)/2;
msort(s,mid); //分解左序列
msort(mid+1,t); //分解右序列
int i=s, j=mid+1, k=s; //接下来合并
while(i<=mid && j<=t)
{
if(a[i]<=a[j])
{
r[k]=a[i]; k++; i++;
}else{
r[k]=a[j]; k++; j++;
}
}
while(i<=mid) //复制左边子序列剩余
{
r[k]=a[i]; k++; i++;
}
while(j<=t) //复制右边子序列剩余
{
r[k]=a[j]; k++; j++;
}
for(int i=s; i<=t; i++) a[i]=r[i];
return 0;
}
```
by _不赦_ @ 2017-11-06 21:35:51
小优化冒泡
```cpp
bool ok;
for(int i=n-1; i>=1; i--)
{
ok=true; //判断是否有交换
for(int j=1; j<=i; j++)
{
if(a[j]>a[j+1])
{
swap(a[j],a[j+1]);
ok=false;
}
}
if(ok==true) break; //没有交换就退出
}
```
by _不赦_ @ 2017-11-06 21:37:31
你像极了那些。。。
by aface0427 @ 2017-11-06 21:38:15
插入的
```cpp
for(i=0; i<n; i++)
{
for(j=i-1; j>=0; j--) //在前面有序区间中为a[i]找合适的插入位置
if (a[j]<a[i]) break; //找到比a[i]小的位置就退出,插入其后
if (j!=i-1)
{
temp=a[i]; //将比a[i]大的数据向后移
for(k=i-1;k>j;k--)
a[k+1]=a[k]; //将a[i]放在正确位置上
a[k+1]=temp;
}
}
```
by _不赦_ @ 2017-11-06 21:38:15
@[aface0427](/space/show?uid=28053) 别队形了，蒟蒻的我只想默默地存个代码。。
by _不赦_ @ 2017-11-06 21:38:55
@[\_不赦\_](/space/show?uid=56482) 可以把插排换成优先队列啊2333
by moye到碗里来 @ 2017-11-06 21:39:18
垃圾桶
```cpp
#include<iostream>
#include <cstring>
using namespace std;
int main()
int b[101],n,i,j,k;
memset(b,0,sizeof(b)); //初始化
cin>>n;
for (i=1;i<=n;i++)
{
cin>>k; b[k]++; //将等于k的值全部装入第k桶中
}
for (i=0;i<=100;i++) //输出排序结果
while (b[i]>0) //相同的整数，要重复输出
{
cout<<i<<" "; b[i]--; //输出一个整数后，个数减1
}
cout<<endl;
}
```
by _不赦_ @ 2017-11-06 21:39:41
@[moye到碗里来](/space/show?uid=52576) 有道理！
by _不赦_ @ 2017-11-06 21:39:59
逆序对
```cpp
void msort(int s,int t)
{
if(s==t) return; //如果只有一个数字则返回，无须排序
int mid=(s+t)/2;
msort(s,mid); //分解左序列
msort(mid+1,t); //分解右序列
int i=s, j=mid+1, k=s; //接下来合并
while(i<=mid && j<=t)
{
if(a[i]<=a[j])
{ r[k]=a[i]; k++; i++;
}else{
r[k]=a[j]; k++; j++;
ans+=mid-i+1; //统计产生逆序对的数量
}
}
while(i<=mid) //复制左边子序列剩余
{
r[k]=a[i]; k++; i++;
}
while(j<=t) //复制右边子序列剩余
{
r[k]=a[j]; k++; j++;
}
for(int i=s; i<=t; i++) a[i]=r[i];
return 0;
}
```
by _不赦_ @ 2017-11-06 21:40:55
#In the end:
##1.稳定性比较
插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的。
选择排序、希尔排序、快速排序、堆排序是不稳定的。
##2.时间复杂性比较
插入排序、冒泡排序、选择排序的时间复杂性为O(n2)；快速排序、堆排序、归并排序的时间复杂性为O(nlog2n)；桶排序的时间复杂性为O(n);
若从最好情况考虑，则直接插入排序和冒泡排序的时间复杂度最好，为O(n)，其它算法的最好情况同平均情况相同；若从最坏情况考虑，则快速排序的时间复杂度为O(n2)，直接插入排序和冒泡排序虽然平均情况相同，但系数大约增加一倍，所以运行速度将降低一半，最坏情况对直接选择排序、堆排序和归并排序影响不大。
由此可知，在最好情况下，直接插入排序和冒泡排序最快；在平均情况下，快速排序最快；在最坏情况下，堆排序和归并排序最快。
##3.辅助空间的比较
桶排序、二路归并排序的辅助空间为O(n)，快速排序的辅助空间为O(log2n)，最坏情况为O(n)，其它排序的辅助空间为O(1);
##4.其它比较
插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。
当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。
若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。
当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。
当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序
快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
by _不赦_ @ 2017-11-06 21:42:02