`
chiyx
  • 浏览: 274831 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

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

阅读更多
基数排序:
#include <stdlib.h> 
#include "algosort.h"
/*被排序元素的最大位数,4则意味着只能排序< 10000 的数*/
#define WIDTH 4 
#define MAXK 10  //位数划分基于的基数,10表示为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);
}

/*
*获取一个数第d位数的值,位数索引从0开始
*/
int getDValue(int value, int d) {
	for (;d > 0 && value > 0; d--) {
		value = value / MAXK;
	}
	return value % MAXK;
}
分享到:
评论

相关推荐

    各种常用排序算法的C语言实现

    本资源提供了各种常用排序算法的C语言实现,源自严蔚敏的经典教材《数据结构》。下面将详细介绍这些排序算法及其在C语言中的实现原理。 1. 冒泡排序(Bubble Sort) 冒泡排序是最基础的排序方法,通过不断交换相邻...

    常用排序算法C语言实现.zip

    本压缩包“常用排序算法C语言实现.zip”包含了多种经典的排序算法用C语言编写的源代码,这对于我们理解和实践这些算法非常有帮助。下面将详细解释其中可能包含的一些常见排序算法。 1. 冒泡排序(Bubble Sort) ...

    浅析基于C语言的常用排序算法比较.pdf

    插入排序算法同样是基于C语言的一种常用排序算法。插入排序的基本思想是:把待排序的序列分为已排序和未排序两部分,每次将一个未排序的元素,按照其大小插入到已排序序列中的适当位置,直到所有元素都被插入。插入...

    常用排序算法C语言示例代码解说PDF

    个人原创总结的常用排序算法C语言示例代码解说PDF,可以动态输出排序过程,以便理解排序算法的主旨思想。包含有直接插入排序,折半插入排序,2路直接插入排序,起泡排序,简单选择排序,快速排序,堆排序,(希尔排序,归并...

    8大常用排序算法实现

    本文将详细解析八大常用排序算法的实现,帮助你更好地理解和测试这些算法。 1. 冒泡排序(Bubble Sort): 冒泡排序是一种简单的交换排序,通过不断比较相邻元素并交换,使得每次遍历都将最大(或最小)的元素“冒...

    常用算法程序集(C语言描述)第三版源代码

    《常用算法程序集(C语言描述)第三版源代码》是一个专门为C语言学习者和开发者提供的资源,包含了大量的经典算法实现。这个集合旨在帮助程序员深入理解各种基础和高级算法,提高编程技能,以及解决实际问题的能力。...

    基于C语言的常用排序算法设计实现

    本项目聚焦于使用C语言实现常见的排序算法,包括冒泡排序、插入排序、归并排序、快速排序、计数排序和基数排序。下面将详细介绍这些排序算法的原理、实现方式以及在C语言中的应用。 1. **冒泡排序**: 冒泡排序是...

    C语言数据结构内部排序算法及比较

    在计算机科学领域,数据结构和排序算法是编程基础的重要组成部分,特别是对于C语言这样底层而强大的编程工具。本文将深入探讨“C语言数据结构内部排序算法及比较”这一主题,结合个人课程作业的经验,对一些核心概念...

    常用算法源码C语言版.zip

    基数排序算法.zip 堆排序算法.zip 多维矩阵转一维矩阵.zip 大数运算.zip 完全二叉树算法.zip 完美数.zip 宽度优先搜索.zip 对称矩阵.zip 对角矩阵.zip 左倾堆.zip 布隆过滤器.zip 希尔排序算法.zip 平衡二叉树算法....

    常用排序算法的C语言版实现示例整理

    基本的排序算法有如下几种:交换排序(冒泡排序、快速排序)、选择排序(直接选择排序、堆排序)、插入排序(直接插入排序、希尔排序)、归并排序、分配排序(基数排序、箱排序、计数排序)。下面依次列出各种算法的...

    基数排序 数据结构 c语言

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。这种排序方法适用于大量...以上就是关于基数排序及其在C语言中实现的详细知识,希望对你理解基数排序有所帮助。

    深入浅出-C语言8种经典排序算法

    "深入浅出-C语言8种经典排序算法" 本文将深入浅出地介绍 C 语言中的 8 种经典排序算法,包括冒泡排序、选择排序、插入排序、快速排序、归并排序、基数排序、希尔排序和堆排序。这些算法都是在程序设计中常用的排序...

    常用的内部排序---源码

    本资源提供的“常用的内部排序---源码”包含了C语言实现的一些经典排序算法,这对于学习和理解这些算法的工作原理非常有帮助。 1. **冒泡排序**:冒泡排序是最简单的排序算法之一,通过不断交换相邻的错误位置元素...

    C语言的一些常用算法

    此外,还有**排序算法**,如**选择排序(Selection Sort)、插入排序(Insertion Sort)、冒泡排序(Bubble Sort)**等,它们都是基础的排序方法,虽然效率相对较低,但在理解和实现上较为简单。**Shell排序、Shaker...

    许士良常用算法程序集C语言

    《许士良常用算法程序集C语言》是一个包含C/C++语言实现的算法集合,旨在帮助程序员理解和掌握各种基础及进阶的算法。这个程序集是许士良先生的智慧结晶,提供了丰富的代码示例,涵盖了数据结构、排序、搜索等核心...

    精选_毕业设计_基于C语言的八大排序算法的比较_完整源码

    本项目聚焦于C语言实现的八大排序算法,通过对比分析,有助于深入理解每种算法的工作原理、效率以及适用场景。 一、八大排序算法概述 1. 冒泡排序(Bubble Sort):通过不断交换相邻的逆序元素,逐步将较大的元素...

    常用算法程序集(C语言描述) (第三版)

    《常用算法程序集(C语言描述)(第三版)》是一部深入探讨算法的宝贵资源,专为编程爱好者和IT专业人士打造。此书以其全面且深入的C语言实现,揭示了算法设计与分析的核心原理,旨在提升读者在算法理解与应用上的...

    常用排序算法复杂度总结

    包含排序类型有以下几种:插入排序,交换排序,选择排序,归并排序,基数排序

    C常用用算法程序集(C语言描述)+(第三版)

    《C常用算法程序集(C语言描述)+(第三版)》是一本专注于C语言实现常见算法的书籍,旨在帮助读者深入理解并掌握算法在实际编程中的应用。这本书的第三版可能包含了更多更新的内容和优化的算法实现,以适应不断发展...

    C语言常用排序方法大全.rar

    "C语言常用排序方法大全.rar"这个压缩包文件很可能是为了收集并演示C语言中实现的各种排序算法。 1. **冒泡排序**: 冒泡排序是最基础的排序算法,通过不断地交换相邻两个元素的位置,使较大的元素逐渐“冒”到...

Global site tag (gtag.js) - Google Analytics