1,计数排序是一个非基于比较的线性时间排序算法。
它对输入的数据有附加的限制条件:
(1)、输入的线性表的元素属于有限偏序集S;
(2)、设输入的线性表的长度为n,|S|=k(表示集合S中元素的总数目为k),则 k=O(n)。
在这两个条件下,计数排序的复杂性为O(n)。
2,计数排序算法的基本思想是对于给定的输入序列中的每一个元素x,确定该序列中值小于x的元素的个数。一旦有了这个信息,就可以将x直接存放到最终的输出序列的正确位置上。
当然,如果有多个元素具有相同的值时,我们不能将这些元素放在输出序列的同一个位置上,因此,上述方案还要作适当的修改。
3,实例代码:
#include<iostream>
using namespace std;
//考虑重复元素的情况
void CountingSort(int data[], int n)
{
int* tmp=new int[n];
int max=data[0];
for(int i=1;i<n;i++)
max=(max>data[i]? max:data[i]);
int* count = new int[max+1];
memset(count, 0, (max+1)*sizeof(int));
//统计每个元素的个数
for (int i = 0; i < n; i++)
count[data[i]]++;
//数组中小于等于当前data[i]的元素个数
for (int i = 1; i <= max; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--)
{
tmp[ count[data[i]]-1 ] = data[i];
count[data[i]]--;
}
for (int i = 0; i < n; i++)
data[i]=tmp[i];
delete[] count;
delete[] tmp;
}
void Output(int data[], int n)
{
for(int i = 0 ; i < n ; i++ )
cout << data[i] << " ";
cout << endl;
}
int main()
{
int data[]={73, 22, 93, 43, 55, 55, 14, 28, 65, 39, 81};
int n=sizeof(data)/sizeof(data[0]);
CountingSort(data,n);
Output(data,n);
return 0;
}
分享到:
相关推荐
计数排序是一种非基于比较的排序算法,它适用于待排序数据是整数的情况。这种算法的基本思想是通过统计每个整数出现的次数,然后利用这些信息来直接确定每个元素在输出数组中的位置。计数排序在某些特定情况下可以...
### 计数排序源代码C++实现 #### 知识点概述 计数排序是一种非比较型整数排序算法,其通过确定每个元素在最终排序数组中的位置来达到排序的效果,而无需相互比较。该算法适用于一定范围内的整数排序,并且在数据...
"C语言版的排序方法---计数排序" 计数排序是一种非比较排序算法,它的工作原理是通过统计每个元素在数组中的出现次数,然后根据这些统计结果将元素排列到正确的位置。下面是对计数排序的详细解释: 1. 初始化计数...
计数排序是一种非基于比较的排序算法,它的主要思想是通过统计待排序数组中每个元素出现的次数,然后根据这些计数来确定每个元素在排序结果中的位置。这种算法特别适用于整数排序,且在数据范围不大的情况下,效率极...
计数排序是一种非基于比较的排序算法,它适用于待排序的元素是整数的情况。这种算法的基本思想是通过统计每个不同整数出现的次数,然后根据这些计数值来确定每个元素在排序结果中的位置。计数排序的时间复杂度为O(n)...
超级经典的计数排序算法,号称效率达到了O(n) 超级经典的计数排序算法,号称效率达到了O(n) 超级经典的计数排序算法,号称效率达到了O(n) 超级经典的计数排序算法,号称效率达到了O(n) 超级经典的计数排序算法,号称...
Java实现计数排序不是C,Java实现计数排序不是C,Java实现计数排序不是C
主要是对算法导论中计数排序的实现
计数排序(代码片段)
排序算法之计数排序,计数排序是一种线性的排序算法,比基于比较的排序算法效率高,但其应用有特定的领域。我给出了两种策略的计数排序算法,欢迎下载~~如程序中有Bug,恳请指正!
计数排序.py 使用python来实现计数排序.py 使用python来实现计数排序.py 使用python来实现计数排序.py 使用python来实现计数排序.py 使用python来实现计数排序.py 使用python来实现计数排序.py 使用python来实现计数...
计数排序是一种非比较型的排序算法,适用于一定范围内的整数排序。在该算法中,使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。计数排序的关键在于它不是比较两个元素的大小,而是统计每个...
### Python3实现计数排序(源代码) #### 实现原理 计数排序是一种非基于比较的排序算法,其核心思想是将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据...
### C++实现计数排序(源代码) #### 实现原理 计数排序是一种非比较型整数排序算法,其核心思想在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序算法,计数排序要求输入的...
该资源提供了在Java中如何实现计数排序的全面指南。文档涵盖了计数排序的基本概念,包括如何对数组进行排序以及如何在Java中实现计数排序。此外,文档还包括一个逐步指南,介绍了如何在Java中实现计数排序,包括详细...
利用python实现计数排序,程序直接可以用
JavaScript中的计数排序算法是一种非比较型排序算法,它的核心思想是通过统计待排序数组中每个元素出现的次数,然后根据这些计数直接确定每个元素在输出数组中的位置。由于这种算法是基于数字的出现频率来进行排序,...
计数排序是一种非基于比较的排序算法,它适用于待排序的元素是整数的情况。它的基本思想是通过确定每个输入元素出现的次数,然后利用这些信息来直接计算出每个元素在输出序列中的位置。计数排序是线性的,时间复杂度...
计数排序介绍和Java代码实现 计数排序是一种非比较的线性时间复杂度排序算法,它通过统计每个元素在待排序数组中出现的次数,然后根据统计信息将元素放回原数组中,从而实现排序。下面是计数排序的详细介绍。 计数...
countingSort 方法实现了计数排序算法。首先,我们遍历一遍原数组,找出其中的最大值,以确定计数数组的大小。然后,创建计数数组 count,并将每个元素的出现次数记录在计数数组中。接下来,根据计数数组中的元素...