算法（六）计数排序

文章目录

计数排序
- 技术排序简介
- 算法实现

计数排序

技术排序简介

计数排序是利用数组下标来确定元素的正确位置的。

假定数组有10个整数，取值范围是0~10，可以根据这有限的范围，建立一个长度为11的数组。数组下标从0到10，元素初始值全为0。
假定给定无序数组数据为：9，1，2，7，8，1，3，6，5，3
创建累计数组，然后遍历无序数组，每一个数按照其值对应累计数组索引下标进行对号入座，每出现一次该值，累计数据该索引下标的值就加1，最终就会得到下面的累计数组：
然后遍历累计数组，就可以得到正确的顺序：：1、1、2、3、3、5、6、7、8、9。

算法实现

package com.xxliao.algorithms.sort.count_sort;

/**
 * @author xxliao
 * @description: 计数排序
 * @date 2024/5/30 21:12
 */
public class CountSort {

    public static void main(String[] args) {
        int[] scores = {95, 94, 91, 98, 99, 90, 99, 93, 91, 92};
        for (int n : countSort(scores, 90)) {
            System.out.print(n + " ");
        }
    }

    /**
     * @description  计数排序
     * array : 待排序数组
     * offset : 数组起始数 -- 为了节约数据空间
     * @author  xxliao
     * @date  2024/5/30 21:13
     */
    public static int[] countSort(int[] array, int offset) {
        // 创建累计数组
        int[] nums = new int[array.length];
        // 遍历待排序数组，将各个元素的进行出现次数标记到累计数组中
        for(int i = 0; i < array.length; i++) {
            int n = array[i] - offset;
            nums[n]++;//累计数组中改索引的值加1
        }
        // 定义最终结果数组
        int[] result = new int[array.length];
        // 定义最终结果数组添加数据索引指针
        int resultIndex = 0;
        //遍历累计数组，填充最终结果数组
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] != 0) { //有值
                for(int j = 0; j < nums[i]; j++) {
                    result[resultIndex++] = i + offset;
                }

            }
        }
        return result;
    }
}