P1177题解

· · 题解

提供三种做法。

题目大意

给定一个数组，将数组的元素排序后输出。

题目解答

一、 冒泡排序

算法原理：

用 a 数组表示要排序的数组。

第一步：将 a 数组的第 i 个元素 a_i 和第 i+1 个元素 a_{i+1} 比较大小。

第二步：循环重复第一步的操作。

第三步：用 b 数组把排序后的结果存下来，输出即可。

代码：

输入完后，循环比较一下 a 数组的某对相邻元素的哪个大哪个小，最后输出即可。

二、快速排序

算法原理：

用 a 数组表示要排序的数组。

第一步：选择一个数 x，将 ≥x 的数移到 a 数组的左边或右边；将 <x 的数移到 a 数组的右边或左边。

第二步：a 数组的左边和右边分别进行排序。两边的排序都重复第一步的操作。

第三步：重复前两步的操作。

第四步：两边都排好后，再把全部排一下。

第五步：输出。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int N,a[maxn];
void quicksort(int left,int right){
    if(left>=right)return;
    int key=left+1+(int)rand()%(right-left);
    swap(a[key],a[left]);
    key=left;
    int i=left+1,j=right;
    while(i<j){ 
        while(a[i]<a[key]&&i<j)i++;//在数组左边，找比分界值大的数 
        while(a[j]>a[key]&&i<j)j--;//在数组右边，找比分界值小的数 
        if(i>=j)break;
        swap(a[i],a[j]);//交换
        i++;
        j--;
    }
    if(a[i]>a[key]){//排序 
        swap(a[i-1],a[key]);
        key=i-1;
    }else{
        swap(a[i],a[key]);
        key=i;
    }
    quicksort(left,key-1);
    quicksort(key+1,right);
}
int main(){
    srand((unsigned)time(NULL));
    int i;
    scanf("%d",&N);
    for(i=1;i<=N;i++)scanf("%d",&a[i]);//输入 
    quicksort(1,N);
    for(i=1;i<=N;i++)printf("%d ",a[i]);//输出 
    cout<<endl;
    return 0;
}

三、STL

利用 STL 库里的 sort 函数来排序。sort 的含义是：

例如，

sort(a+1,a+n+1)。

这里 a+1 表示从 a 数组的第一个元素开始排序；a+n+1 表示排序到 a 数组的第 n 个元素结束。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,a[maxn]; 
int main(){
    int i;
    cin>>n;
    for(i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    for(i=1;i<=n;i++)cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}