论坛首页 编程语言技术论坛

常用排序算法的实现(C语言版)-基数排序

浏览 3496 次
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2012-08-01  
基数排序:
#include <stdlib.h> 
#include "algosort.h"
/*被排序元素的最大位数,4则意味着只能排序< 10000 的数*/
#define WIDTH 4 
#define MAXK 10 

void radixSort(int a[], int n) {
	int i;
	void innerCountingSort(int a[], int n, int d);
	for (i = 0; i < WIDTH; i++) {
		innerCountingSort(a, n, i);
	}
}

void innerCountingSort(int a[], int n, int d) {
	int i, j, x, k[MAXK] = {0};
	int *ip = (int *)malloc(n * sizeof(int));
	int *bp = (int *)malloc(n * sizeof(int));
	int getDValue(int value, int d);
	for (i = 0; i < n; i++) {
		ip[i] = getDValue(a[i], d);
		k[ip[i]]++;
	}

	for (j = 1; j < MAXK; j++) {
		k[j] = k[j] + k[j-1];
	}

	for (i = n - 1; i >= 0; i--) {
		bp[k[ip[i]] - 1] = a[i];
		k[ip[i]]--;
	}

	for (i = 0; i < n; i++) {
		a[i] = bp[i];
	}

	free(ip);
	free(bp);
}

int getDValue(int value, int d) {
	for (;d > 0 && value > 0; d--) {
		value = value / MAXK;
	}
	return value % MAXK;
}
论坛首页 编程语言技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics