C++ 基数排序的实现实例代码

C++ 基数排序

 大家好,今天带来的是自己实现的用C++完成基数排序.在数据结构,算法分析和程序设计的学习过程中,我们经常也无法避免的要学到排序的算法.排序算法是程序设计过程中使用频率极高的算法之一,其输入是一组无序的序列,要求以升序或者降序的方式输出一组有序的序列.对于如二分查找等算法,要求输入是有序的序列,也就是要先排序后查找,由此可见排序算法的重要性.

  广为人知的排序算法有冒泡排序,还有选择排序,插入排序.高级一些的有快速排序,希尔排序,堆排序,归并排序,基数排序等. 其中时间复杂度为O(n*logn)的算法有快速排序,归并排序和堆排序等,其中快速排序的使用最为广泛.时间复杂度为O(n2)的算法有冒泡排序,选择排序和插入排序等.

  基数排序是一种非比较的排序算法,它是以桶排序为基础的.它们在现代计算机出现之前,一直被用于老式穿孔卡的排序.

  基数排序的基本思想是:一共有10个"桶",代表各个数位为0~9.在每个桶上,组织一个优先队列,对于输入的一系列正整数和0,按照个位的大小关系分别进入10个"桶"中.然后遍历每个"桶",按照十位的大小关系进行调整,紧接着是百位,千位.......直到到达最大数的最大位数.结合图例,我们可以理解这个算法:

  在C++实现中,我用到了队列这一数据结构作为每个"桶"的组织方式,因为取数总是从最下方取,而放入数这是放入"桶"的顶部,这与队列的队头出对,队尾入队的方式相似.对10个"桶"的组织,则采用向量vector.这个程序支持,输入序列一定范围内不限个数,且在int数据类型表示范围内的非负数排序,根据最大数的位数来决定排序趟数.将数据类型从int改为long或者long long ,则可对更大的整数排序.

  排序函数如下:

 1 vector<int> radix_sort(vector<int> in)
 2 {
 3   vector<queue<int>> bucket(10);      //十个桶为一个向量,每个桶又是一个队列
 4   int max_value = in.at(0);
 5
 6   for (auto &i : in)
 7   {
 8     if ( i > max_value)
 9       max_value = i;
 10   }                               //找出输入的最大元素
 11
 12   int n = 0;
 13
 14   for (; max_value != 0; max_value /= 10, ++n)
 15     ;                             //得到最多位数,也即排序趟数
 16
 17   for (auto &i : in)
 18     bucket.at(0).push(i);               //全部放入第一个桶
 19
 20   int i = 0;                         //趟数控制变量
 21   int m = 0;                        //提取各个位数有关的控制变量
 22   int k = 0;                         //桶数控制变量
 23   int x = 0;                         //桶的大小,因动态改变了容器,迭代器会失效,不使用迭代器
 24   int y = 0;                         //桶内部控制变量
 25   int j = 0;
 26   int item = 0;                        //桶内元素
 27
 28   for (; i < n ; ++i)                    //趟数循环
 29   {
 30     for ( k = 0; k < 10 ; ++k)    //遍历每个桶
 31     {
 32       x = bucket.at(k).size();
 33
 34       if ( !x )
 35         continue;
 36
 37       for (y = 0; y < x ; ++y)                 //遍历桶中队列的元素
 38       {
 39         item = j = bucket.at(k).front();
 40
 41         for (m = i; m > 0; --m)               //提取出各个位
 42           j /= 10;
 43
 44         switch (j % 10)                   //进入相应的桶
 45         {
 46           case 0:
 47             bucket.at(0).push(item);
 48             break;
 49
 50           case 1:
 51             bucket.at(1).push(item);
 52             break;
 53
 54           case 2:
 55             bucket.at(2).push(item);
 56             break;
 57
 58           case 3:
 59             bucket.at(3).push(item);
 60             break;
 61
 62           case 4:
 63             bucket.at(4).push(item);
 64             break;
 65
 66           case 5:
 67             bucket.at(5).push(item);
 68             break;
 69
 70           case 6:
 71             bucket.at(6).push(item);
 72             break;
 73
 74           case 7:
 75             bucket.at(7).push(item);
 76             break;
 77
 78           case 8:
 79             bucket.at(8).push(item);
 80             break;
 81
 82           case 9:
 83             bucket.at(9).push(item);
 84             break;
 85
 86           default:                     //异常检测,捕捉与处理
 87             try
 88             {
 89               throw runtime_error("Error!");
 90             }
 91             catch (runtime_error err)
 92             {
 93               cout << err.what() << endl;
 94               exit(EXIT_FAILURE);
 95             }
 96         }
 97
 98         bucket.at(k).pop();
 99       }
100     }
101   }
102
103   vector<int> out;                        //定义一个新的向量,将所有桶的数据收集起来作为最后结果
104
105   for ( i = 0; i < 10; ++i )
106   {
107     int num = bucket.at(i).size();
108
109     for (int ai = 0; ai < num; ++ai)
110     {
111       out.push_back( bucket.at(i).front() );
112       bucket.at(i).pop();
113     }
114   }                                            //排序结果到一个向量中
115
116   return out;                         //返回这个有序的序列
117
118 }

