反饋

計數排序

計數排序是一個非基於比較的排序算法，該算法於1954年由 Harold H. Seward 提出。它的優勢在於在對一定範圍內的整數排序時，它的複雜度為Ο(n+k)（其中k是整數的範圍），快於任何比較排序算法。^[1] 當然這是一種犧牲空間換取時間的做法，而且當O(k)＞O(n*log(n))的時候其效率反而不如基於比較的排序（基於比較的排序的時間複雜度在理論上的下限是O(n*log(n)), 如歸併排序，堆排序）

中文名: 計數排序
外文名: Counting Sort

提出人: Harold H. Seward
提出時間: 1954年
定義: 非基於比較的排序算法

計數排序算法思想

計數排序對輸入的數據有附加的限制條件：

1、輸入的線性表的元素屬於有限偏序集S；

2、設輸入的線性表的長度為n，|S|=k（表示集合S中元素的總數目為k），則k=O(n)。

在這兩個條件下，計數排序的複雜性為O(n)。

計數排序的基本思想是對於給定的輸入序列中的每一個元素x，確定該序列中值小於x的元素的個數（此處並非比較各元素的大小，而是通過對元素值的計數和計數值的累加來確定）。一旦有了這個信息，就可以將x直接存放到最終的輸出序列的正確位置上。例如，如果輸入序列中只有17個元素的值小於x的值，則x可以直接存放在輸出序列的第18個位置上。當然，如果有多個元素具有相同的值時，我們不能將這些元素放在輸出序列的同一個位置上，因此，上述方案還要作適當的修改。

計數排序排序過程

假設輸入的線性表L的長度為n，L=L1,L2,..,Ln；線性表的元素屬於有限偏序集S，|S|=k且k=O(n)，S={S1,S2,..Sk}；則計數排序可以描述如下：

1、掃描整個集合S，對每一個Si∈S，找到在線性表L中小於等於Si的元素的個數T(Si)；

2、掃描整個線性表L，對L中的每一個元素Li，將Li放在輸出線性表的第T(Li)個位置上，並將T(Li)減1。

計數排序算法描述

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.

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;
}

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
}

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;
    }
}

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] --
       }
    }
}

計數排序總結

我們看到，計數排序算法沒有用到元素間的比較，它利用元素的實際值來確定它們在輸出數組中的位置。因此，計數排序算法不是一個基於比較的排序算法，從而它的計算時間下界不再是O(nlogn)。另一方面，計數排序算法之所以能取得線性計算時間的上界是因為對元素的取值範圍作了一定限制，即k=O(n)。如果k=n^2,n^3,..，就得不到線性時間的上界。此外，我們還看到，由於算法第4行使用了downto語句，經計數排序，輸出序列中值相同的元素之間的相對次序與他們在輸入序列中的相對次序相同，換句話説，計數排序算法是一個穩定的排序算法。