排序算法——选择排序

原理

每次从数组中选取最小的数字放在第一个位置，直到数组最后一个位置也被放上合适的数字。

分析

由于每次选择最小的数字过程中，每个数字都会被遍历一次，总共会选择n（n为数组长度）次，所以其最好和最坏情况下的时间复杂度都是O（n2）；由于其选择交换操作都是在原数组上进行，所以空间复杂度为O（1）。

C语言实现

void swap(void *a, void *b, int size)
{
    void *tmp = Malloc(size);
    memcpy(tmp, a, size);
    memcpy(a, b, size);
    memcpy(b, tmp, size);
    free(tmp);
}
Boolean select(int *arr, int arrlen)
{
    int i = 0, j = 0;
    int minindex = 0;

    if(NULL == arr || 0 >= arrlen){
        printf("Invalid input...\n");
        return FALSE;
    }
    for(i = 0; i < arrlen ; ++i){
        minindex = i;
        for(j = i; j < arrlen; ++j){
            if(arr[j] < arr[minindex]){
                minindex = j;
            }
        }
        swap(arr+minindex, arr+i, sizeof(arr[i]));
    }
}

本文出自 “11219885” 博客，请务必保留此出处http://11229885.blog.51cto.com/11219885/1751520

排序算法——选择排序

原文：http://11229885.blog.51cto.com/11219885/1751520