算法要得到正确结果,要注意的是同一个桶的元素的顺序,是从下至上递增的,这是由遍历时从代表0的"桶"开始和从桶中取     元素时是从下取保证的.再有,最后从桶中取出元素时也要注意顺序.

时间: 2016-11-05

C++ 字符串去重排序实例代码

 C++ 字符串去重排序实例代码 入一个字符串,去掉重复出现的字符,并把剩余的字符串排序输出. 实现代码: #include <iostream> #include <string> using namespace std; void sort(string s) { char tmp[100]; int len=s.size(); int count=0,i,j; for (i=0;i<len;i++) { for (j=i+1;j<len;j++) { if (s[

C++中用栈来判断括号字符串匹配问题的实现方法

本文实例主要实现:输入一个括号字符串,依次检验,若为左括号则入栈,若为右括号则出栈一个字符判断是否与之相对应,在最后还需判断栈是否为空,如果不为空则不匹配. 首先回顾栈的基本知识: 1.定义栈的结构体并初始化一个新栈: struct stack { char strstack[stacksize]; int top; }; void InitStack(stack &s) { s.top=-1; } 2.出栈和入栈操作: char Push(stack &s,char a) { if(s.

C++基于栈实现铁轨问题

本文实例讲述了C++基于栈实现铁轨问题.分享给大家供大家参考.具体分析如下: 示例图如下所示: 经典栈问题!第一次做的时候思路太混乱了,现在看了刘汝佳的书,重新整理下. #include <stdio.h> #include <string.h> /****************************************************************** * 用数组A存储调整前的车厢号序列,用数组B存储调整好的车厢号序列 * 用栈stack存储存放在中转站

C++中实现队列类链式存储与栈类链式存储的代码示例

队列类链式存储 代码: linkqueue.hpp // 队列类 #pragma once #include "linklist.hpp" template <typename T> class LinkQueue { public: LinkQueue(); ~LinkQueue(); public: int clear(); int append(T &t); int retieve(T &t); int header(T &t); int le

C++中栈结构建立与操作详细解析

什么是栈结构 栈结构是从数据的运算来分类的,也就是说栈结构具有特殊的运算规则,即:后进先出. 我们可以把栈理解成一个大仓库,放在仓库门口(栈顶)的货物会优先被取出,然后再取出里面的货物. 而从数据的逻辑结构来看,栈结构起始就是一种线性结构. 如果从数据的存储结构来进一步划分,栈结构包括两类:顺序栈结构: 即使用一组地址连续的内存单元依次保存栈中的数据.在程序中,可以定义一个指定大小的结构数组来作为栈,序号为0的元素就是栈低,再定义一个变量top保存栈顶的序号即可.链式栈结构: 即使用链表的的形式

c/c++堆栈分布及其设置方法

一个由C/C++编译的程序占用的内存分为以下几个部分1.栈区(stack)- 由编译器自动分配释放 ,存放函数的参数名,局部变量的名等.其操作方式类似于数据结构中的栈.2.堆区(heap)- 由程序员分配释放, 若程序员不释放,程序结束时可能由OS回收.注意它与数据结构中的堆是两回事,分配方式倒是类似于链表.3.全局区(静态区)(static)-全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域, 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域.程序结束后由系统

C/C++函数调用栈的实现方法

本文实例讲述了C/C++函数调用栈的实现方法.可用于实现简单的脚本解释器.分享给大家供大家参考.具体实现方法如下: 头文件声明部分: 复制代码 代码如下: #pragma once const int BUFFERSIZE = 1024; const int growfactor = 2;   // this stack is used as call stack. class TStack{ private: size_t size;   // the stack length size_t

C++利用链栈实现表达式求值

本文实例为大家分享了C++利用链栈实现表达式求值的具体代码,供大家参考,具体内容如下 #include<iostream.h> typedef int Status; typedef char Cstack; #define OK 1 #define ERROR 0 typedef struct StackNode { Cstack data; struct StackNode *next; }StackNode,*LinkStack; Status InitStack(LinkStack &

用C++实现一个链式栈的实例代码

自定义一个链式栈,c++语言实现,不足之处,还望指正! 复制代码 代码如下: // MyStack.cpp : 定义控制台应用程序的入口点.//自己构造一个链式栈,具有push(入栈),pop(出栈),top(取得栈顶元素),size(返回栈大小),empty(判断是否为空)等功能#include "stdafx.h"#include <iostream>using namespace std;//构造栈的节点template <class T>struct N

C++实现单链表按k值重新排序的方法

本文实例讲述了C++实现单链表按k值重新排序的方法.分享给大家供大家参考,具体如下: 题目要求: 给定一链表头节点,节点值类型是整型. 现给一整数k,根据k将链表排序为小于k,等于k,大于k的一个链表. 对某部分内的节点顺序不做要求. 算法思路分析及代码(C) 思路:将链表分为小于k.等于k.大于k的三个链表,然后再合并. 链表结点定义: typedef struct Node { int data; struct Node* next; }node, *pNode; 算法代码: pNode s

C++使用一个栈实现另一个栈的排序算法示例

本文实例讲述了C++用一个栈实现另一个栈的排序算法.分享给大家供大家参考,具体如下: 题目: 一个栈中元素类型为整型,现在想将该栈从顶到底按从小到大的顺序排序,只许申请一个辅助栈. 除此之外,可以申请新的变量,但不能申请额外的数据结构.如何完成排序? 算法C++代码: class Solution { public: //借助一个临时栈排序源栈 static void sortStackByStack(stack<int>& s) { stack<int>* sTemp =

C++使用递归函数和栈操作逆序一个栈的算法示例

本文实例讲述了C++使用递归函数和栈操作逆序一个栈的算法.分享给大家供大家参考,具体如下: 题目: 一个栈依次压入1.2.3.4.5,那么栈顶到栈底分别为:5.4.3.2.1. 将这个栈逆置后栈顶到栈底分别为1.2.3.4.5. 用递归函数来实现,不能用其他数据结构. 解题思路及代码 1.递归函数一:将栈的栈底元素一个个返回并移除. 2.递归函数二:逆序栈,调用递归函数一实现. C++实现: class Solution { public: //递归函数一 static int getAndRe

JS使用栈判断给定字符串是否是回文算法示例

本文实例讲述了JS使用栈判断给定字符串是否是回文算法.分享给大家供大家参考,具体如下: /*使用栈stack类的实现*/ function stack() { this.dataStore = [];//保存栈内元素,初始化为一个空数组 this.top = 0;//栈顶位置,初始化为0 this.push = push;//入栈 this.pop = pop;//出栈 this.peek = peek;//查看栈顶元素 this.clear = clear;//清空栈 this.length

JS栈stack类的实现与使用方法示例

本文实例讲述了JS栈stack类的实现与使用方法.分享给大家供大家参考,具体如下: 栈是一种"先进后出"的数据结构,原理如下图所示: 示例代码: /*使用栈stack类的实现*/ function stack() { this.dataStore = [];//保存栈内元素,初始化为一个空数组 this.top = 0;//栈顶位置,初始化为0 this.push = push;//入栈 this.pop = pop;//出栈 this.peek = peek;//查看栈顶元素 thi

一个非常不错的一个正则练习JS版

技术含量不高,主要是平时使用正则多了,在代码上调试太麻烦了,干脆做这个来试比较快~~~送给那些喜欢正则的朋友~~~ 做得头晕脑涨,实在找不出几个正则例子来给新手学习,所以现在俺里面的帮助文件里面也才三个例子而以! 由于本人的语言表达实在不怎么样,而以材料一个人制作麻烦,希望有热心人士提供经典的正则例子,最好附上详解,以便新手学习! 无殇 - 正则练习器 window.onerror=function(a,b,c){alert("发生未知错误:"+a+"\n第"+c+

VC实现五子棋游戏的一个算法示例

本文讲述了VC实现五子棋游戏的一个算法示例,该算法采用极大极小剪枝博弈算法,感兴趣的读者可以对程序中不完善的部分进行修改与完善. 该设计主要包括:数据结构.估值函数.胜负判断.搜索算法 程序运行界面如下: 具体实现步骤如下: 1.数据结构 //记录每步棋,可以建立链表用来进行悔棋.后退(本程序没有实现) struct Step { int x,y; //棋子坐标 int ball; //表示下子方{BLACK,WHITE} }; //记录棋盘情况,用于搜索过程 class CBoardSitua

js判断一个字符串是否包含一个子串的方法

本文实例讲述了js判断一个字符串是否包含一个子串的方法.分享给大家供大家参考.具体如下: 在我们前端日常开发中,经常会遇到判断一个字符串中是否包含某个子串,这里我们将去探究一些解决此种需求的方法以及正确的使用它们.理想情况下,我们要找的是一个能匹配我们的目的(if x contains y)的方法,并返回true或false. 一.String.prototype.indexOf和String.prototype.lastIndexOf 这两个方法,可能是我们最容易想到的,如果包含子串,则返回大

mysql用一个表更新另一个表的方法

Solution 1:  修改1列 update student s, city c set s.city_name = c.name where s.city_code = c.code; Solution 2:  修改多个列 update  a,  b set a.title=b.title, a.name=b.name where a.id=b.id Solution 3: 采用子查询 update student s set city_name = (select name from c

如何判断出一个js对象是否一个dom对象

我们在写js代码时有时需要判断某个对象是不是DOM对象,然后再进行后续的操作,这里我给出一种兼容各大浏览器,同时又算是比较稳妥的一种方法. 要判断一个对象是否DOM对象,首先想到的无非就是它是否具有DOM对象的各种属性或特征,比如是否有nodeType属性,有tagName属性,等等.判断的特征越多,也就越可靠,因为毕竟我们自定义的js对象也可以有那些属性.还有其他方法吗? 在DOM Level2标准中定义了一个HTMLElement对象,它规定所有的DOM对象都是HTMLElement的实例,

使用jquery判断一个元素是否含有一个指定的类(class)实例

在jquery中可以使用2种方法来判断一个元素是否包含一个确定的类(class).两种方法有着相同的功能. 2 种方法如下: 1. is('.classname') 2. hasClass('classname') 以下是一个div元素是否包含一个redColor的例子: 1. 使用is('.classname')的方法 $('div').is('.redColor') 2. 使用hasClass('classname')的方法(注意jquery的低版本可能是hasClass('.classna