选择排序(Selection Sort)

选择排序是经典排序的一种,最差的时间复杂度为O(n^2),它的主要原理是直接从待排序数组里选择一个最小(或最大)的数字,每次都拿一个最小数字出来,顺序放入新数组,直到全部拿完。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
#define MAX 100
void Select(int a[], int n);
int main(void)
{
int ar[MAX], n;
int i;
freopen("input.txt", "r", stdin); /*重定向标准输入输出*/
freopen("output.txt", "w", stdout);
scanf("%d", &n); /*写入数据*/
for(i = 1; i <= n; i++)
scanf("%d", &ar[i]);
Select(ar, n); /*排序*/
for(i = 1; i <= n; i++) /*输出数据*/
{
printf("%d ", ar[i]);
if(i % 10 == 0)
putchar('\n');
}
return 0;
}

void Select(int a[], int n) /*待排序数组a[1...n]*/
{
int min, i, j, t;
for(i = 1; i <= n; i++)
{
min = i; /*从a[i...n]选出最小值*/
for(j = i + 1; j <= n; j++) { if(a[min] > a[j])
min = j;
}
if(min != i) /*交换*/
{
t = a[min]; a[min] = a[i]; a[i] = t;
}
}
}

测试数据:
输入:

1
2
3
4
5
6
50
13 95 29 62 69 34 74 38 29 78
29 67 98 22 27 13 92 26 94 98
28 62 2 27 23 92 87 96 11 93
25 94 6 15 35 63 61 88 80 5
39 47 36 35 26 83 39 77 25 61

输出:

1
2
3
4
5
2 5 6 11 13 13 15 22 23 25 
25 26 26 27 27 28 29 29 29 34
35 35 36 38 39 39 47 61 61 62
62 63 67 69 74 77 78 80 83 87
88 92 92 93 94 94 95 96 98 98

坚持原创技术分享,您的支持将鼓励我继续创作!