问答文章1 问答文章501 问答文章1001 问答文章1501 问答文章2001 问答文章2501 问答文章3001 问答文章3501 问答文章4001 问答文章4501 问答文章5001 问答文章5501 问答文章6001 问答文章6501 问答文章7001 问答文章7501 问答文章8001 问答文章8501 问答文章9001 问答文章9501

计数排序c语言

发布网友 发布时间：2022-04-24 09:57

我来回答

共3个回答

好二三四 时间：2022-06-13 06:15

排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。以下是计数排序算法：

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

1. 计数排序的特征

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。

通俗地理解，例如有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第 9 位,用这个方法可以得到其他每个人的位置,也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 1 的原因。

?算法的步骤如下：

2. 动图演示

代码实现

JavaScript

实例

function countingSort(arr, maxValue) {
    var bucket = new Array(maxValue+1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1;

    for (var i = 0; i < arrLen; i++) {
        if (!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }

    for (var j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }

    return arr;
}

Python

实例

def countingSort(arr, maxValue):
    bucketLen = maxValue+1
    bucket = [0]*bucketLen
    sortedIndex =0
    arrLen = len(arr)
    for i in range(arrLen):
        if not bucket[arr[i]]:
            bucket[arr[i]]=0
        bucket[arr[i]]+=1
    for j in range(bucketLen):
        while bucket[j]>0:
            arr[sortedIndex] = j
            sortedIndex+=1
            bucket[j]-=1
    return arr

Go

实例

func countingSort(arr []int, maxValue int) []int {
        bucketLen := maxValue + 1
        bucket := make([]int, bucketLen) // 初始为0的数组

        sortedIndex := 0
        length := len(arr)

        for i := 0; i < length; i++ {
                bucket[arr[i]] += 1
        }

        for j := 0; j < bucketLen; j++ {
                for bucket[j] > 0 {
                        arr[sortedIndex] = j
                        sortedIndex += 1
                        bucket[j] -= 1
                }
        }

        return arr
}

Java

实例

public class CountingSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxValue = getMaxValue(arr);

        return countingSort(arr, maxValue);
    }

    private int[] countingSort(int[] arr, int maxValue) {
        int bucketLen = maxValue + 1;
        int[] bucket = new int[bucketLen];

        for (int value : arr) {
            bucket[value]++;
        }

        int sortedIndex = 0;
        for (int j = 0; j < bucketLen; j++) {
            while (bucket[j] > 0) {
                arr[sortedIndex++] = j;
                bucket[j]--;
            }
        }
        return arr;
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

}

PHP

实例

function countingSort($arr, $maxValue = null)
{
    if ($maxValue === null) {
        $maxValue = max($arr);
    }
    for ($m = 0; $m < $maxValue + 1; $m++) {
        $bucket[] = null;
    }

    $arrLen = count($arr);
    for ($i = 0; $i < $arrLen; $i++) {
        if (!array_key_exists($arr[$i], $bucket)) {
            $bucket[$arr[$i]] = 0;
        }
        $bucket[$arr[$i]]++;
    }

    $sortedIndex = 0;
    foreach ($bucket as $key => $len) {
       
        if($len !== null){
            for($j = 0; $j < $len; $j++){
                $arr[$sortedIndex++] = $key;
            }
        }
    }

    return $arr;
}

C

实例

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void print_arr(int *arr, int n) {
        int i;
        printf("%d", arr[0]);
        for (i = 1; i < n; i++)
                printf(" %d", arr[i]);
        printf(" ");
}

void counting_sort(int *ini_arr, int *sorted_arr, int n) {
        int *count_arr = (int *) malloc(sizeof(int) * 100);
        int i, j, k;
        for (k = 0; k < 100; k++)
                count_arr[k] = 0;
        for (i = 0; i < n; i++)
                count_arr[ini_arr[i]]++;
        for (k = 1; k < 100; k++)
                count_arr[k] += count_arr[k - 1];
        for (j = n; j > 0; j--)
                sorted_arr[--count_arr[ini_arr[j - 1]]] = ini_arr[j - 1];
        free(count_arr);
}

int main(int argc, char **argv) {
        int n = 10;
        int i;
        int *arr = (int *) malloc(sizeof(int) * n);
        int *sorted_arr = (int *) malloc(sizeof(int) * n);
        srand(time(0));
        for (i = 0; i < n; i++)
                arr[i] = rand() % 100;
        printf("ini_array: ");
        print_arr(arr, n);
        counting_sort(arr, sorted_arr, n);
        printf("sorted_array: ");
        print_arr(sorted_arr, n);
        free(arr);
        free(sorted_arr);
        return 0;
}

参考地址：

https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/8.countingSort.md

https://zh.wikipedia.org/wiki/%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F

以上为计数排序算法详细介绍，插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法各有优缺点，用一张图概括：

关于时间复杂度

平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；

O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序

线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

关于稳定性

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

名词解释：

n：数据规模

k："桶"的个数

In-place：占用常数内存，不占用额外内存

Out-place：占用额外内存

稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

热心网友 时间：2022-06-13 03:23

这个程序还有点问题，

1. 动态数组申请

2. 访问越界

3. 输出错误


应该就这三个问题了吧，简单的调试了下。

1. 在第9行出现，比较好解决。使用malloc内存分配函数直接解决，注意，在使用完成后需要用free（）去释放这段内存，否则会出现内存泄露。

2. 这个出现在第22行，判断条件写错了，应该判断是j，而不是i。可以将我改过的程序和原始程序进行比较。

3. 这个出现在第38行，因为这里对B数组进行修改，或者说排序，所以应该输出的B数组的元素。而原始程序是输出A数组的元素，这里A数组中的元素并没有改变，所以，输出肯定和定义A时一样，不会出现期望的顺序。


贴一下我执行的结果：


修改后的代码：

#include <stdio.h>
#include <string.h>
#include <malloc.h>

//计数排序函数
void counting_sort(int A[], int B[], int k, int length)     //k 为待排序数组A中最大元素
{
int i, j, temp;
int *C = (int*)malloc(sizeof(int) * (k + 1));
for (i = 0; i <= k; i++)                        //数组C初始化 
{
C[i] = 0;
}
for (j = 1; j <= length - 1; j++)                //C[i]中包含等于i的元素的个数 
{
C[A[j]] = C[A[j]] + 1;
}
for (i = 1; i <= k; i++)                        //C[i]中包含小于或等于i的元素的个数 
{
C[i] = C[i] + C[i - 1];
}
for (j = length - 1; j >= 0; j--)                //元素重排 
{
B[C[A[j]]] = A[j];
C[A[j]]--;
}
free(C);
}

//测试计数排序函数
main()
{
int A[] = { 2, 6, 1, 2, 4, 5, 9, 6, 4, 5, 8, 2, 3, 7 };
int B[] = { 2, 6, 1, 2, 4, 5, 9, 6, 4, 5, 8, 2, 3, 7 };
int k = 9, i;
counting_sort(A, B, 9, 14);
for (i = 0; i <= 13; i++)
printf("    %d", B[i]);
printf("\n");
return 0;
}

热心网友 时间：2022-06-13 04:41

数组C的大小没有确定
声明声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL:11247931@qq.com
ups快递客服电话24小时 贷款记录在征信保留几年? 安徽徽商城有限公司公司简介 安徽省徽商集团新能源股份有限公司基本情况 安徽省徽商集团有限公司经营理念 2019哈尔滨煤气费怎么有税? 快手删除的作品如何恢复 体育理念体育理念 有关体育的格言和理念 什么是体育理念 英语专业有什么特点? 想问您一些排序算法的伪代码,谢啦 初中英语的学科特点 数据结构中排序的方法中稳定的有那些,不稳定的有那些(如快速排序等... 小学英语科目特点 稳定的排序算法有哪些? 英语学科特点 “二分法插入排序”、“快速排序”、“归并排序”和“堆排序”的时间... 英语学科成绩分析老师怎么写 除了经典和常用的排序算法外,还有哪些奇葩而有趣的排序算法 和常用的排序算法外,还有哪些奇葩而有趣的排序算法 稳定排序有哪些 pythonCOUNTING SORT排位后相乘对应的数字 C++ 排序问题 quick sort , counting sort 和 heap sort counting sort运行内存错误 在用电脑登录微信打字聊天的时候,怎么进入到拼音界面打字聊天? 电镀槽液中高锰酸钾过量怎么解决 电镀过程中镀铜槽会爆炸? 如何解决电镀槽液温度过高? 电镀废水含什么成分,一般怎么处理 向英语初学者介绍英语这门学科背景等 排序算法及MATLAB实现 kind of的词性 perl 飞碟操作符{ $a &lt;=&gt; $b } 运行机制 乐视手机在哪开启微信设备锁 C++计数排序 想要一个C++实现外排序的源代码 对英语这门学科的看法 什么是计数排序 初中英语学科特点概括 C语言实现计数排序,求代码,最好用链表 急!这是个计数问题 高中英语学科特点 作为小学英语老师,你认为这一学科有什么特点 非志无以成学,志字的词类活用 狼怎么画既简单又凶? 《诫子书》中的非志了人以成学中的志是什么意思? 非学无以广才非志无以成学的意思是什么? 怎样画一只霸气的狼王 非学无以广才,非志无以成学.什么意思
懂视IT 51dongshi.com 版权所有
Copyright © 2019-2024