黑马程序员技术交流社区

标题: 计数排序的 Java 实现 [打印本页]

作者: haoxiujie 时间: 2018-8-3 10:26
标题: 计数排序的 Java 实现
本帖最后由 haoxiujie 于 2018-8-3 10:36 编辑

计数排序的 Java 实现
在基础班的课程中，阿君老师讲授了冒泡排序。常见的排序算法有很多种，冒泡排序是所有排序算法中最容易理解的，但不是最佳的排序算法。常见的排序算法有插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序、桶排序、基数排序等。
本文就计数排序进行简单 Java 实现。

1. 计数排序的优势计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。计数排序要求输入的数据必须是有确定范围的整数。
以下是计数排序的具体情况：

时间复杂度（平均）：

O(n+k)

时间复杂度（最坏）：

O(n+k)

时间复杂度（最好）：

O(n+k)

空间复杂度：

O(n+k)

线性特征：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因属于线性时间非比较类排序。
稳定性特征：如果 a 原本在 b 前面，而a==b，排序之后 a 仍然在 b 的前面。

2. 计数排序的算法描述找出数组中的最大值 maxValue，创建一个大小为 maxValue+1 的临时数组 C；
将源数组的值 i 累加到数组 C 项中；
依次将 C 项中的 i 赋值给源数组 C 次。

动图演示：

（动图转载自：https://www.cnblogs.com/onepixel/p/7674659.html）

3. 计数排序的 Java 实现
[Java] 纯文本查看 复制代码
public class CountingSort {

public static int[] countingSort(int[] arr) {
      int[] c = new int[maxValue(arr) + 1];
      for (int i = 0; i < arr.length; i++) {
         c[arr]++;
      }

      for (int i = 0, count = 0; i < c.length; i++) {
         while (c > 0) {
            arr[count++] = i;
            c--;
         }
      }
      return arr;
}

private static int maxValue(int[] arr) {
      int max = arr[0];
      for (int i = 1; i < arr.length; i++)
         if (arr > max)
            max = arr;
      return max;
}
}

849589-20171015231740840-6968181.gif (264.41 KB, 下载次数: 8)

download.png (2.71 KB, 下载次数: 9)

download.png (2.71 KB, 下载次数: 26)

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2