20北大软微华为实验班——排序题

学习目标：完成10017~10022 共6题（排序算法）中至少3道题。

1.基本排序题

输入： 5 3 1 8 6 1 输出： 1 1 3 6 8

思路一：冒泡排序（把最大的换到最后面）

#include <iostream> using namespace std; int a[500000]={0}; int main() { int n; cin>>n; //输入数据 for(int k=0;k<n;k++) cin>>a[k]; //冒泡排序 O(n^2) for(int i=0;i<n;i++) { for(int j=0;j<n-1-i;j++) { if(a[j]>a[j+1]) { int temp=a[j+1]; a[j+1]=a[j]; a[j]=temp; } } } //输出数据 for(int l=0;l<n;l++) cout<<a[l]<<" "; return 0; }

思路二：使用内置的快速排序库函数

#include <iostream> #include <algorithm> using namespace std; int a[500000]={0}; /** 定义排序规则 bool cmp(int x,int y) { reture x<=y; } **/ int main() { int n; cin>>n; //输入数据 for(int k=0;k<n;k++) cin>>a[k]; //排序库函数 #include <algorithm> sort(a,a+n);//默认升序排序 sort(a,a+n,cmp); //输出数据 for(int l=0;l<n;l++) cout<<a[l]<<" "; return 0; }

思路三：自己写快速排序函数

#include <iostream> using namespace std; int a[5000002]={0}; void quickSort(int *arr,int begin,int end) { if(begin>=end)//!!!!!这一句不可以删除 return; //第一个数为基准 int temp=arr[begin]; int i=begin,j=end; while(i<j) { while(i<j&&arr[j]>temp) j--; arr[i]=arr[j]; while(i<j&&arr[i]<=temp) i++; arr[j]=arr[i]; } //基准元素入位 arr[i]=temp; quickSort(arr,begin,i-1); quickSort(arr,i+1,end); return; } int main() { int n; cin>>n; //输入数据 for(int i=0;i<n;i++) cin>>a[i]; //排序 quickSort(a,0,n-1); //输出数据 for(int j=0;j<n;j++) cout<<a[j]<<" "; return 0; }

思路四：利用数组

#include <stdio.h> int a[5000005]={0}; int main() { int n,temp; scanf("%d",&n); //输入数据 for(int i=0;i<n;i++) { scanf("%d",&temp); //cin>>temp; a[temp]++; } //输出数据 for(int j=0;j<5000005;j++) { while(a[j]>0) { printf("%d ",j); //cout<<j<<" "; a[j]--; } } return 0; }

注：c++可能提示超时，改用c就行了（cin、cout比scanf、printf慢很多）。