选择排序

/**
 * 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置(末尾位置)
 * 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末
 * 尾(首处)。以此类推，直到所有元素均排序完毕。选择排序的主要优点与数据移动
 * 有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换
 * 一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排
 * 序总共进行至多n-1次交换,选择排序最优和最差时间复杂度均为O(n ^ 2)
 */

#include <stdio.h>

void select_sort(int array[], int n)
{
    int i, j, index, tmp;

    for(i = 0; i < n - 1; ++i)
    {
        index = i;

        for(j = i + 1; j < n; ++j)
        {
            if(array[j] < array[index])
            {
                index = j;
            }
        }

        // 最好用一个swap函数代替
        if(index != i)
        {
            tmp = array[i];
            array[i] = array[index];
            array[index] = tmp;
        }
    }
}

main()
{
    int array[] = {-1, 5, -1, 0, 100, 30};
    select_sort(array, 6);
    for(int i = 0; i < 6; ++i)
        printf("%d ", array[i]);
}

运行结果: -1 -1 0 5 30 100