B站视频演示地址:https://www.bilibili.com/video/BV1GW411H7Cs/
概念:计数排序是一个非基于比较的排序算法,而是利用数组下标来确定元素的正确位置。用辅助数组对数组中出现的数字技术,元素转下标,下标转元素。
假设元素均大于等于0,一次扫描原数组,将元素值K记录在辅助数组的K位上。
1,基础版计数排序
假定20个随机整数的值如下:
9,3,5,4,9,1,2,7,8,1,3,6,5,3,4,0,10,9,7,9
创建一个辅助数组(长度为最大值+1)
先遍历这个无序的随机数列,每一个整数按照其值对号入座,对应数组下标的元素进行加1操作。
比如第一个整数是9,那么数组下标为9的元素加1:
第二个整数是3,那么数组下标为3的元素加1:
继续遍历数列并修改数组。。。。。。
最终,数列遍历完毕时,数组的状态如下:
遍历数组,输出数组元素的下标值,元素的值是几,就输出几次:
0,1,1,2,3,3,3,4,4,5,5,6,7,7,8,9,9,9,9,10
public static void countSort1(int[] arr) { int max = arr[0]; for (int i : arr) { if (i > max) { max = i; } } int[] countarr = new int[max + 1]; for (int j : countarr) { countarr[j]++; } int current = 0; for (int i = 0; i < countarr.length; i++) { while (countarr[i] > 0) { arr[current] = i; countarr[i]--; current++; } } }
2,改进版:
public static void countSort(int[] arr) { // 找到arr的最大值和最小值 int min = arr[0]; int max = arr[0]; for (int i : arr) { if (i < min) { min = i; } if (i > max) { max = i; } } // 创建计数数组 int[] countArr = new int[max - min + 1]; for (int j : countArr) { countArr[j - min]++; } // 定义指针 int current = 0; // 回填 for (int i = 0; i < countArr.length; i++) { while (countArr[i] > 0) { arr[current] = i + min; current++; } } }
3,最终版
public static int[] countArr3(int[] arr) { int min = arr[0]; int max = arr[0]; for (int i : arr) { if (i < min) { min = i; } if (i > max) { max = i; } } // 创建计数数组 int[] countArr = new int[max - min + 1]; for (int j : countArr) { countArr[j - min]++; } // 对计数数组的元素进行累加,累加的规则将前一个元素的值+当前元素的值 for (int i = 1; i < countArr.length; i++) { countArr[i] += countArr[i - 1]; } // 创建一个数组,存储最终的有序数列 int[] sortedArr = new int[arr.length]; // 回填 for (int i = arr.length - 1; i >= 0; i--) { sortedArr[countArr[arr[i] - min] - 1] = arr[i]; countArr[arr[i] - min]--; } return sortedArr; }
以上皆为笔记
评论 (0)