public class CountSort {
static int[] countSort(int[] a, int range/*数组元素的范围*/){
int count[] = new int[range];
for (int i = 0; i < a.length; i++) {
count[a[i]]++;
}
for (int i = 1; i < count.length; i++) {
count[i] += count[i-1];
}
int sortArr[] = new int[a.length];
for (int i = 0; i < sortArr.length; i++) {
count[a[i]]--;
sortArr[count[a[i]]] = a[i];
}
return sortArr;
}
public static void main(String[] args) {
int[] a = {1,34,66,90,99,34,56,2,3,47,66,99};
int[] sortArr = countSort(a,100);
for (int i = 0; i < sortArr.length; i++) {
System.out.print(sortArr[i]+" ");
}
}
}
#include <time.h> #include <iostream> #include <iomanip> using namespace std; /*initial arr*/ void InitialArr(double *arr,int n) { srand((unsigned)time(NULL)); for (int i = 0; i<n;i++) { arr[i] = rand()/double(RAND_MAX+1); //(0.1) } } /* print arr*/ void PrintArr(double *arr,int n) { for (int i = 0;i < n; i++) { cout<<setw(15)<<arr[i]; if ((i+1)%5 == 0 || i == n-1) { cout<<endl; } } } void BucketSort(double * arr,int n) { double **bucket = new double*[10]; for (int i = 0;i<10;i++) { bucket[i] = new double[n]; } int count[10] = {0}; for (int i = 0 ; i < n ; i++) { double temp = arr[i]; int flag = (int)(arr[i]*10); //flag标识小树的第一位 bucket[flag][count[flag]] = temp; //用二维数组的每个向量来存放小树第一位相同的数据 int j = count[flag]++; /* 利用插入排序对每一行进行排序 */ for(;j > 0 && temp < bucket[flag][j - 1]; --j) { bucket[flag][j] = bucket[flag][j-1]; } bucket[flag][j] =temp; } /* 所有数据重新链接 */ int k=0; for (int i = 0 ; i < 10 ; i++) { for (int j = 0 ; j< count[i];j++) { arr[k] = bucket[i][j]; k++; } } for (int i = 0 ; i<10 ;i++) { delete bucket[i]; bucket[i] =NULL; } delete []bucket; bucket = NULL; } void main() { double *arr=new double[10]; InitialArr(arr, 10); BucketSort(arr, 10); PrintArr(arr,10); delete [] arr; }
基数排序
#include<stdio.h>
#define MAX 20
#define SHOWPASS
#define BASE 10
void print(int *a, int n) {
int i;
for (i = 0; i < n; i++) {
printf("%d\t", a[i]);
}
}
void radixsort(int *a, int n) {
int i, b[MAX], m = a[0], exp = 1;
//寻找最大位数的那个数
for (i = 1; i < n; i++) {
if (a[i] > m) {
m = a[i];
}
}
while (m / exp > 0) {
int bucket[BASE] = { 0 };
//进行计数排序
for (i = 0; i < n; i++) {
bucket[(a[i] / exp) % BASE]++;
}
for (i = 1; i < BASE; i++) {
bucket[i] += bucket[i - 1];
}
for (i = n - 1; i >= 0; i--) {
b[--bucket[(a[i] / exp) % BASE]] = a[i];
}
for (i = 0; i < n; i++) {
a[i] = b[i];
}
//计数排序结束
exp *= BASE;//进入下个位数
#ifdef SHOWPASS
printf("\nPASS : ");
print(a, n);
#endif
}
}
int main() {
int arr[MAX];
int i, n;
printf("Enter total elements (n <= %d) : ", MAX);
scanf("%d", &n);
n = n < MAX ? n : MAX;
printf("Enter %d Elements : ", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("\nARRAY : ");
print(&arr[0], n);
radixsort(&arr[0], n);
printf("\nSORTED : ");
print(&arr[0], n);
printf("\n");
return 0;
}基于非比较的排序：计数排序（countSort），桶排序（bucketSort），基数排序（radixSort）,布布扣,bubuko.com
基于非比较的排序：计数排序（countSort），桶排序（bucketSort），基数排序（radixSort）
原文：http://blog.csdn.net/dafeng_blog/article/details/24939955