自学内容网 自学内容网

【算法】排序

排序算法在信息学非常常用。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;
}

好啦!今天就讲到这,小伙伴们,拜拜!

(本文章禁止转载)


原文地址:https://blog.csdn.net/yangyanbin_sam/article/details/139234725

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!