对纯数字的高效排序算法

通过位操作或数组操作，一次扫描，一次赋值即可完成，对于数据量巨大，数据范围较小的应用具有最大的运行效率。

在实际应用场合，最大值和最小值可以直接填写而不通过函数获取。

 

/**
 * @file sort.c
 * @brief 对所有元素都为正整数的数组进行排序
 * @defgroup sort
 * @{
 */
#include <stdio.h>

/** @brief 位设置 */
static void bit_set(char *tmp, int pos)
{
    if (NULL == tmp || pos < 0)
        return;
    int n = pos / 8;
    int mov = pos % 8;
    tmp += n;
    *tmp |= 1 << mov;
}
/** @brief 位比较 */
static int bit_cmp(char *tmp, int pos)
{
    if (NULL == tmp || pos < 0)
        return;
    int n = pos / 8;
    int mov = pos % 8;
    tmp += n;
    return (*tmp & 1 << mov);
}

/**
 * @brief 对所有元素都不同的数组进行排序，要求数组所有元素为正整数。
 * @param  arr  等待排序的数组
 * @param  len  数组长度
 * @param[in]  min  数组中最小可能出现的最小值
 * @param[in]  max  数组种最大可能出现的最大值
 * @return 无
 */
void sort_diff_num(int *arr, int len, int min, int max)
{
    if (NULL == arr || min < 0)
        return;
    int i, j;
    int range = max - min + 1;
    char tmp[range / 8 + 1];
    memset(tmp, 0, sizeof tmp);
    for (i=0; i<len; i++) {
        bit_set(tmp, arr[i]-min);
    }
    for (i=0,j=0; i<range; i++) {
        if (bit_cmp(tmp, i)) {
            arr[j] = i+ min;
            printf("arr[%d] = %d\n", j, i+min);
            j++;
        }
    }
}

/**
 * @brief 对可能出现重复值的数组进行排序，要求数组所有元素为正整数。
 * @param  arr  等待排序的数组
 * @param  len  数组长度
 * @param[in]  min  数组中最小可能出现的最小值
 * @param[in]  max  数组种最大可能出现的最大值
 * @return 无
 */
int sort_repe_num(int *arr, int len, int min, int max)
{
    if (NULL == arr || min < 0)
        return;
    int i, j, k;
    int range = max - min + 1;
    int tmp[range];
    memset(tmp, 0, sizeof tmp);
    for (i=0; i<len; i++) {
        tmp[arr[i]]++;
    }
    for (i=0,j=0; i<range; i++) {
        for (k=0; k<tmp[i]; k++) {
            arr[j] = i+ min;
            printf("arr[%d] = %d\n", j, i+min);
            j++;
        }
    }
}

int get_max_num(int arr[], int len)
{
    int i, max = 0;
    for (i=0; i<len; i++)
        max = max > arr[i] ? max : arr[i];
    return max;
}

int get_min_num(int arr[], int len)
{
    int i, min = 0;
    for (i=0; i<len; i++)
        min = min < arr[i] ? min : arr[i];
    return min;
}

/** @} */

#if 1
int main(int argc, char **argv)
{
    int array_num[] = {1, 4, 12, 4, 3};
    int array_len = sizeof array_num / sizeof (int);
    int i;
    for (i=0; i<array_len; i++) 
        printf("%d ", array_num[i]);
    printf("\n");
    sort_repe_num(array_num, array_len, 
                get_min_num(array_num, array_len),
                   get_max_num(array_num, array_len));
    for (i=0; i<array_len; i++) 
        printf("%d ", array_num[i]);
    printf("\n");
}
#endif