选择排序

选择排序是一种很容易理解和实现的简单排序算法。

首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。因为它在不断地选择剩余元素之中的最小者，所以这种方法叫选择排序。

它有两个很鲜明的特点：
　　运行时间与输入无关。为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息。这种性质在某些情况下是缺点，因为使用选择排序的人可能会惊讶的发现，一个已经有序的数组或是主键全部相等的数组和一个元素随机排列的数组所用的排序时间竟然一样长！我们将会看到，其它算法会更善于利用输入的初始状态。
　　数据移动是最少的。每次交换都会改变两个数组元素的值，因此选择排序用了Ｎ次交换——交换次数和数组大小是线性关系。其它的任何算法都不具备这个特征（大部分的增长数量级都是线性对数或平方级别）

简单的实现

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int *A;
    int length, i, j, t, min, key;

    //输入要排序的数字个数
    scanf("%d", &length);
    A = (int*)malloc(length * sizeof(int));
    //输入数字
    for (i = 0; i < length; i++)
        scanf("%d", &A[i]);
    //排序
    for (i = 0; i < length - 1; i++)
    {
        min = A[i];
        key = i;
        for (j = i + 1; j < length; j++)
        {
            if (A[j] < min)
            {
                min = A[j];
                key = j;
            }
        }
        t = A[i];
        A[i] = min;
        A[key] = t;
    }
    for (i = 0; i < length; i++)
        printf("%d ", A[i]);
    free(A);//别忘了释放malloc来的空间
    return 0;
}