排序算法5 - 选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

算法描述

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

3. 以此类推，直到全部待排序的数据元素的个数为零。

演示图：

代码：

#include <stdio.h>

void SelectSort(int k[], int n)
{
	int i, j, min;

	for(i=0; i<n-1; i++)
	{
		min = i; // 假设最小值的所在序号是i
		// 找出最小值所在序号
		for(j=i+1; j<n; j++)
		{
			if( k[j]<k[min] )
			{
				min = j;
			}
		}

		// 数据交换(异或实现)
		if( min!=i )
		{
			k[i]^=k[min];
			k[min]^=k[i];
			k[i]^=k[min];
		}
	}
}


int main(void)
{

	int i;
	int a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};

	SelectSort(a, 10);

	printf("排序后的结果是：");
	for(i=0; i<10; i++)
	{
		printf("%d", a[i]);
		if(i!=9)
		{
			printf(",");
		}
	}
	printf("\n");
	return 0;
}