选择排序，思想非常简单，分为selectMax和selectSort两个部分。

selectMax：
每次选择区间内最大的数，返回其Index
selectSort
1、从右到左依次扫描i（除idx=0，因为选到最后，最小的一定在最左边），规定区间为[0, i]
2、调用selectMax，获得最大的maxIndex。
3、这个i位置应该是第i大的数的位置，也就是maxIndex的数的位置，因此，如果i!=maxIndex，swap之。

算法复杂度，不管是最坏、平均还是最好，都是O(N^2)。

#include <stdio.h>

typedef long TYPE;

int cmp(TYPE a, TYPE b)
{
    return a - b;
}

void swap(TYPE* a, TYPE* b)
{
    TYPE tmp = *a;
    *a = *b;
    *b = tmp;
}

int selectMax(TYPE* arr, int left, int right, int (*cmp)(TYPE a, TYPE b))
{
    int maxIndex = left;
    int i = left + 1;
    while(i<=right)
    {
        if(cmp(arr[i], arr[maxIndex])>0)
        {
            maxIndex = i;
        }
        i++;
    }
    return maxIndex;
}

void selectSort(TYPE* arr, int n, int (*cmp)(TYPE a, TYPE b))
{
    int i;
    int maxIndex;
    for(i=n-1 ; i>0; i--)
    {
        maxIndex = selectMax(arr, 0, i, cmp);
        if(maxIndex!=i)
        {
            swap(&arr[maxIndex], &arr[i]);
        }
    }
}

int main()
{
    TYPE arr[] = {5,4,3,2,1,-2};
    int len = sizeof(arr) / sizeof(TYPE);
    int i;

    //Test select max
    //printf("Max INdex\t%d\n",selectMax(arr, 1, len-1, cmp));

    //Select Sort
    selectSort(arr, len, cmp);

    //Print
    for(i=0; i<len; i++)
    {
        printf("%ld ", arr[i]);
    }
    printf("\n");
}