不知

计数排序

2021-11-02|来源:|发布者:

计数排序是一个非基于比较的排序算法,该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法。当然这是一种牺牲空间换取时间的做法,而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序(基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序,堆排序)

1. 算法步骤

1、找出待排序的数组中最大和最小的元素

2、统计数组中每个值为i的元素出现的次数,存入数组C的第i项

3、对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)

4、反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1

2. 动图演示

计数排序

3. 时间复杂度

复杂度为Ο(n+k)(其中k是整数的范围)

4. 算法实现

计数排序C语言

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

#define MAXNUM 10

void main()
{
    void CountSort(int data[],int n);
    int i,data[MAXNUM];
    for(i=0;i<MAXNUM;i++)
        scanf("%d",&data[i]);
    CountSort(data,MAXNUM);
    for(i=0;i<MAXNUM;i++)
        printf("%d ",data[i]);
    printf("\n");
}

void CountSort(int data[],int n)
{
    int i,j,count,*data_p,temp;
    data_p=(int*)malloc(sizeof(int)*n);
    for(i=0;i<n;i++)//初始化data_p
        data_p[i]=0;
    for(i=0;i<n;i++)
    {
        count=0;
        for(j=0;j<n;j++)//扫描待排序数组
            if(data[j]<data[i])//统计比data[i]值小的值的个数
                count++;
        while(data_p[count]!=0)//对于相等非0的数据,应向后措一位。数据为0时,因数组data_p被初始化为0,故不受影响。
        /* 注意此处应使用while循环进行判断,若用if条件则超过三个重复值后有0出现 */    
                count++;
        data_p[count]=data[i];//存放到data_p中的对应位置
    }
        //用于检查当有多个数相同时的情况
    i=0,j=n;
    while(i<j)
        {
        if(data_p[i]==0)
                {
            temp=i-1;
            data_p[i]=data_p[temp];
        }//of if
        i++;
    }//of  while
    for(i=0;i<n;i++)//把排序完的数据复制到data中
        data[i]=data_p[i];
    free(data_p);//释放data_p
}

计数排序C++

#include <iostream>
using namespace std;
const int MAXN = 100000;
const int k = 1000; // range(范围)
int a[MAXN], c[MAXN], ranked[MAXN];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i]; 
        ++c[a[i]];
    }
    for (int i = 1; i < k; ++i)
        c[i] += c[i-1];
    for (int i = n-1; i >= 0; --i)
        ranked[--c[a[i]]] = a[i];//如果是i表达的是原数标号,a[i]就是排序后的正确序列
    for (int i = 0; i < n; ++i)
        cout << ranked[i] << endl;
    return 0;
}

计数排序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) $arr[$sortedIndex++] = $key;
        if($len !== null){
            for($j = 0; $j < $len; $j++){
                $arr[$sortedIndex++] = $key;
            }
        }
    }

    return $arr;
}

计数排序JAVA

//针对c数组的大小,优化过的计数排序
publicclassCountSort{
    publicstaticvoidmain(String[]args){
      //排序的数组
        int a[]={100,93,97,92,96,99,92,89,93,97,90,94,92,95};
        int b[]=countSort(a);
        for(inti:b){
           System.out.print(i+"");
        }
        System.out.println();
    }
    public static int[] countSort(int[]a){
        int b[] = new int[a.length];
        int max = a[0],min = a[0];
        for(int i:a){
            if(i>max){
                max=i;
            }
            if(i<min){
                min=i;
            }
        }//这里k的大小是要排序的数组中,元素大小的极值差+1
        int k=max-min+1;
        int c[]=new int[k];
        for(int i=0;i<a.length;++i){
            c[a[i]-min]+=1;//优化过的地方,减小了数组c的大小
        }
        for(int i=1;i<c.length;++i){
            c[i]=c[i]+c[i-1];
        }
        for(int i=a.length-1;i>=0;--i){
            b[--c[a[i]-min]]=a[i];//按存取的方式取出c的元素
        }
    return b;
    }
}

计数排序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;
}

计数排序C#语言

public int[] CountSort(int[] a)
{
    int[] b = new int[a.Length];
    int max = a[0];
    int min = a[0];
    foreach (int item in a)
    {
        if(item > max)
        {
            max = item;
        }
        else if (item < min)
        {
            min = item;
        }
    }
    int k = max - min + 1;
    int[] c = new int[k];
    for (int i = 0; i < a.Length; i++)
    {
        c[a[i] - min] += 1;
    }
    for (int i = 1; i < c.Length; i++)
    {
        c[i] = c[i] + c[i - 1];
    }
    for (int i = a.Length-1; i >= 0; i--)
    {
        b[--c[a[i] - min]] = a[i];
    }
    return b;
}

计数排序Python

def count_sort(input_list):
length = len(input_list)
if length < 2:
	return input_list
max_num = max(input_list)
count = [0] * (max_num + 1)
for element in input_list:
	count[element] += 1
output_list = []
for i in range(max_num + 1):
	for j in range(count[i]):  # count[i]表示元素i出现的次数,如果有多次,通过循环重复追加        
		output_list.append(i)
return output_list

计数排序Go语言

func countSort(arr []int) {
	maxVal := 0
	length := len(arr)
	for i := 0; i < length; i ++ {
		   if arr[i] > maxVal {
		 maxVal = arr[i]
		   }
	 }
 
	 tmp := make([]int, maxVal+1)
	 for i := 0; i < length; i ++ {
		 tmp[arr[i]] += 1
	 }
 
	 j := 0
	 for i := 0; i < maxVal+1; i ++ {
		for tmp[i] > 0 {
		   arr[j] = i
		   j ++
		   tmp[i] --
		}
	 }
 }

计数排序PASCAL

实现方法1:
program counting_sort1;

var 
    a,b,c:Array[1..max] of longint;
    i,j,k,n:longint;
begin
    readln(n);
    for i:=1 to n do read(a[i]);
    fillchar(c,sizeof(c),0);
    for j:=1 to n do inc(c[a[j]]);
    for i:=2 to x{x是大于a[i]中任意值的任意数且x≤max}do c[i]:=c[i]+c[i-1];
    for j:=n downto 1 do
    begin
        b[c[a[j]]]:=a[j];
        dec(c[a[j]]);
    end;
    for i:=1 to n do writeln(b[i],' ');
end.
实现方法2:
program counting_sort2;
const max=100;
var 
 a:array[1..max] of longint;
 i,j,k,n,m,x:longint;
begin
 readln(n);
 fillchar(a,sizeof(a),0);//初始清空
 m:=0;
 for i:=1 to n do
  begin
   read(x);
   inc(a[x]);
   if x>m then m:=x;//找到最大的数
  end;
 for i:=1 to m do
  if a[i]>0 then
   for j:=1 to a[i] do
    write(i,' ');
end.

用手机扫一扫访问本站
妖姬屋文章数据均来自于互联网,版权归原作者所有。如有侵犯您权利的资源,请联系我们处理。
Copyright © 2016-2024 妖姬屋 版权所有