/************************************************************************* 
  > File Name: CountingSort.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<iostream> 
using namespace std; 
 
/* 
 *计数排序：A和B为待排和目标数组，k为数组中最大值,len为数组长度 
 */ 
void CountingSort(int A[], int B[], int k, int len) 
{ 
  int C[k+1]; 
  for(int i=0; i<k+1; ++i) 
    C[i] = 0; 
  for(int i=0; i<len; ++i) 
    C[A[i]] += 1; 
  for(int i=1; i<k+1; ++i) 
    C[i] = C[i] + C[i-1]; 
  for(int i=len-1; i>=0; --i) 
  { 
    B[C[A[i]]-1] = A[i]; 
    C[A[i]] -= 1; 
  } 
} 
 
/* 输出数组 */ 
void print(int arr[], int len) 
{ 
  for(int i=0; i<len; ++i) 
    cout << arr[i] << " "; 
  cout << endl; 
} 
 
/* 测试 */ 
int main() 
{ 
  int origin[8] = {4,5,3,0,2,1,15,6}; 
  int result[8]; 
  print(origin, 8); 
  CountingSort(origin, result, 15, 8); 
  print(result, 8); 
  return 0; 
}

/************************************************************************* 
  > File Name: BucketSort.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<iostream> 
using namespace std; 
 
/* 节点 */ 
struct node 
{ 
  int value; 
  node* next; 
}; 
 
/* 桶排序 */ 
void BucketSort(int A[], int max, int len) 
{ 
  node bucket[len]; 
  int count=0; 
  for(int i=0; i<len; ++i) 
  { 
    bucket[i].value = 0; 
    bucket[i].next = NULL; 
  } 
   
  for(int i=0; i<len; ++i) 
  { 
    node *ist = new node(); 
    ist->value = A[i]; 
    ist->next = NULL; 
    int idx = A[i]*len/(max+1); // 计算索引 
    if(bucket[idx].next == NULL) 
    { 
      bucket[idx].next = ist; 
    } 
    else /* 按大小顺序插入链表相应位置 */ 
    { 
      node *p = &bucket[idx]; 
      node *q = p->next; 
      while(q!=NULL && q->value <= A[i]) 
      { 
        p = q; 
        q = p->next; 
      } 
      ist->next = q; 
      p->next = ist; 
    } 
  } 
 
  for(int i=0; i<len; ++i) 
  { 
    node *p = bucket[i].next; 
    if(p == NULL) 
      continue; 
    while(p!= NULL) 
    { 
      A[count++] = p->value; 
      p = p->next; 
    } 
  } 
} 
 
/* 输出数组 */ 
void print(int A[], int len) 
{ 
  for(int i=0; i<len; ++i) 
    cout << A[i] << " "; 
  cout << endl; 
} 
 
/* 测试 */ 
int main() 
{ 
  int row[11] = {24,37,44,12,89,93,77,61,58,3,100}; 
  print(row, 11); 
  BucketSort(row, 235, 11); 
  print(row, 11); 
  return 0; 
} 

/************************************************************************* 
  > File Name: RadixSort.cpp 
  > Author: SongLee 
 ************************************************************************/ 
#include<iostream> 
using namespace std; 
 
// 找出整数num第n位的数字 
int findIt(int num, int n) 
{ 
  int power = 1; 
  for (int i = 0; i < n; i++) 
  { 
    power *= 10; 
  } 
  return (num % power) * 10 / power; 
} 
 
// 基数排序（使用计数排序作为辅助） 
void RadixSort(int A[], int len, int k) 
{ 
  for(int i=1; i<=k; ++i) 
  { 
    int C[10] = {0};  // 计数数组 
    int B[len];    // 结果数组 
 
    for(int j=0; j<len; ++j) 
    { 
      int d = findIt(A[j], i); 
      C[d] += 1; 
    } 
 
    for(int j=1; j<10; ++j) 
      C[j] = C[j] + C[j-1]; 
 
    for(int j=len-1; j>=0; --j) 
    { 
      int d = findIt(A[j], i); 
      C[d] -= 1; 
      B[C[d]] = A[j]; 
    } 
     
    // 将B中排好序的拷贝到A中 
    for(int j=0; j<len; ++j) 
      A[j] = B[j]; 
  } 
} 
 
// 输出数组 
void print(int A[], int len) 
{ 
  for(int i=0; i<len; ++i) 
    cout << A[i] << " "; 
  cout << endl; 
} 
 
// 测试 
int main() 
{ 
  int A[8] = {332, 653, 632, 5, 755, 433, 722, 48}; 
  print(A, 8); 
  RadixSort(A, 8, 3); 
  print(A, 8); 
  return 0; 
}