当前位置：首页 > article >正文

C语言程序设计十大排序—计数排序

article 2025/1/24 23:52:26

文章目录

1.概念✅
2.计数排序🎈
3.代码实现✅
- 3.1 直接写✨
- 3.2 函数✨
4.总结✅

1.概念✅

排序是数据处理的基本操作之一，每次算法竞赛都很多题目用到排序。排序算法是计算机科学中基础且常用的算法，排序后的数据更易于处理和查找。在计算机发展的历程中，在排序算法的研究一直深受人们重视，出现了很多算法，在思路、效率、应用等方面各有特色。通过学习排序算法，读者可以理解不同算法的优势和局限性，并根据具体情况选择最合适的算法，以提高程序的性能和效率。学习排序算法还有助于培养逻辑思维和问题解决能力，在解决其他类型的问题时也能够应用到类似的思维方法。

2.计数排序🎈

计数排序（Counting Sort）是基于哈希思想的一种排序算法，他使用一种额外的数组（称为计数数组）来统计每个数出现的次数，然后基于次数输出排序后的数组，以数列a[]={5,2,7,3,4,3}为例说明计数排序的操作步骤：

&emsp（1）找到最大值7，建计数数组cnt[8]；

&emsp（2）把数列中的每个数看成cnt[i]的下标i，对应的cnt[i]计数。例如{5}对应cnt[5] = 1，{2}对应cnt[2] = 1，2个{3}对应cnt[3] = 2。

&emsp（3）遍历cnt[]，若cnt[i] = k，输出k次i。输出结果就是排序结果

在这里插入图片描述

&emsp概括地说，计数排序是一种非比较性的排序算法，它使用了元素的值作为建值确定元素在序列中出现的次数，从而实现排序。

3.代码实现✅

3.1 直接写✨

#include <stdio.h>
#include <stdlib.h>
int main()
{
	int arr[] = {4, 2, 2, 8, 3, 3, 1}; // 原始数组
	int n = sizeof(arr) / sizeof(arr[0]); // 数组大小 
	int max = arr[0];
	int i;
	for(i=1;i<n;i++){
		if(max<arr[i])
		     max = arr[i];
	}
	//创建技计数数组并且初始化为0 
	int *count = (int *)calloc(max+1,sizeof(int)); 
      
	
	// 统计每个元素的出现次数
      for ( i = 0; i < n; i++) {
	    count[arr[i]]++;
	 }
		    
	 // 将结果写回原数组
      int index = 0;
      for ( i = 0; i <= max; i++) {
         while (count[i] > 0) {
             arr[index++] = i;
              count[i]--;
        }
     }

    // 释放动态分配的内存
    free(count);

    // 打印排序后的数组
    printf("排序过后的数组: \n");
    for ( i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

3.2 函数✨


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

// 计数排序函数
void countingSort(int arr[], int n) {
    // 找到数组中最大值
    int max = arr[0],i;
    for ( i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }

    // 创建计数数组并初始化为0
    int *count = (int *)calloc(max + 1, sizeof(int));

    // 统计每个元素的出现次数
    for ( i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    // 将结果写回原数组
    int index = 0;
    for ( i = 0; i <= max; i++) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }

    // 释放动态分配的内存
    free(count);
}

// 打印数组的函数
void printArray(int arr[], int n) {
	int i;
    for ( i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1}; // 原始数组
    int n = sizeof(arr) / sizeof(arr[0]); // 数组大小

    countingSort(arr, n); // 调用计数排序函数
    printf("排序过后的数组: \n");
    printArray(arr, n); // 打印排序后的数组

    return 0;
}