算法技术手册 – 排序 – 选择排序

选择排序,思想非常简单,分为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");
}

Leave a Reply

Your email address will not be published. Required fields are marked *