蓝桥杯 选择排序

选择排序的思想

选择排序的思想和冒泡排序类似，是每次找出最大的然后直接放到右边对应位置，然后将最
右边这个确定下来（而不是一个一个地交换过去）。
再来确定第二大的，再确定第三大的…
对于数组a[]，具体的来说，每次确定操作（假设当前要确定的是i位置）就是从左往右扫描，
计算出最大元素的下标max_id, 最后执行一次swap(a[max_id],a[i])将两项交换即可。
第一次确定操作是将a[1]~a[n]中最大的放到a[n]；
第二你确定操作是将a[1]～a[n-1]中最大的放到a[n-1]。
类推（类似地，如果你想先把最小的放到左边也是可以的），时间复杂度为O(n^2)。

选择排序的实现

#includeusing namespace std;const int N=1e3+9;int a[N];int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];//i表示当前要确定的位置 for(int i=n;i>=1;i--){int max_id=1;//初始化为1//j从左往右扫求出max_idfor(int j=1;j<=i;j++){if(a[j]>a[max_id])max_id=j;} swap(a[max_id],a[i]);}//输出for(int i=1;i<=n;i++) cout<<a[i]<<" \n"[i==n];return 0; }

例题讲解

#includeusing namespace std;const int N=1e3+9;int a[N];int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=n;i>=1;i--){int max_id=1;for(int j=1;j<=i;j++){if(a[j]>a[max_id])max_id=j;} swap(a[max_id],a[i]);}for(int i=1;i<=n;i++) cout<<a[i]<<" \n"[i==n];return 0; }