【算法】排序

排序算法在信息学非常常用。Hello！大家好，我是@学霸小羊，今天讲几个排序算法。

1.“打擂台”排序

思路：a[ i ]和a[ j ]打擂台（i<j）。

这个方法简单易懂，只需要看看需不需要交换。按从大到小排，如果a[ i ]<a[ j ]，那就要换；从小到大排，如果a[ i ]>a[ j ]，那就要换。

#include<bits/stdc++.h>
using namespace std;
int a[1001],n;
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}//从大到小排序 for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i<j){if(a[i]<a[j]) swap(a[i],a[j]);}else if(j<i){if(a[j]<a[i]) swap(a[i],a[j]);}else continue;}}for(int i=1;i<=n;i++){cout<<a[i]<<" ";}return 0;
}

你以为这就完了吗？才！怪！

上面代码的时间复杂度是O(n^2)！算是比较大的了。

话说其实可以简化一下，将中间的双重循环变一下。

for(int i=1;i<n;i++){for(int j=i+1;j<=n;j++){if(a[i]<a[j]) swap(a[i],a[j]);}
}

这样接可以稍微缩短一下时间，时间复杂度变为(n+(n-1)+(n-1)+···+1)。

2.冒泡排序

这儿排序可以用一句话形容：将最大值冒上去。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[1001],n;
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}//从小到大排序 for(int i=n;i>1;i--){for(int j=2;j<=n;j++){if(a[j-1]>a[j]) swap(a[j],a[j-1]);}}for(int i=1;i<=n;i++){cout<<a[i]<<" ";}return 0;
}

3.插入排序

将变量取出，然后找到一个合适的位置插进去。

就是一个字：找！

代码:

#include<bits/stdc++.h>
using namespace std;
int a[1001],n;
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}//从小到大排序 int j;int current;for(int i=0; i<n; i++){j = i ;current = a[i];while(j>=0 && a[j-1]> current){a[j] = a[j-1];j--;}a[j] = current;}for(int i=1;i<=n;i++){cout<<a[i]<<" ";}return 0;
}

4.sort()排序

这是一个c++标准函数。

sort(函数名+开始下标，函数名+结束下标，其他);

话都不多说，上代码！

#include<bits/stdc++.h>
using namespace std;
int a[1001],n;
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}//从小到大排序sort(a+1,a+n+1);for(int i=1;i<=n;i++){cout<<a[i]<<" ";}return 0;
}

好啦！今天就讲到这，小伙伴们，拜拜！