排序算法(2)

本文是”排序算法“第2篇文章，主要介绍线性时间复杂度的三种非比较排序算法：计数排序、桶排序和基数排序。这三种排序给我们另一种思考问题的角度。

计数排序

计数排序的算法思想不同寻常：根据待排序数组的元素数值范围构造一个临时数组，将元素数值对应到临时数组的索引，最后按序输出即可。

void CountSort(int data[], int n) {
	if (n <= 1) return;

	// 求最大值、最小值
	int min = data[0];
	int max = data[0];
	for (int i = 1; i < n; i++) {
		if (data[i] < min)
			min = data[i];
		if (data[i] > max)
			max = data[i];
	}

	// 创建数组用于计数
	int count = max - min + 1;
	int *tempArray = (int*)malloc(sizeof(int) * count);
	for (int i = 0; i < count; i++)
		tempArray[i] = 0;
	for (int i = 0; i < n; i++)
		tempArray[data[i] - min]++;

	// 输出有序数组
	int k = 0;
	for (int i = 0; i < count; i++) {
		for (int j = 0; j < tempArray[i]; j++) {
			data[k++] = i + min;
		}
	}
    // 释放临时数组
	free(tempArray);
}

桶排序

桶排序是计数排序的升级版，其基本思想是：将N个元素按照某种映射关系分到M个桶中，将每个桶中的元素进行排序后合并就可以得到N个元素的排序。

// 定义桶数量
#define BUCKETNUM 20

void BucketSort(int data[], int n) {
    int* bucket[BUCKETNUM];
    for (int i = 0; i < BUCKETNUM; i++) {
        bucket[i] = (int*)malloc(sizeof(int) * n);
        bucket[i][0] = 0;
    }
	
    // 将数组元素散列到桶中
    for (int i = 0; i < n; i++) {
        int index = data[i] / BUCKETNUM;
        bucket[index][0]++;
        bucket[index][bucket[index][0]] = data[i];
    }

    // 对每个桶中的元素进行排序，可以采用快排
    for (int i = 0; i < BUCKETNUM; i++) 
        QSort(bucket[i], 1, bucket[i][0]);

    // 合并每个桶的元素
    int totalIndex = 0;
    for (int i = 0; i < BUCKETNUM; i++)
        for (int j = 1; j <= bucket[i][0]; j++)
            data[totalIndex++] = bucket[i][j];

    for (int i = 0; i < BUCKETNUM; i++)
        free(bucket[i]);
}

基数排序

基数排序就是按照数位从低到高的顺序，对每一位执行技术排序，完成最高位排序后，整个数组的元素就有序了。

思想很清晰，不做代码介绍。

总结

计数排序、桶排序和基数排序是非比较排序，而是将其数组与某种索引挂钩，是一种完全不同的排序思维。