选择排序（英语：Selection Sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

选择排序是不稳定的。选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。

一、 选择排序源码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NUM 10

// 选择排序函数实现
void selection_sort(int a[], int n)
{
	for(int i=0; i<n-1; i++)
	{
		int min = i;
		
		for(int j=i+1; j<n; j++)
		{
			if(a[j] < a[min]) min = j;
		}
		
		if(min != i)
		{
			int tmp = a[i];
			a[i] = a[min];
			a[min] = tmp;
		}
	}
}

int main(void)
{
	int array[NUM];
	
	srand((unsigned int)time(NULL));
	
	// 给数组赋随机值
	for(int i=0; i<NUM; i++)
	{
		array[i] = rand()%100;
	}
	
	// 打印排序前数组
	for(int i=0; i<NUM; i++)
	{
		printf("%5d", array[i]);
	}
	
	printf("\n");
	
	// 选择排序
	selection_sort(array, NUM);
	
	// 打印排序后数组
	for(int i=0; i<NUM; i++)
	{
		printf("%5d", array[i]);
	}
	
	printf("\n");
	
	return 0;
}

二、 运行结果

[root@localhost workspace]# gcc selection_sort.c -o selection_sort -Wall
[root@localhost workspace]# ./selection_sort
   83   86   77   15   93   35   86   92   49   21
   15   21   35   49   77   83   86   86   92   93
[root@localhost workspace]# ./selection_sort
   75    0   59   99   67   18   53   17   55   73
    0   17   18   53   55   59   67   73   75   99
[root@localhost workspace]# ./selection_sort
   66   21   99   40   55    1   77   55    4    2
    1    2    4   21   40   55   55   66   77   99
[root@localhost workspace]# ./selection_sort
   17   42   99   39    9   12   78   64   49   71
    9   12   17   39   42   49   64   71   78   99
[root@localhost workspace]# ./selection_sort
    5    2    0   64   51   78   80   53   90   78
    0    2    5   51   53   64   78   78   80   90
[root@localhost workspace]# ./selection_sort
   96   21   88   86    1   38   77   23   58    0
    0    1   21   23   38   58   77   86   88   96
[root@localhost workspace]# ./selection_sort
   96   54    4   19   46   19   22   17    1    7
    1    4    7   17   19   19   22   46   54   96
[root@localhost workspace]# ./selection_sort
   65   33   11   11   28   69   77   25    8   80
    8   11   11   25   28   33   65   69   77   80
[root@localhost workspace]# ./selection_sort
   17   26   47   85   87   42   54   88   18   56
   17   18   26   42   47   54   56   85   87   88