搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > Android部落格 > 算法-排序-计数排序

算法-排序-计数排序

Android部落格 2020-08-02

1.1 描述

  • 找出待排序的数组中最大和最小的元素;
  • 统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
  • 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
  • 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。

1.2 代码

package com.chuck.algorithmproject.sort;
import android.util.Log;
import java.util.Arrays;
public class CountSort { private static String TAG = "CountSort"; private static int[] number = {5, 8, 3, 6, 9, 10, 34, 3, 7, 6};
public static void countSort() { int maxNumber = number[0]; int minNumber = maxNumber; int size = number.length; for (int index = 0; index < size; index++) { if (number[index] > maxNumber) { maxNumber = number[index]; } if (number[index] < minNumber) { minNumber = number[index]; } } Log.e(TAG, "maxNumber:" + maxNumber + ",minNumber:" + minNumber); int tempArraySize = maxNumber - minNumber + 1; int[] tempArray = new int[tempArraySize]; for (int index = 0; index < size; index++) { ++tempArray[number[index] - minNumber]; } int originNumberIndex = 0; for (int index = 0; index < tempArraySize; index++) { while (tempArray[index] != 0) { number[originNumberIndex++] = index + minNumber; --tempArray[index]; } } Log.e(TAG, "sorted number is " + Arrays.toString(number)); }}

1.3 总结

  • 先找出给出数组的最大值,最小值;
  • 创建最大值 - 最小值 + 1个大小的数组;
  • 以index为序分别填入待排序数组中每个元素的个数,以此累加;
  • 需要注意的是,存储元素个数的数组序号要减去最小值,反向填充数组的时候要加上最小值,避免数组溢出。

示意图如下:

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《算法-排序-计数排序》的版权归原作者「Android部落格」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注Android部落格微信公众号

Android部落格微信公众号:chuck2Dev

Android部落格

手机扫描上方二维码即可关注Android部落格微信公众号

Android部落格最新文章

精品公众号随机推荐