选择排序

缘起

邓俊辉数据结构和算法（C++语言版）第二章的例子.

这里要说一句, 其实数组（向量）和链表的排序的思想是一致的,只是因为存储结构不一样而略有不同. 这里以数组为例

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
#include "stdafx.h"
#include <iostream>
#include <algorithm>

#define LOCAL
#define N 8

using namespace std;

// a是数组, n是数组元素的个数
void sort(int *a, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int _min =  i;
		for (int j = i; j< n; j++) if (a[j]<a[_min]) _min = j;
		if (_min!=i) swap(a[i], a[_min]); // 如果真的变动了 才交换
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif

	int a[8];
	for (int i = 0; i < N; i++) scanf("%d", &a[i]);
	sort(a, N);
	for (int i = 0; i < N; i++) cout<< a[i]<< endl;
	return 0;
}

选择排序是不稳定的（设想一下, 2,2,1; 则第一次选择排序的时候, 第一个2就跑最后去了, 所以不稳定）, O(n^2)的复杂度, 就地算法