<>选择排序
<>题目
<>选择排序
<>
排序,顾名思义,是将若干个元素按其大小关系排出一个顺序。形式化描述如下:有n个元素a[1],a[2],…,a[n],从小到大排序就是将它们排成一个新顺序a[i[1]]<
a[i[2]]< …< a[i[n]]
<>i[k]为这个新顺序。
<>选择排序的思想极其简单,每一步都把一个最小元素放到前面,如果有多个相等的最小元素,选择排位较考前的放到当前头部。还是那个例子:{3 1 5 4 2}:
<>第一步将1放到开头(第一个位置),也就是交换3和1,即swap(a[0],a[1])得到{1 3 5 4 2}
<>第二步将2放到第二个位置,也就是交换3和2,即swap(a[1],a[4])得到{1 2 5 4 3}
<>第三步将3放到第三个位置,也就是交换5和3,即swap(a[2],a[4])得到{1 2 3 4 5}
<>第四步将4放到第四个位置,也就是交换4和4,即swap(a[3],a[3])得到{1 2 3 4 5}
<>第五步将5放到第五个位置,也就是交换5和5,即swap(a[4],a[4])得到{1 2 3 4 5}
<>输入n个整数,输出选择排序的全过程。
<>要求使用递归实现。
<>输入
<>第一行一个正整数n,表示元素个数
<>第二行为n个整数,以空格隔开,每组数据由两行组成,第一行是n和x,第二行是已经有序的n个数的数列。n和x同时为0标示输入数据的结束,本行不做处理。
<>输出
<>共n行,每行输出第n步选择时交换哪两个位置的下标,以及交换得到的序列,格式:
<>swap(a[i],a[j]):a[0] … a[n-1]
<>i和j为所交换元素的下标,下标从0开始,最初元素顺序按输入顺序。另外请保证i< =j
<>a[0]…a[n-1]为交换后的序列,元素间以一个空格隔开
<>样例输入
5 4 3 1 1 2
<>样例输出
swap(a[0], a[2]):1 3 4 1 2 swap(a[1], a[3]):1 1 4 3 2 swap(a[2], a[4]):1 1 2 3
4 swap(a[3], a[3]):1 1 2 3 4 swap(a[4], a[4]):1 1 2 3 4
<>解析
<>这是一道难度为三级的排序算法题,考察的是选择排序的算法,
<>
对于选择排序,我们要知道,是第一次从待排序的数据元素中选出最小或最大的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小或最大元素,然后放到已排序的序列的末尾,以此类推,知道全部待排序的数据元素的个数为零。
<>有如下排序函数部分代码
void select_sort(int a[], int n) { for (int i = 0; i < n; i++) { int k = i;
for (int j = i + 1; j < n; j++) { if (a[j] < a[k]) { k = j; } } swap(a[i],
a[k]); } }
<>代码流程
#include<bits/stdc++.h> using namespace std; //选择排序:从无序区找一个最小值和无序区第一个元素置换 void
select_sort(int a[], int n) { for (int i = 0; i < n; i++) { //a[0:i-1] is
sorted //find min_elem a[k] in a[i,n-1] //swap(a[i],a[k]) int k = i; for (int j
= i + 1; j < n; j++) { if (a[j] < a[k]) { k = j; } } swap(a[i], a[k]); cout <<
"swap(a[" << i << "], a[" << k << "]):"; for (int j = 0; j < n; j++) { cout <<
a[j] << " "; } cout << endl; } } int main() { int n; cin >> n; int a[n]; for
(int i = 0; i < n; i++)cin >> a[i]; select_sort(a, n); return 0; }
<>总结
<>1.选择排序是一种直观的排序算法,不稳定。
<>2.输出时记得多测试
<>3. 输出格式要正确