作业介绍
C2.07 数组排序
计数排序与选择排序
-
计数排序_基本原理
计数排序
是一种非比较排序算法,其核心思想是将序列中的元素作为键存储在额外的数组空间中,而该元素的个数作为值存储在数组空间中,通过遍历该数组进行排序。
-
计数排序_参考代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
// 定义一个大小为 100005 的整型数组 a ,并初始化为 0 。这个数组用于记录每个整数出现的次数
int a[100005]={0};
// 声明变量 n(表示整数数量),m(用于临时存储输入的整数)和 max1(用于记录输入中的最大整数)
int n, m, max1=0;
cin>>n; // 从标准输入读取整数 n
for(int i=1;i<=n;i++) // 循环 n 次,每次读取一个整数
{
cin>>m; // 读取整数 m
max1=max(max1,m); // 更新 max1 为 max1 和 m 中的较大值
a[m]++; // 将整数 m 在数组 a 中的对应位置加 1
}
for(int i=0;i<=max1;i++) // 循环从 0 到 max1,遍历数组 a
{
while(a[i]) // 如果整数 i 出现过(即 a[i] 大于 0 )
{
cout<<i<<" "; // 输出整数 i
a[i]--; // 将整数 i 在数组 a 中的计数减 1 ,表示已经输出了一次
}
}
return 0;
}
-
计数排序_代码解析
- 首先,找出待排序的数组中最大和最小的元素。
- 然后,创建一个新的计数数组,其大小为最大值与最小值的差加1。
- 针对所有的元素重复以上的步骤,除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较
- 对计数数组进行累加操作,使每个索引的值变为小于或等于该索引的元素的个数。
- 反向遍历待排序数组,对于每个元素,根据其在计数数组中的值确定其在排序后数组中的位置,并将其放到正确的位置上。
题目
认领作业后才可以查看作业内容。
- 状态
- 正在进行…
- 题目
- 3
- 开始时间
- 2024-1-1 0:00
- 截止时间
- 2099-12-31 23:59
- 可延期
- 0 小时