题解 | #输入整型数组和排序标识,对其元素按照升序或降序进行排序#

输入整型数组和排序标识,对其元素按照升序或降序进行排序

http://www.nowcoder.com/practice/dd0c6b26c9e541f5b935047ff4156309

题目的主要信息:

  • 输入整型数组和排序标识,对其元素按照升序或降序进行排序
  • 0代表升序排序,1代表降序排序。

方法一:

保存这n个元素,直接调用库函数sort函数进行排序,默认的sort函数是升序排序,因此如果需要进行降序排序,需要用一个比较函数compare传入参数改变顺序。

具体做法:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

bool compare(int a,int b){
    return a>b;
}
int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)//输入
    {
        cin>>a[i];
    }
    int flag;
    cin>>flag;
    if(!flag){//当flag=0时升序排序
        sort(a.begin(),a.end());
    }
    else{//降序排序
        sort(a.begin(),a.end(),compare);
    }
    for(int i=0;i<n;i++){//输出
        cout<<a[i]<<" ";
    }
    cout<<endl;
}

复杂度分析:

  • 时间复杂度:O(nlog2n)O(nlog_2n),sort排序是快速排序。
  • 空间复杂度:O(n)O(n),用a储存n个元素。

方法二:插入排序

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对未排序的数据,在已排序序列中从后向前扫描,找到相应位置并插入。 插入排序算法的一般步骤:

  1. 从第一个元素开始,该元素可以认为已被排序;
  2. 从第二个元素开始,在已经排序的元素序列中从后向前扫描;
  3. 升序排序:如果已排序的元素大于新元素,将该元素移到下一个位置;
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  5. 将新元素插入到该位置后,重复2~5。 alt

具体做法:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

void Insert_Sort(vector<int> Arr,int flag)
{
    // 假设第一个元素已经排好序,将后面的元素有序插入到已经排好序的元素中,所以从第二个元素开始(索引为1)
	for (int i = 1; i < Arr.size(); i++)
	{
        // 将第一个需要排序的元素,与已经排好序的对比,找到正确的插入位置。
        int j = i-1;
        int value = Arr[i];
		if(flag){//降序排序
            while(j >= 0 && Arr[j] < value){
                Arr[j+1] = Arr[j];
                j--;
            }
        }else{//升序排序
            while(j >= 0 && Arr[j] > value){
                Arr[j+1] = Arr[j];
                j--;
            }
        }
        Arr[j+1] = value;
	}
    //输出排序后的数组
	for (int i = 0; i < Arr.size(); i++)
	{
		cout << Arr[i] << " ";
	}
	cout << endl;
}
int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)//输入
    {
        cin>>a[i];
    }
    int flag;
    cin>>flag;
    Insert_Sort(a, flag);//插入排序
    cout<<endl;
}

复杂度分析:

  • 时间复杂度:O(n2)O(n^2),最坏情况下,每次都要与所有排好序的元素比较。
  • 空间复杂度:O(n)O(n),用a储存n个元素。
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务