学习目标：完成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;
}