算法(5)- 计数排序(键索引计数法)

01 计数排序算法概念

计数排序不是一个比拟排序算法，该算法于 1954 年由 Harold H. Seward 提出，通过计数将工夫复杂度降到了O(N)。

02 根底版算法步骤

第一步：找出原数组中元素值最大的，记为max。

第二步 ：创立一个新数组count，其长度是max 加 1，其元素默认值都为 0。

第三步 ：遍历原数组中的元素，以原数组中的元素作为count 数组的索引，以原数组中的元素呈现次数作为 count 数组的元素值。

第四步：创立后果数组result，起始索引index。

第五步 ：遍历count 数组，找出其中元素值大于 0 的元素，将其对应的索引作为元素值填充到 result 数组中去，每解决一次，count中的该元素值减 1，直到该元素值不大于 0，顺次解决 count 中剩下的元素。

第六步：返回后果数组result。

03 根底版代码实现

public int[] countSort(int[] A) {
    // 找出数组 A 中的最大值
    int max = Integer.MIN_VALUE;
    for (int num : A) {max = Math.max(max, num);
    }
    // 初始化计数数组 count
    int[] count = new int[max+1];
    // 对计数数组各元素赋值
    for (int num : A) {count[num]++;
    }
    // 创立后果数组
    int[] result = new int[A.length];
    // 创立后果数组的起始索引
    int index = 0;
    // 遍历计数数组，将计数数组的索引填充到后果数组中
    for (int i=0; i<count.length; i++) {while (count[i]>0) {result[index++] = i;
            count[i]--;
        }
    }
    // 返回后果数组
    return result;
}

04 优化版

根底版可能解决个别的状况，然而它有一个缺点，那就是存在空间节约的问题。

比方一组数据 {101,109,108,102,110,107,103}，其中最大值为 110，依照根底版的思路，咱们须要创立一个长度为 111 的计数数组，然而咱们能够发现，它后面的[0,100] 的空间齐全节约了，那怎么优化呢？

将数组长度定为 max-min+1，即不仅要找出最大值，还要找出最小值， 依据两者的差来确定计数数组的长度。

public int[] countSort2(int[] A) {
    // 找出数组 A 中的最大值、最小值
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for (int num : A) {max = Math.max(max, num);
        min = Math.min(min, num);
    }
    // 初始化计数数组 count
    // 长度为最大值减最小值加 1
    int[] count = new int[max-min+1];
    // 对计数数组各元素赋值
    for (int num : A) {
        // A 中的元素要减去最小值，再作为新索引
        count[num-min]++;
    }
    // 创立后果数组
    int[] result = new int[A.length];
    // 创立后果数组的起始索引
    int index = 0;
    // 遍历计数数组，将计数数组的索引填充到后果数组中
    for (int i=0; i<count.length; i++) {while (count[i]>0) {
            // 再将减去的最小值补上
            result[index++] = i+min;
            count[i]--;
        }
    }
    // 返回后果数组
    return result;
}

05 进阶版步骤

以数组 A = {101,109,107,103,108,102,103,110,107,103} 为例。

第一步：找出数组中的最大值max、最小值min。

第二步：创立一个新数组count，其长度是max-min 加 1 ，其元素默认值都为 0。

第三步 ：遍历原数组中的元素，以原数组中的元素作为count 数组的索引，以原数组中的元素呈现次数作为 count 数组的元素值。

第四步 ：对count 数组 变形 ， 新元素的值是后面元素累加之和的值 ，即count[i+1] = count[i+1] + count[i];。

第五步：创立后果数组result，长度和原始数组一样。

第六步 ：遍历原始数组中的元素，以后元素 A[j] 减去最小值 min，作为索引，在计数数组中找到对应的元素值count[A[j]-min]，再将 count[A[j]-min] 的值减去 1，就是 A[j] 在后果数组 result 中的地位，做完上述这些操作，count[A[j]-min]自减 1。

是不是对第四步和第六步有疑难？为什么要这样操作？

第四步操作，是让计数数组 count 存储的元素值，等于原始数组中相应整数的最终排序地位，即 计算原始数组中的每个数字在后果数组中处于的地位。

比方索引值为 9 的 count[9]，它的元素值为 10，而索引 9 对应的原始数组A 中的元素为 9 +101=110（要补上最小值 min，能力还原），即 110 在排序后的地位是第 10 位，即 result[9] = 110，排完后count[9] 的值须要减 1，count[9]变为 9。

再比方索引值为 6 的 count[6]，他的元素值为 7，而索引 6 对应的原始数组A 中的元素为 6 +101=107，即 107 在排序后的地位是第 7 位，即 result[6] = 107，排完后count[6] 的值须要减 1，count[6]变为 6。

如果索引值持续为 6，在通过上一次的排序后，count[6]的值变成了 6，即 107 在排序后的地位是第 6 位，即 result[5] = 107，排完后count[6] 的值须要减 1，count[6]变为 5。

至于第六步操作，就是为了找到 A 中的以后元素在后果数组 result 中排第几位，也就达到了排序的目标。

06 进阶版代码实现

