选择排序算法，C语言选择排序算法详解

选择排序是一种简单直观的排序算法。它与冒泡排序很相似，都是比较 n-1 轮，每轮都是比较 n–1–i 次，每轮找出一个最大值或最小值。

只不过，冒泡排序是将每轮找出的最值放到最右边，而选择排序是将每轮找出的最值放到最左边。并且在算法上，冒泡排序是将相邻的数进行逐个比较，以从小到大排序为例，只要前面的比后面的大，就互换这两个数，直到最后将最大的数“浮”到最右边，如此依次循环。而选择排序是先保存第一个元素的下标，然后后面所有的数依次与第一个元素相比，如果遇到更小的，则记录更小的那个数的下标，然后后面所有的数都依次与那个更小的数比较，直到最后将最小的数的下标找出来，然后再将这个数放到最左边，即与下标为 0 的数互换。如果最小的数的下标就是 0 那么就不用互换。

所以，选择排序算法是先判断最小的数的下标是不是 0，如果不是则说明最小的数不是第一个元素，则将这个数与第一个元素互换位置，这样一轮下来最小的那个数就被找到并放到了最左边。

在第二轮同样先保存新序列第二个元素的下标，后面所有的数依次与第二个元素相比较，如果遇到更小的则记录更小的那个数的下标，然后后面所有的数都依次与那个更小的数比较，直到最后又找到一个最小的，此时这个最小的在整个序列中是“第二小”。然后再判断这个数的下标是否等于 1，如果不等于 1 说明“第二小”的那个数不是第二个元素，则将这个数与第二个元素互换位置，这样第二轮下来就找到了“第二小”的那个数，并将它放到了第二个位置。如此循环，直到整个序列实现从小到大排序。

如果是从大到小排序，那么就记录大的那个数的下标，每一轮找出一个最大的数放到左边。

从上面的分析可以看出，选择排序和冒泡排序的另一个不同点是，冒泡排序只要遇到前面比后面大的就互换，而选择排序是比较一轮才互换一次，而且如果本轮中最小的就是最左边那个数则不用互换。所以从这个角度看，选择排序比冒泡排序的效率要高。而且通过上面对选择排序的分析发现，从逻辑上讲，与冒泡排序相比，选择排序更符合人的思维。

下面来写一个程序，用选择排序实现一个序列的从小到大排序：

# include <stdio.h>
int main(void)
{
    int i, j;  //循环变量
    int MinIndex;  //保存最小的值的下标
    int buf;  //互换数据时的临时变量
    int a[] = {5, 5, 3, 7, 4, 2, 5, 4, 9, 1, 8, 6};
    int n = sizeof(a) / sizeof(a[0]);  //存放数组a中元素的个数
    for (i=0; i<n-1; ++i)  //n个数比较n-1轮
    {
        MinIndex = i;
        for (j=i+1; j<n; ++j)  //每轮比较n-1-i次, 找本轮最小数的下标
        {
            if (a[MinIndex] > a[j])
            {
                MinIndex = j;  //保存小的数的下标
            }
        }
        if (MinIndex != i)  /*找到最小数之后如果它的下标不是i则说明它不在最左边, 则互换位置*/
        {
            buf = a[MinIndex];
            a[MinIndex] = a[i];
            a[i] = buf;
        }
    }
    printf("最终排序结果为:\n");
    for (i=0; i<12; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

输出结果是：
         最终排序结果为:1 2 3 4 4 5 5 5 6 7 8 9

通过程序可以看出，虽然选择排序比冒泡排序的效率高，逻辑上也更符合人的思维，但是程序相对更复杂，冒泡排序比选择排序在逻辑上要清晰一点，也稍微简单一点。