网站建设收费价目表,长治市住房保障和城乡建设管理局网站,四川网站建设有哪些,app开发流程详解图解 计数排序是一种线性时间复杂度的排序算法#xff0c;它不基于比较排序#xff0c;而是根据待排序序列中元素的值来进行排序。
具体的过程如下#xff1a; 统计序列中每个元素出现的个数#xff0c;得到一个计数数组count。其中#xff0c;count[i]表示待排序序列中值… 图解 计数排序是一种线性时间复杂度的排序算法它不基于比较排序而是根据待排序序列中元素的值来进行排序。
具体的过程如下 统计序列中每个元素出现的个数得到一个计数数组count。其中count[i]表示待排序序列中值为i的元素出现的次数。 对计数数组做累加操作得到一个前缀和数组sum。其中sum[i]表示待排序序列中所有小于等于i的元素的个数。 根据sum数组中元素的值将待排序序列中的元素放到相应的位置上。具体做法是对于待排序序列中的元素a[i]找到sum[a[i]]将a[i]放到输出序列的sum[a[i]]-1位置上然后将sum[a[i]]-1减1。
计数排序的时间复杂度为O(nk)其中n为待排序序列的长度k为待排序序列中元素的取值范围。
需要注意的是计数排序只适用于元素取值范围不大的情况下否则空间复杂度会很高。此外计数排序是一种稳定排序算法即具有相同值的元素在排序后相对位置不会发生改变。
计数排序是一种非比较排序方式它的基本思想是统计每个元素在序列中出现的次数然后根据统计信息将原序列中的元素排列到正确的位置上。以下是Java实现计数排序的示例代码
public class CountingSort {public static void countingSort(int[] arr) {if (arr null || arr.length 0) {return;}int max arr[0];int min arr[0];for (int i 1; i arr.length; i) { // 找出数组中的最大值和最小值if (arr[i] max) {max arr[i];}if (arr[i] min) {min arr[i];}}int[] count new int[max - min 1]; // 计数数组for (int i 0; i arr.length; i) {count[arr[i] - min]; // 统计元素出现次数}int index 0;for (int i 0; i count.length; i) { // 将元素按计数数组中的统计信息排序while (count[i]-- 0) {arr[index] i min;}}}
}在主函数中可以通过以下方式使用计数排序的函数
int[] arr {5, 3, 7, 1, 8, 2, 6, 4};
CountingSort.countingSort(arr);
System.out.println(Arrays.toString(arr));输出结果为
[1, 2, 3, 4, 5, 6, 7, 8]
