计数排序 counting sort

计数排序

1. 时间复杂度(平均、最坏、最好) O(n+k)
2. 空间复杂度为O(n+k)
3. 稳定性：稳定
4. n为数组元素个数，k为数据最大值

算法解析：

• 计数排序不是比较数值排序，是记录数据出现次数的一种排序算法
• 找出待排数组中最大值
• 额外一个数组记录待排数组值出现的次数
• 循环打印存储数值次数的数组下标值

动画演示：

countingSort

C实现

int * countingSort1(int arr[],int count,int max) {
    int index = 0;
    int *tmpArr = (int *)malloc(max*sizeof(int));
    int *result = (int *)malloc(max*sizeof(int));
    
    for(int k = 0;k<max;k++) {
        tmpArr[k] = 0;
    }
    
    for (int i = 0; i<count; i++) {
        tmpArr[arr[i]]++;
    }
    for (int j = 0; j<max; j++) {
        while (tmpArr[j]) {
            result[index++] = j;
            tmpArr[j]--;
        }
    }
    free(tmpArr);
    tmpArr = NULL;
    return result;
}

oc实现

- (NSArray *)countingSort:(NSArray *)arr max:(int)maxNum {//[@1,@20,@5]
    NSMutableArray *mutableArr = @[].mutableCopy;
    NSMutableArray *result = @[].mutableCopy;
    //初始化
    for (int i = 0; i<=maxNum; i++) { //K
        mutableArr[i] = @0;
    }
    //下标数值++
    for (int j = 0; j<arr.count; j++) { // N
        int t = [arr[j] intValue];
        mutableArr[t] = [NSNumber numberWithInt:[mutableArr[t] intValue]+1];
    }
    
    for (int i = 0; i<mutableArr.count; i++) {
        NSNumber *tmp = mutableArr[i];
        int t = tmp.intValue;
        while (t) {
            [result addObject:@(i)];
            t--;
        }
    }
    return result.copy;
}

Swift 实现

func countingSort(arr : Array<Int>,count:Int,max:Int) -> Array<Int> {
    var tmp = 0
    var tmpArr = Array.init(repeating: 0, count: max)
    var result = Array.init(repeating: 0, count: count)
    for i in 0..<arr.count {
        tmpArr[arr[i]] += 1
    }
    for j in 0..<tmpArr.count {
        while tmpArr[j] > 0 {
            result[tmp] = j
            tmpArr[j] -= 1
            tmp+=1
        }
    }
    return result
}

以下代码来源于网络，未验证

js 实现

function countingSort(arr, maxValue) {
    var bucket = new Array(maxValue+1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1;

    for (var i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }

    for (var j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }

    return arr;
}

Python 代码实现

def countingSort(arr, maxValue):
    bucketLen = maxValue+1
    bucket = [0]*bucketLen
    sortedIndex =0
    arrLen = len(arr)
    for i in range(arrLen):
        if not bucket[arr[i]]:
            bucket[arr[i]]=0
        bucket[arr[i]]+=1
    for j in range(bucketLen):
        while bucket[j]>0:
            arr[sortedIndex] = j
            sortedIndex+=1
            bucket[j]-=1
    return arr

Go 代码实现

func countingSort(arr []int, maxValue int) []int {
    bucketLen := maxValue + 1
    bucket := make([]int, bucketLen) // 初始为0的数组

    sortedIndex := 0
    length := len(arr)

    for i := 0; i < length; i++ {
        bucket[arr[i]] += 1
    }

    for j := 0; j < bucketLen; j++ {
        for bucket[j] > 0 {
            arr[sortedIndex] = j
            sortedIndex += 1
            bucket[j] -= 1
        }
    }
    return arr
}

Java 代码实现

public class CountingSort implements IArraySort {
    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxValue = getMaxValue(arr);

        return countingSort(arr, maxValue);
    }

    private int[] countingSort(int[] arr, int maxValue) {
        int bucketLen = maxValue + 1;
        int[] bucket = new int[bucketLen];

        for (int value : arr) {
            bucket[value]++;
        }

        int sortedIndex = 0;
        for (int j = 0; j < bucketLen; j++) {
            while (bucket[j] > 0) {
                arr[sortedIndex++] = j;
                bucket[j]--;
            }
        }
        return arr;
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }
}