计数排序

个人主页：https://chengang.plus/

文章将会同步到个人微信公众号：Android部落格

1.1 描述

• 找出待排序的数组中最大和最小的元素；
• 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
• 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
• 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

1.2 代码

package com.chuck.algorithmproject.sort;

import android.util.Log;

import java.util.Arrays;

public class CountSort {
    private static String TAG = "CountSort";
    private static int[] number = {5, 8, 3, 6, 9, 10, 34, 3, 7, 6};

    public static void countSort() {
        int maxNumber = number[0];
        int minNumber = maxNumber;
        int size = number.length;
        for (int index = 0; index < size; index++) {
            if (number[index] > maxNumber) {
                maxNumber = number[index];
            }
            if (number[index] < minNumber) {
                minNumber = number[index];
            }
        }
        Log.e(TAG, "maxNumber:" + maxNumber + ",minNumber:" + minNumber);
        int tempArraySize = maxNumber - minNumber + 1;
        int[] tempArray = new int[tempArraySize];
        for (int index = 0; index < size; index++) {
            ++tempArray[number[index] - minNumber];
        }
        int originNumberIndex = 0;
        for (int index = 0; index < tempArraySize; index++) {
            while (tempArray[index] != 0) {
                number[originNumberIndex++] = index + minNumber;
                --tempArray[index];
            }
        }
        Log.e(TAG, "sorted number is " + Arrays.toString(number));
    }
}

1.3 总结

• 先找出给出数组的最大值,最小值;
• 创建最大值 - 最小值 + 1个大小的数组；
• 以index为序分别填入待排序数组中每个元素的个数，以此累加；
• 需要注意的是，存储元素个数的数组序号要减去最小值，反向填充数组的时候要加上最小值，避免数组溢出。

示意图如下：