今天讲了堆排序，就这以前学过的排序方法，我来做一个总结
1、选择排序：
选择排序是比较基础的排序方法，需要两个循环，用于对每一个数进行查找和替换，不用多说，代码如下：
<span style="color:#000000;BACKGROUND-COLOR: #ffff99">#include<cstdio>
<span style="font-size:12px;">int a[101];
</span>int main()
{
int n,t,i,j;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(a[i]>a[j])
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
for(i=0;i<n;i++)
printf("%d ",a[i]);
}</span>其实也没什么优点，关键是好想，对于初学者，是必须掌握的
2、冒泡排序：
跟选择排序差不多，只是选择排序先从前面确定数，而冒泡排序恰恰相反
代码如下：
<span style="color:#000000;BACKGROUND-COLOR: #ffff99">#include<cstdio>
int a[101];
int main()
{
int n,t,i,j;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n-1;i++)
for(j=0;j<n-i-1;j++)
if(a[j]>a[j+1])
{
t=a[j+1];
a[j+1]=a[j];
a[j]=t;
}
for(i=0;i<n;i++)
printf("%d ",a[i]);
}</span>这个就不必多说了吧
3、桶排序：
这个其实根本不叫排序，只是把一个数装入与它数值一样的数组小房间里罢了，再一个个输出
代码如下：
<span style="color:#000000;BACKGROUND-COLOR: #ffff99">#include<cstdio>
int a[100001];
int main()
{
int n,i,k;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&k);
a[k]++;
}
for(i=0;i<100001;i++)
while(a[i])
{
printf("%d ",i);
a[i]--;
}
}</span>
桶排序的优点在于，当数据个数很大时，几乎不会耗时，但一旦单个数值很大的话，会出现数组崩溃或无法设立那么大的数组
4、快速排序：
快速排序是指一个数组从中间划开，中间那个数为m，当 l > m && r < m 时，交换 l 和 r，这个方法可以跳过符合标准的数
代码如下：
<span style="color:#000000;BACKGROUND-COLOR: #ffff99">#include<cstdio>
int a[101];
void sort(int l,int r)
{
int i,j,m,t;
i=l,j=r;
m=(l+r)/2;//一刀两断
do//先做一遍再说
{
while(a[i]<a[m]) i++;
while(a[j]>a[m]) j--;
if(i<=j)
{
t=a[i],a[i]=a[j],a[j]=t;//作交换
i++;
j--;
}
}while(i<=j);
if(l<j) sort(l,j);//二分继续找
if(i<r) sort(i,r);
}
int main()
{
int n,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(1,n);
for(i=1;i<=n;i++)
printf("%d ",a[i]);
}</span>快排虽快，但是极不稳定，真正稳定的排序方法，是下面的归并排序
5、归并排序
归并排序是指将数组划分成一个个小分段，一个个小分段进行排序，最后在合并起来排序，有二分查找的思想在里面
代码如下：
<span style="color:#000000;BACKGROUND-COLOR: #ffff99">#include<cstdio>
int a[101];
void sort(int l,int r)
{
int s[101]={0};
int m,i,j,k;
if(l==r)//只剩一个就无视了
return;
m=(l+r)/2;
sort(l,m);//二分查找
sort(m+1,r);
i=l,j=m+1,k=l;
while(i<=m&&j<=r)
{
if(a[i]<=a[j])//s 数组的挑选
{
s[k]=a[i];
i++;
k++;
}
else
{
s[k]=a[j];
j++;
k++;
}
}
while(i<=m)//剩下的一口气塞进去
{
s[k]=a[i];i++;k++;
}
while(j<=r)
{
s[k]=a[j];k++;j++;
}
for(i=l;i<=r;i++)//有借有还
a[i]=s[i];
}
int main()
{
int n,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(1,n);
for(i=1;i<=n;i++)
printf("%d ",a[i]);
}</span>归并排序非常的稳定，且时间复杂度极低
下面来看一个例题 ( ⊙ o ⊙ )
输入
第一行是一个整数n，表示该排列有n个数（n <= 100000)。
第二行是n个不同的正整数，之间以空格隔开，表示该排列。
输出
输出该排列的逆序数。
样例输入6
2 6 3 4 5 1 样例输出8
这道题就可以用归并排序，交换的时候加一下交换数就行了
代码如下：
<span style="color:#000000;BACKGROUND-COLOR: #ffff99">#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int a[100001],b[100001],n;
long long g;
void msort(int l,int r)
{
int m,i,j,k;
m=(l+r)/2;
if(l==r)
return;
msort(l,m);
msort(m+1,r);
i=l;
j=m+1;
k=l;
while(i<=m&&j<=r)
{
if(a[i]>a[j])
{
b[k]=a[j];
g=g+m+1-i;//加上比其小的数的个数
j++;
k++;
}
else
{
b[k]=a[i];
i++;
k++;
}
}
while(i<=m)
{
b[k]=a[i];
i++;
k++;
}
while(j<=r)
{
b[k]=a[j];
j++;
k++;
}
for(i=l;i<=r;i++)
a[i]=b[i];
return;
}
int main()
{
int i;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
msort(1,n);
printf("%lld",g);
}</span>
几乎就是复制粘贴的啊
6、堆排序
其实就是使用二叉树的特性来排序，通过交换来将最小数转移到根节点，再删除根节点，重新建树
可使用algorithm的函数
代码如下：
<span style="color:#000000;BACKGROUND-COLOR: #ffff99">#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[10005];
int k;
int main()
{
int n,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
push_heap(a+1,a+i+1,greater<int>());//建树
}
for(i=1;i<=n;i++)
{
printf("%d ",a[1]);//输出树根
pop_heap(a+1,a+n-i+2,greater<int>());//删除树根，重新建树
}
}</span>跟快排一样，比较的不稳定，但是很方便
下面再来看一个例题 ( ⊙ o ⊙ )
合并果子
题目描述
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。 多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。 假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。例如有3种果子，数目依次为1，2，9。可以先将
1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
输入
第1行:一个整数n（1≤n≤10000），表示果子的种类数。第2行:包含n个整数，用空格分隔，第i个整数ai（1≤ai≤20000）是第i种果子的数目。
输出
一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于2^31。
样例输入
3
1 2 9
样例输出
15
这道题就可以使用堆排序啦 ~ ( ≧ ▽ ≦ ) /~
使用的总力气用一个变量，一直加加就好啦
代码如下：
<span style="color:#000000;BACKGROUND-COLOR: #ffff99">#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[10005];
int k;
int main()
{
//freopen("fruit.in","r",stdin);
//freopen("fruit.out","w",stdout);
int n,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
push_heap(a+1,a+i+1,greater<int>());
}
int x;
for(i=1;i<n;i++)
{
x=a[1];
pop_heap(a+1,a+n-i+2,greater<int>());
x+=a[1];
pop_heap(a+1,a+n-i+1,greater<int>());
k+=x;
a[n-i]=x;
push_heap(a+1,a+n-i+1,greater<int>());
}
printf("%d",k);
}</span>
除了这种方法外，还可以使用优先队列
priority_queue<int,vector<int>,greater<int> >h;//注意：int> >h 之间必须有一个空格
代码如下：
<span style="color:#000000;BACKGROUND-COLOR: #ffff99">#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
priority_queue<int,vector<int>,greater<int> >h;
int main()
{
//freopen("fruit2.in","r",stdin);
//freopen("fruit2.out","w",stdout);
int n,k,i;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&k);
h.push(k);
}
k=0;
int x=0;
for(i=0;i<n-1;i++)
{
x+=h.top();
h.pop();
x+=h.top();
h.pop();
k+=x;
h.push(x);
x=0;
}
printf("%d",k);
}</span>黑科技啊 ╮(╯▽╰)╭，这玩意可以把推进去的数自动排序，妈妈再也不用担心我的排序了 O(∩_∩)O哈哈~
好了，这就是我总结的排序方法啦，喜欢或者对你有所帮助的话，别忘了顶一下哟，蟹蟹 ~(≧▽≦)/~