1. 基本概念

简单选择排序（Select Sort）真的是人如其名，一是它真的非常简单，二是它主要依靠选择和交换操作来进行排序。可以将简单选择排序实现为稳定的排序算法，也可以实现为不稳定的排序算法。

我们先来直观地感受一下它的主要思想，假设有一个装满了球的桶，每个球上都标有一个数字，现在我们需要对桶中的所有球按从小到大的顺序进行排序。

首先我们从桶中选择数字最小的那个球，将它取出并放在桌子上；然后再从桶中选择数字最小的那个球，并将它取出放在第一个球的后面；然后又从桶中选择数字最小的那个球，并把它放到第二个球的后面。以此类推，每次都从桶中选择数字最小的那个球，并把它取出后放到之前所有已选出的那些球的后面；那么当最后一个球被取出并放置后，所有这些球就排好序了。

我们可以发现，第一次取出的球它在最终的有序序列中的位置是第一个，第二次取出的球在最终的有序序列中的位置是第二个。同理，第i次取出的球它在最终的有序序列中的位置是第i个。

这个例子主要体现了选择的思想，但是简单选择排序还涉及另一个思想，那就是交换。在上面这个例子中，排序之前球在桶中，排序后球在桌子上，即排序前后放置的地方不同。简单选择排序是对一个序列（数组）中的元素进行排序，排序后这些元素还是在这个原始序列中，只是它们的相对位置发生了改变。我们当然可以使用一个和原序列相同大小的临时序列，每当从原序列中选出一个元素就将它放置到临时序列中，最后再将整个有序的临时序列复制回原序列。

这样的方式需要大量额外的临时存储空间，但实际上不需要临时序列也能实现简单选择排序，这就是通过交换来完成的。我们先提醒一下，在大多数编程语言中序列（数组）的第1个元素的下标为0，最后一个元素的下标为n-1（假设序列一共有n个元素）。

总的来说简单选择排序由多趟组成，第 i 趟（i的取值范围是[1, n-1]）排序就是从 n-i+1 个未排序的元素中选择最小的那个元素，并将它和序列中的第 i 个元素（它的下标为i-1）交换位置。在 n-i+1 个元素中找出最小的那个是通过元素之间的两两比较完成的，一共需要 n-i 次比较。

我们首先从整个序列（下标为0 ~ n-1）中选择最小的那个元素，如果它不是第1个元素（下标为0），那么就将它和第1个元素交换位置；这样这个最小的元素就处于它最终的位置上了，而原来的第1个元素现在位于这个最小元素之前的位置上。然后再从第2 ~ n个元素（下标为1 ~ n-1）中选择最小的元素，并将它和第2个元素交换位置，这样这个第二小的元素就在它最终的位置上了。然后又从第3 ~ n个元素（下标为2 ~ n-1）中选择最小的那个元素，并将它和第3个元素交换位置，这样这个第三小的元素也在它的最终位置上了。重复这一过程，直到整个序列排好序。

在简单选择排序的过程中，我们可以将整个序列看成是前后两部分，前面部分中的元素是已经排好序了的，后面部分中的元素是还没有排好序的。每趟排序都从后面部分选出最小的元素，将它和后面部分的第1个元素交换位置，这样该元素就和之前的前面部分形成新的前面部分，它之中的所有元素都是排好序了的，而原先的后面部分中从它的第2个元素开始的所有剩余元素形成新的后面部分。图1通过一个例子展示了简单选择排序的完整过程。

一个具有n个元素的序列进行简单选择排序的时候，需要执行n-1趟而不是n趟。这是因为在第n-1趟开始时，序列中的前n-2个元素都是已排好序了的，只有最后的两个元素还没有排好序。第n-1趟就是从这两个元素中选择较小的那个元素，并将它交换到序列中倒数第二个位置上，同时最后那一个元素也被交换到了最后的位置上。此时，整个序列就排好序了，因此也就不再需要第n趟操作了。

2. 代码实现

本文中我们使用C语言来实现简单选择排序，代码非常简单直接，即便不熟悉C语言也能明白；并且在代码中我们也给出了非常详细的注释。

/*
 * Function: selectSort
 * Description: 简单选择排序的实现
 * param: array 待排序的序列（数组）
 * param: n 序列中的元素数量
 */
void selectSort(int array[], int n) {
    /*
     * i、j作为循环控制变量，temp用于交换元素，
     * minIndex用于记录每一趟中最小元素的下标。
     */
    int i;
    int j;
    int temp;
    int minIndex;

    /*
     * 外层循环，用于控制第1至第(n-1)趟排序；
     * 第i趟时，后面部分的元素的下标范围是(i-1) ~ (n-1)。
     */
    for(i = 1; i < n; i++) {
        // 将后面部分的第1个元素的下标赋予minIndex
        minIndex = i - 1;

        /*
         * 从后面部分的第二个元素开始，通过和当前最小元素
         * 进行比较而选出实际最小的那个元素，将它的下标
         * 记录在minIndex中。
         */
        for(j = i; j < n; j++) {
            if(array[j] < array[minIndex]) {
                minIndex = j;
            }
        }

        /* 
         * 如果本趟中最小的元素不是后面部分的第1个元素（下标是i-1），
         * 则需要交换元素
         */
        if(minIndex != i - 1) {
            temp = array[i - 1];
            array[i - 1] = array[minIndex];
            array[minIndex] = temp;
        }
    }
}

3. 复杂度分析

根据我们前面的讲述可知，一个具有n个元素的序列需要进行n-1趟排序，第i趟需要进行n-i次比较，因此一共需要 (n - 1) + (n - 2) + ··· + 1 = n(n - 1)/2次比较。而每一趟要么交换元素、要么不交换元素，因此最好情况下（原序列中的元素在排序前就已经是有序的了）共需0次交换，最坏情况下共需n-1次交换。因此时间复杂度为O(n^2)，即n的平方。

根据我们的实现，简单选择排序只需要几个固定的额外空间用于存储变量i、j、temp和minIndex，它和原序列的长度无关。因此，简单选择排序的空间复杂度为O(1)。

（完）