詳解計數排序算法及C說話法式中的完成

詳解計數排序算法及C說話法式中的完成。本站提示廣大學習愛好者：（詳解計數排序算法及C說話法式中的完成）文章只能為提供參考，不一定能成為您想要的結果。以下是詳解計數排序算法及C說話法式中的完成正文

關於計數排序算法

當輸出的元素是 n 個 0 到 k 之間的整數時，它的運轉時光是 Θ(n + k)。計數排序不是比擬排序，排序的速度快於任何比擬排序算法。

因為用來計數的數組C的長度取決於待排序數組中數據的規模（等於待排序數組的最年夜值與最小值的差加上1），這使得計數排序關於數據規模很年夜的數組，須要年夜量內存。計數排序是用來排序0到100之間的數字的最好的算法，然則它不合適按字母次序排序人名。然則，計數排序可以用在基數排序中的算法來排序數據規模很年夜的數組。

算法的步調以下：

• 找出待排序的數組中最年夜和最小的元素
• 統計數組中每一個值為i的元素湧現的次數，存入數組C的第i項
• 對一切的計數累加（從C中的第一個元素開端，每項和前一項相加）
• 反向填充目的數組：將每一個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1

代碼示例：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
void CountingSort(int *A,int *B,int *Order,int N,int K)
{
  int *C=new int[K+1];
  int i;
  memset(C,0,sizeof(int)*(K+1));
  for (i=1;i<=N;i++) //把A中的每一個元素分派
    C[A[i]]++;
  for (i=2;i<=K;i++) //統計不年夜於i的元素的個數
    C[i]+=C[i-1];
  for (i=N;i>=1;i--)
  {
    B[C[A[i]]]=A[i]; //依照統計的地位，將值輸入到B中，將次序輸入到Order中
    Order[C[A[i]]]=i;
    C[A[i]]--;
  }
}
int main()
{
  int *A,*B,*Order,N=15,K=10,i;
  A=new int[N+1];
  B=new int[N+1];
  Order=new int[N+1];
  for (i=1;i<=N;i++)
    A[i]=rand()%K+1; //生成1..K的隨機數
  printf("Before CS:\n");
  for (i=1;i<=N;i++)
    printf("%d ",A[i]);
  CountingSort(A,B,Order,N,K);
  printf("\nAfter CS:\n");
  for (i=1;i<=N;i++)
    printf("%d ",B[i]);
  printf("\nOrder:\n");
  for (i=1;i<=N;i++)
    printf("%d ",Order[i]);
  return 0;
}