我们做题需要排序都是使用sort，并未系统学习排序方法，那么如果比赛中明确说明禁止使用algorithm，怎么排序呢？
1、冒泡排序
这种排序是非常简单粗暴的，与他一样粗暴的还有选择排序与插入排序，有兴趣自己搜集资料，时间复杂度为
基本思想：
将序列中每个数一一比较，如果发现顺序不对就交换。
代码：
for(int i=n; i>=2; i--)
for(int j=1; j<i; j++)
if(a[j]>a[j+1]) swap(a[i],a[j])
此代码将a数组排为升序
二、桶排序
这种排序方法在众多排序方法中，其简单粗暴可谓是登峰造极，是个人都懂，然而他的适用范围却不广，必须在序列数很小并且为非负整数（<=1000000）的时候才行，时间复杂度为
基本思想：
设序列数字范围为
开一个大小为n的数组（也就是桶），这个数是几就把他装入编号为几的桶，输出时“自然”就变得有序了
代码实现在此略去，因为实在没什么技术含量，请独立编写程序
三、快速排序
这个排序方法是重头戏,因为是平均速度最快的，辅助空间也小（）,时间复杂度，但对初学者来说较难理解
基本思想：
给出需要排序的起始位置l与结束位置r，令mid=(l+r)/2，通过一趟排序将所有比a[mid]小的排到左边，大的排到右边，在分别对左右区间进行快排。
代码实现：
void qsort(int l,int r){
if(l==r) return;//一个数字不需要排序
int mid=a[(l+r)/2],i=l,j=r;
do{
while(a[i]<mid) i++;//找到左边比mid大的数
while(a[j]>mid) j--;//找到右边比mid小的数
if(i<=j){
swap(a[i],a[j]);
i++,j--;//继续找
}
}while(i<=j);//在左边部分和右边部分寻找需要交换的数，不能少了等号，结合下面的代码，想一想为什么
}
if(l<j) qsort(l,j);
if(i<r) qsort(i,r);//若未到两个数的边界，递归搜索左右区间
四、归并排序
归并排序是二分法的经典应用，时间复杂度O(nlogn)（实际上，他比快速排序慢），相较于快速排序，他的优点将在下面举例说明
基本思想：先对l,mid与mid+1,r序列排序，再将两序列合并，合并过程：
令i=k=l，j=mid+1；
比较a[i]和a[j]大小，如果a[i]<=a[j]，则将a[i]复制到r[k]中，i和k同时加一；
反之，将a[j]复制到r[k]中，j和k同时加一；
代码实现：
void msort(int l,int r){
if(l==r) return;//一个数字无需排序
int mid=(l+r)/2,i=l,j=mid+1,k=l;
msort(l,mid);//对左边的序列排序；
msort(mid+1,r);//对右边的序列排序；
//接下来合并
while(i<=mid&&j<=r){
if(a[i]<=a[j]) s[k++]=a[i++];
else s[k++]=a[j++];
}
while(i<=mid) s[k++]=a[i++];//复制左边子序列剩余
while(j<=r) s[k++]=a[j++];//复制右边子序列剩余
for(int i=l; i<=r; i++) a[i]=s[i];//将排序后的数复制到原序列中
}
归并排序比快速排序优势的地方：
归并排序的优势在于，他是稳定的排序，而快速排序是不稳定的。什么叫“稳定的”呢？稳定性是指排序后的序列尽可能保持原来的顺序
举个栗子：
1号 成绩 10分 2号 成绩 9分 3号 成绩 10分
那么稳定的排序后应该是2号、1号、3号而不是2号、3号、1号
这在排序时要求尽可能保持原来的顺序时很有用
并且，归并排序还有一个用处：
经典题：归并排序求逆序对
在序列a中，如果存在这样一对数，满足：
则称其为一对逆序对
现在给你一个序列，让你排序后输出并输出他的逆序对个数
首先，我们很容易想到：冒泡排序正是通过交换所有的逆序对排序的，但是冒泡法因为每次只能统计一个逆序对，速度太慢，不可取，这时候可以用到归并排序：
int ans
void msort(int l,int r){
if(l==r) return;
int mid=(l+r)/2,i=l,j=mid+1,k=l;
msort(l,mid);
msort(mid+1,r);
while(i<=mid&&j<=r){
if(a[i]<=a[j]) s[k++]=a[i++];
else s[k++]=a[j++]，ans+=mid-i+1;//$a_i>a_j$，那么a[i]~a[mid]都比a[j]大并且都在a[j]前面，所以逆序对要统计这么多
}
while(i<=mid) s[k++]=a[i++];
while(j<=r) s[k++]=a[j++];
for(int i=l; i<=r; i++) a[i]=s[i];
}
附：如果你手写了上面的快排并且和sort速度对比，你或许会问：为什么sort快这么多？
sort融合了三种排序方法，代码非常复杂，其中一种就是快速排序，并且sort的空间占用也会比我们手写的快排要小
所以，别去和sort比了，不然你可以发明一个新的sort了~
共 2 条回复
哇哦，ZQS你好牛逼哦！！！你真的太牛逼了！！！对我贼有帮助！！！
棒~