算法导论：选择排序的原理与实现

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下：

首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。

下面附上动画演示：

选择排序的思想非常直接，不是要排序么？那好，我就从所有序列中先找到最小的，然后放到第一个位置。之后再看剩余元素中最小的，放到第二个位置……以此类推，就可以完成整个的排序工作了。可以很清楚的发现，选择排序是固定位置，找元素。相比于插入排序的固定元素找位置，是两种思维方式。不过条条大路通罗马，两者的目的是一样的。

下面是C语言实现：

#include 
#include 
void main()
{
    int i;
    int arr[10];
    int count;

    printf("排序前数组为：");
    srand((int)time(0));
	for(i=0; i < 10; i++)
	{
	    arr[i] = rand()%100;
	    printf("%d ",arr[i]);
	}

    count = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, count);

    printf("\n排序后数组为：");
    for(i=0; i < 10; i++)
	{
	    printf("%d ", arr[i]);
	}
}

void selectionSort(int data[], int count)
{
    int i, j, min, temp;
    for(i = 0; i < count; i ++) {
        /*find the minimum*/
        min = i;
        for(j = i + 1; j < count; j ++)
            if(data[j] < data[min])
                min = j;
        temp = data[i];
        data[i] = data[min];
        data[min] = temp;
    }
}

从选择排序的思想或者是上面的代码中，我们都不难看出，寻找最小的元素需要一个循环的过程，而排序又是需要一个循环的过程。因此显而易见，这个算法的时间复杂度也是O(n*n)的。这就意味值在n比较小的情况下，算法可以保证一定的速度，当n足够大时，算法的效率会降低。并且随着n的增大，算法的时间增长很快。因此使用时需要特别注意。