题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1018
基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题
给出N个整数,对着N个整数进行排序 Input 第1行:整数的数量N(1 <= N <= 50000) 第2 - N + 1行:待排序的整数(-10^9 <= A[i] <= 10^9) Output 共n行,按照递增序输出排序好的数据。 Input示例 5 5 4 3 2 1 Output示例 1 2 3 4 5
使用时间复杂度为O(n*logn) 的排序就行了,快排、归并排序、堆排序,这里用快排,也可以直接使用C++ STL 的 sort 函数模板,代码:
#include <iostream>
#include <stdio.h>
using namespace std;
const int N = 50010;
int a[N];
void quickSort(int a[], int start, int end) {
int i = start, j = end, t = a[start];
if(start >= end) {
return ;
}
while(i < j) {
while(i < j && a[j] >= t) {
j--;
}
swap(a[j], a[i]);
while(i < j && a[i] <= t) {
i++;
}
swap(a[i], a[j]);
}
quickSort(a, start, i-1);
quickSort(a, i+1, end);
}
int main() {
int n;
cin >> n;
for(int i = 0; i < n; i++) {
scanf("%d", a+i);
}
quickSort(a, 0, n-1);
for(int i = 0; i < n; i++) {
printf("%d\n", a[i]);
}
return 0;
}