from large to small
选择排序:
- 算法描述：
- 输入a[n]
- a[1]~a[n]
- a[2]~a[n] a[i]~a[n]
找最小的，与a[1]交换
找最小的，与a[2]交换
……
找最小的，与a[i]交换
i=n-1
such as this
代码：
#include<iostream>
using namespace std;
const int Maxn=;
int n,k,i,j;
double temp,a[Maxn];
int main(){
scanf("%d",&n);
for(i=;i<=n;i++)
scanf("%d",&a[i]);
for(i=;i<=n;i++){
k=i;//标记
for(j=i+;j<=n;j++)
if(a[i]<a[j])
k=j;
if(k!=i)
swap(a[i],a[k]);//进行交换
}
for(i=;i<=n;i++)
printf("%d ",a[i]);
return ;
}
冒泡排序：
就是使最矮的数，像鱼吐泡泡一样升上来。
比较相邻两数是否为逆序对，若是则交换，不是则继续搜寻下一位
例如：
第一次
第二次
第三次
第四次
第五次
例题：洛谷P1116
跳过一般的冒泡排序直接进入加强版
这里是求转换次数，并非输出结果
#include<bits/stdc++.h>
using namespace std;
long n,i,j,t,s,a[];
int main()
{
cin>>n;
for(i=;i<=n;i++)
cin>>a[i];
for(i=;i<=n;i++)
for(j=;j<=n-;j++)
if(a[j]>a[j+])
{
swap(a[j],a[j+]);
s++;
};
cout<<s;
return ;
}
输出结果的方法：
//在cout<<s;前加上
for(i=;i<=n;i++)
cout<<a[i]<<“ ”;
//这样既可
在这一题中是由小到大
插入排序：
回忆打扑克的时候的样子，就是选择大小花色来插入适当的位置，
这就叫做插入排序
当读入一个元素时，在已经排序好的序列中，搜寻它正确的位置，再放入读入的元素。
当然，其中有一个不容忽略的重要问题
在插入这个元素前，应当先将将它后面的所有元素后移一位，以保证插入位置的原元素不被覆盖。
示例：
代码在这：
#include<iostream>
using namespace std;
const int MAXN=;
int main()
{
int n,i,j,k;
float temp,a[MAXN];
cin>>n;
for (i=;i<n;i++)
cin>>a[i]; //输入n个数
for(i=; i<n; i++)
{
for(j=i-; j>=; j--) //在前面有序区间中为a[i]找合适的插入位置
if (a[j]<a[i]) break; //找到比a[i]小的位置就退出,插入其后
if (j!=i-)
{
temp=a[i]; //将比a[i]大的数据向后移
for(k=i-;k>j;k--)
a[k+]=a[k]; //将a[i]放在正确位置上
a[k+]=temp;
}
}
for (i=;i<n;i++)
cout<<a[i]<<" "; //输出排序的结果
return ;
}
洛谷P1059
明明的随机数
#include<bits/stdc++.h>
using namespace std;
set<int>s;/*根据适应性原则，这题除了排序还要计算不同数的数量
再接着排序，所以说在STL中适用于这种情况的就是集合
运用集合中不允许存在相同数的原则，即可轻松解决不同数的数量问题
然后在此集合中进行排序，便可轻松进行秒杀*/
int a[];
int main()
{
int n;
cin>>n;
for(int i=;i<=n;i++)
{
cin>>a[i];
s.insert(a[i]);//输入
}
cout<<s.size()<<endl;//计算大小
while(!s.empty())
{
cout<<*s.begin()<<" ";
s.erase(s.begin());
}
}
不完全是排序，有一部分STL表在其中。
快速排序：
快速排序是对冒泡排序的一种改进。
它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小
则可分别对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序的序列为{a[L],a[L+1],a[L+2],……,a[R]}
首先任意选取一个记录（通常可选中间一个记作为枢轴或支点），然后重新排列其余记录，将所有关键字小于它的记录都放在左子序列中
所有关键字大于它的记录都放在右子序列中。由此可以将该“支点”记录所在的位置mid作分界线
将序列分割成两个子序列和。这个过程称作一趟快速排序（或一次划分）。 一趟快速排序的具体做法是：附设两个指针i和j
它们的初值分别为L和R，设枢轴记录取mid，则首先从j所指位置起向前搜索找到第一个关键字小于的mid的记录，然后从i所指位置起向后搜索
找到第一个关键字大于mid的记录，将它们互相交换，重复这两步直至i>j为止。
（直接copyc++一本通的，因为讲的好清楚，自己写的肯定没这么清晰。）
所以说，快排是运用范围最广的。（乱讲分明是sort）
例题：洛谷P1177
直接上代码吧：
#include<iostream>
using namespace std;
int q[];
void qsort(int a,int b)
{
int i,j,mid,p;
i=a;
j=b;
mid=q[(a+b)/];
do
{
while(q[i]<mid)
i++;
while(q[j]>mid)
j--;
if(i<=j)
{
p=q[i];q[i]=q[j];q[j]=p;
i++;j--;
}
}while(i<=j);
if(a<j)
qsort(a,j);
if(i<b)
qsort(i,b);
}
int main()
{
int n,i;cin>>n;
for(i=;i<=n;i++)
cin>>q[i];
qsort(,n);
for(i=;i<=n;i++)
cout<<q[i]<<" ";
return ;
}
其实快排有一个函数，只是理解它的运算更为重要
sort(a[i],b[i],cnt);
桶排序：
这个，就是拿桶倒来倒去。
（开玩笑的啦）划掉
桶排序的思想是若待排序的值在一个明显有限范围内(整型)时
可设计有限个有序桶，待排序的值装入对应的桶（当然也可以装入若干个值）
桶号就是待排序的值，顺序输出各桶的值，将得到有序的序列。
其实很类似于数组排序。（毕竟看着就像啊）
代码：
#include<iostream>
#include <cstring>
using namespace std;
int main(){
int b[],n,i,j,k;
memset(b,,sizeof(b)); //初始化
cin>>n;
for (i=;i<=n;i++)
{
cin>>k; b[k]++; //将等于k的值全部装入第k桶中
}
for (i=;i<=;i++) //输出排序结果
while (b[i]>) //相同的整数，要重复输出
{
cout<<i<<" "; b[i]--; //输出一个整数后，个数减1
}
cout<<endl;
}
有一定的局限性，必须在一定范围内，此话极度重要。
但是利用的好可以对极大部分算法进行优化。
归并排序：
传说中的归并大发
采用分治算法，分而治之
把一整个数组，从中间对半分开，一只分到只有一个数，再进行比对
然后，合并；
整个归并排序中，只有两大步骤：分解，合并
将已有序的子序列合并，得到完全有序的序列；
即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为二路归并。
合并操作：
比较a[i]和a[j]的大小，若a[i]≤a[j]
则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；
否则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。
归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分
接着把左边子区间排序，再把右边子区间排序
最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
好的呀，归并最实用的于求逆序对：
函数哦：
void msort(int s,int t){
if(s==t) return;
int mid=(s+t)/;
msort(s,mid);
msort(mid+,t);
int i=s, j=mid+, 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 ;
} //爱玩的哥们直接调用就行；
例题：洛谷P1908
#include<bits/stdc++.h>
using namespace std;
int p[],ans=;
void merge(int a[],int l,int r)//函数中便是归并大法
{
if(l==r)
return;//如果只有一个数字则返回，无须排序
int half=(l+r)/;
merge(a,l,half);//分解左序列
merge(a,half+,r); //分解右序列
int i=l,j=half+,q=l;//接下来合并
while(i<=half&&j<=r)
{
if(a[i]>a[j])
{
p[q++]=a[j++];
ans+=half-i+;
}
else
p[q++]=a[i++];
}
while(i<=half)//复制左边子序列剩余
p[q++]=a[i++];
while(j<=r) //复制右边子序列剩余
p[q++]=a[j++];
for(i=l;i<=r;i++)
a[i]=p[i];
}
int main()
{
int n,a[];
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
merge(a,,n);
printf("%d",ans);
return ;
}
让我们来比较一下各个排序算法吧！！！
稳定性比较：
插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的。
选择排序、希尔排序、快速排序、堆排序是不稳定的。
好的呀，除了希尔排序和二叉树排序以及二路归并排序都木有，其他的都可以比较
时间复杂性比较：
插入排序、冒泡排序、选择排序的时间复杂度为O（n2）
快速排序、堆排序、归并排序的时间复杂度为O（nlog（2n））
桶排序的时间复杂度为O（n）
其中
在最好情况下，直接插入排序和冒泡排序最快；
在平均情况下，快速排序最快；
在最坏情况下，堆排序和归并排序最快。