public int[] countSort3(int[] A) {
    // 找出数组 A 中的最大值、最小值
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for (int num : A) {max = Math.max(max, num);
        min = Math.min(min, num);
    }
    // 初始化计数数组 count
    // 长度为最大值减最小值加 1
    int[] count = new int[max-min+1];
    // 对计数数组各元素赋值
    for (int num : A) {
        // A 中的元素要减去最小值，再作为新索引
        count[num-min]++;
    }
    // 计数数组变形，新元素的值是后面元素累加之和的值
    for (int i=1; i<count.length; i++) {count[i] += count[i-1];
    }
    // 创立后果数组
    int[] result = new int[A.length];
    // 遍历 A 中的元素，填充到后果数组中去
    for (int j=0; j<A.length; j++) {result[count[A[j]-min]-1] = A[j];
        count[A[j]-min]--;
    }
    return result;
}

07 进阶版的延长之一

如果咱们想要原始数组中的雷同元素依照原本的程序的排列，那该怎么解决呢？

仍旧以上一个数组 {101,109,107,103,108,102,103,110,107,103} 为例，其中有两个 107，咱们要实现第二个 107 在排序后仍旧排在第一个 107 的前面，能够在第六步的时候，做下变动就能够实现，用倒序的形式遍历原始数组，即 从后往前 遍历 A 数组。

从后往前遍历，第一次遇到 107（A[8]）时，107-101 = 6，count[6] = 7，即第二个 107 要排在第 7 位，即result[6] = 107，排序后count[6] = 6。

持续往前，第二次遇到 107（A[2]）时，107-101 = 6，count[6] = 6，即第一个 107 要排在第 6 位，即result[5] = 107，排序后count[6] = 5。

public int[] countSort4(int[] A) {
    // 找出数组 A 中的最大值、最小值
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for (int num : A) {max = Math.max(max, num);
        min = Math.min(min, num);
    }
    // 初始化计数数组 count
    // 长度为最大值减最小值加 1
    int[] count = new int[max-min+1];
    // 对计数数组各元素赋值
    for (int num : A) {
        // A 中的元素要减去最小值，再作为新索引
        count[num-min]++;
    }
    // 计数数组变形，新元素的值是后面元素累加之和的值
    for (int i=1; i<count.length; i++) {count[i] += count[i-1];
    }
    // 创立后果数组
    int[] result = new int[A.length];
    // 遍历 A 中的元素，填充到后果数组中去，从后往前遍历
    for (int j=A.length-1; j>=0; j--) {result[count[A[j]-min]-1] = A[j];
        count[A[j]-min]--;
    }
    return result;
}

08 进阶版的延长之二

既然从后往前遍历原始数组的元素能够保障其原始排序，那么从前往后可不可以达到雷同的成果？

答案时能够的。

第一步：找出数组中的最大值max、最小值min。

第二步：创立一个新数组count，其长度是max-min 加 1 再加 1 ，其元素默认值都为 0。

第三步 ：遍历原数组中的元素，以原数组中的元素作为count 数组的索引，以原数组中的元素呈现次数作为 count 数组的元素值。

第四步 ：对count 数组变形，新元素的值是后面元素累加之和的值，即count[i+1] = count[i+1] + count[i];。

第五步：创立后果数组result，长度和原始数组一样。

第六步 ：从前往后遍历原始数组中的元素，以后元素A[j] 减去最小值 min，作为索引，在计数数组中找到对应的元素值count[A[j]-min]，就是A[j] 在后果数组 result 中的地位，做完上述这些操作，count[A[j]-min]自减少 1。

仍旧以上一个数组 {101,109,107,103,108,102,103,110,107,103} 为例，其中有两个 107，咱们要实现第一个 107 在排序后仍旧排在第二个 107 的后面。

此时计数数组 count 为{0, 1, 2, 5, 5, 5, 5, 7, 8, 9, 10}，从前往后 遍历原始数组 A 中的元素。

第一次遇到 107（A[2]）时，107-101 = 6，count[6] = 5，即第一个 107 在后果数组中的索引为 5，即result[5] = 107，排序后count[6] = 6。

第二次遇到 107（A[8]）时，107-101 = 6，count[6] = 6，即第二个 107 在后果数组中的索引为 6，即result[6] = 107，排序后count[6] = 7。

public int[] countSort5(int[] A) {
    // 找出数组 A 中的最大值、最小值
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for (int num : A) {max = Math.max(max, num);
        min = Math.min(min, num);
    }
    // 初始化计数数组 count
    // 长度为最大值减最小值加 1，再加 1
    int[] count = new int[(max-min+1)+1];
    // 对计数数组各元素赋值，count[0]永远为 0
    for (int num : A) {
        // A 中的元素要减去最小值再加上 1，再作为新索引
        count[num-min+1]++;
    }
    // 计数数组变形，新元素的值是后面元素累加之和的值
    for (int i=1; i<count.length; i++) {count[i] += count[i-1];
    }
    // 创立后果数组
    int[] result = new int[A.length];
    // 遍历 A 中的元素，填充到后果数组中去，从前往后遍历
    for (int j=0; j<A.length; j++) {
        // 如果前面遇到雷同的元素，在后面元素的根底上往后排
        // 如此就保障了原始数组中雷同元素的原始排序
        result[count[A[j]-min]] = A[j];
        count[A[j]-min]++;
    }
    return result;
}

09 小结

以上就是计数排序算法的全部内容了，尽管它能够将排序算法的工夫复杂度升高到 O(N)，然而有两个前提须要满足： 一是须要排序的元素必须是整数，二是排序元素的取值要在肯定范畴内，并且比拟集中。只有这两个条件都满足，能力最大水平施展计数排序的劣势。