备战acm校队第二天。
实惨，排序学了好几年了，还是没有熟练，意难平啊。特此打开oi-wiki，从头到尾把排序敲一遍。
选择排序
比较简单。就是把数组里最大数找出来放到最后，然后再把第二大的找出来放在倒数第二位，依次类推，排序就结束了。
注：TMD，Dev-C++原来不能把中文注释在代码，不然拷贝出来会乱码。所以选择排序我不注释了
点击查看代码
#include<bits/stdc++.h>
int a[100005],n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=n;i>=1;--i)
{
for(int j=1;j<=i;j++)
{
if(a[j]>a[i]) swap(a[j],a[i]);
}
}
for(int i=1;i<=n;++i)
{
printf("%d ",a[i]);
}
}
冒泡排序
每一个位置的数都与后面的数比较，只要后面小于前面，就交换，保持单调递增。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int a[100005],n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n-1;++j)
{
if(a[j]>a[j+1]) swap(a[j],a[j+1]);
}
}/*每一次操作都能保证未被排序中最大的数被交换到最后一位（相对最后一位）*/
for(int i=1;i<=n;++i)
{
printf("%d ",a[i]);
}
}
插入排序
以把小的往前插为例：每当找到小的数，就把这个数存下来，然后把这个数前面比它大的往后移，空出一个位置放入这个数。如果没有比它大的，也就没法移动了。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int a[100005],n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;++i)
{
int k=a[i];
int j=i-1;
while(j>=0&&a[j]>k)//移动过程
{
a[j+1]=a[j];
j--;
}
a[j+1]=k;
}
for(int i=1;i<=n;++i)
{
printf("%d ",a[i]);
}
}
选择排序
随便找一个数x，从左到右找一个比x大的数，然后再从右往左找一个比x小的数，如果不满足递增则交换，重复多次直至左边超过右边。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int a[10005],n;
void quicksort(int l,int r)
{
int mid=a[l+r>>1];
int i=l,j=r;
do
{
while(a[i]<mid) i++;
while(mid<a[j]) j--;
if(i<=j)
{
swap(a[i],a[j]);
i++;
j--;
}
}while(i<=j);
if(l<j) quicksort(l,j);
if(i<r) quicksort(i,r);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
quicksort(1,n);
for(int i=1;i<=n;i++)
{
printf("%d ",a[i]);
}
}
我累了，还有的排序明天再说吧。
标签：排序,复习,int,代码,100005,算法,using,include From： https://www.cnblogs.com/Fire-Colder/p/18408510