[数据结构与算法]【排序算法】计数排序

/**
 * 获取数组元素的最大值和最小值
 * @param array 待排序的数组
 * @param length 数组长度
 * @param min 最小值指针变量
 * @param max 最大值指针变量
 */
void min_max(const int array[], int length, int *min, int *max)
{
    *min = array[0];
    *max = array[0];
    for (int i = 1; i < length; i++) {
        if (*min > array[i]) {
            *min = array[i];
        }
        if (*max < array[i]) {
            *max = array[i];
        }
    }
}

// 调用这个方法,要尽量避免数组中既有正数,又有负数,这样会增加排序的耗时
void number_sort(int *array, int length, int min, int max)
{
    // 用一个数组来计算array中每个元素出现的次数
    int countArray_length = max - min + 1;
    int *p = (int *) malloc(sizeof(int) * countArray_length);
    for (int k = 0; k < countArray_length; k++) {
        p[k] = 0;
    }

    for (int i = 0; i < length; i++) {
        p[array[i] - min]++;
    }
    int index = 0;
    int value;
    int count;
    for (int i = 0; i < countArray_length; i++) {
        value = i + min;
        count = p[i];
        printf("the count of %d is: %d\n", value, count);
        for (int k = 0; k < count; k++) {
            array[index++] = value;
        }
    }
    free(p);
}

// 计数排序优化,数组中既有正数,又有负数,分两次排序.
// 比如这样一个数组{10000, -10000, 9999, -9999, 9998, -9998, 10000, -10000}
// 1.负数先排序得到一个array1
// 2.正数再排序得到一个array2
// 3.合并array1和array2到array中
void number_sort_another_way(int *array, int length)
{
    int negative_number = 0;
    for (int i = 0; i < length; i++) {
        // 算出有多少个负数
        if (array[i] < 0) {
            negative_number++;
        }
    }
    int *negative = (int *) malloc(sizeof(int) * negative_number);
    int *positive = (int *) malloc(sizeof(int) * (length - negative_number));
    int n = 0;
    int p = 0;
    int value;
    for (int i = 0; i < length; i++) {
        value = array[i];
        if (value < 0) {
            negative[n++] = value;
        } else {
            positive[p++] = value;
        }
    }
    int min;
    int max;
    min_max(negative, negative_number, &min, &max);
    number_sort(negative, negative_number, min, max);

    min_max(positive, length - negative_number, &min, &max);
    number_sort(positive, length - negative_number, min, max);
    // 合并两个数组
    for (int i = 0; i < negative_number; i++) {
        array[i] = negative[i];
    }
    for (int i = 0; i < length - negative_number; i++) {
        array[i + negative_number] = positive[i];
    }
    free(negative);
    free(positive);
}

/**
 * 计数排序(此算法适用于数组中最大值和最小值相差不太大的情况,如果相差超过1000,请考虑使用其他排序算法)
 * @param array 待排序的数组
 * @param length 数组长度
 */
extern void counting_sort(int *array, int length)
{
    int min;
    int max;
    min_max(array, length, &min, &max);
    if (min * max >= 0) { // 数组中的元素同±(正负)
        number_sort(array, length, min, max);
        return;
    }
    number_sort_another_way(array, length);
}