基数排序-八大排序汇总(8)

基数排序的性能

排序类别 排序方法 时间复杂度 空间复杂度 稳定性 复杂性
平均情况 最坏情况 最好情况
基数排序 基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(n+r) 稳定 较复杂

时间复杂度:假设在基数排序中,r为基数,d为位数。则基数排序的时间复杂度为O(d(n+r))。可以看出,基数排序的效率和初始序列是否有序没有关联。

空间复杂度:基数排序过程中,对于任何位数上的基数进行“装桶”操作时,都需要n+r个临时空间。

算法稳定性:基数排序过程中,每次都是将当前位数上相同数值的元素统一“装桶”,并不需要交换位置。所以基数排序是稳定的算法。

代码及分析

以LSD为例,假设原来有一串数值如下所示:

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

首先根据个位数的数值,在走访数值时将它们分配至编号0到9的桶子中:

0

1 81

2 22

3 73 93 43

4 14

5 55 65

6

7

8 28

9 39

接下来将这些桶子中的数值重新串接起来,成为以下的数列:

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接着再进行一次分配,这次是根据十位数来分配:

0

1 14

2 22 28

3 39

4 43

5 55

6 65

7 73

8 81

9 93

接下来将这些桶子中的数值重新串接起来,成为以下的数列:

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

  

  这时候整个数列已经排序完毕;如果排序的对象有三位数以上,则持续进行以上的动作直至最高位数为止。

  LSD的基数排序适用于位数小的数列,如果位数多的话,使用MSD的效率会比较好。MSD的方式与LSD相反,是由高位数为基底开始进行分配,但在分配之后并不马上合并回一个数组中,而是在每个“桶子”中建立“子桶”,将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。

代码:

  1 #include "stdafx.h"
  2 #include <iostream>
  3 #include <math.h>
  4 using namespace std;
  5
  6 //查询数组中的最大数
  7 int findMaxNum(int *p, int n)
  8 {
  9     int i;
 10     int max = 0;
 11     for (i = 0; i < n; i++)
 12     {
 13         if (*(p + i) > max)
 14         {
 15             max = *(p + i);
 16         }
 17     }
 18     return max;
 19 }
 20 //获取数字的位数
 21 int getLoopTimes(int num)
 22 {
 23     int count = 1;
 24     int temp = num / 10;
 25     while (temp != 0)
 26     {
 27         count++;
 28         temp = temp / 10;
 29     }
 30     return count;
 31 }
 32
 33 //将数字分配到各自的桶中,然后按照桶的顺序输出排序结果
 34 void sort2(int *p, int n, int loop)
 35 {
 36     //建立一组桶此处的20是预设的根据实际数情况修改
 37     int buckets[10][20] = {};
 38     //求桶的index的除数
 39     //如798个位桶index=(798/1)%10=8
 40     //十位桶index=(798/10)%10=9
 41     //百位桶index=(798/100)%10=7
 42     //tempNum为上式中的1、10、100
 43     int tempNum = (int)pow(10, loop - 1);
 44     int i, j;
 45     for (i = 0; i < n; i++)
 46     {
 47         int row_index = (*(p + i) / tempNum) % 10;
 48         for (j = 0; j < 20; j++)
 49         {
 50             if (buckets[row_index][j] == NULL)
 51             {
 52                 buckets[row_index][j] = *(p + i);
 53                 break;
 54             }
 55         }
 56     }
 57     //将桶中的数,倒回到原有数组中
 58     int k = 0;
 59     for (i = 0; i < 10; i++)
 60     {
 61         for (j = 0; j < 20; j++)
 62         {
 63             if (buckets[i][j] != NULL)
 64             {
 65                 *(p + k) = buckets[i][j];
 66                 buckets[i][j] = NULL;
 67                 k++;
 68             }
 69         }
 70     }
 71 }
 72
 73 //基数排序
 74 void bucketSort3(int *p, int n)
 75 {
 76     //获取数组中的最大数
 77     int maxNum = findMaxNum(p, n);
 78     //获取最大数的位数,次数也是再分配的次数。
 79     int loopTimes = getLoopTimes(maxNum);
 80     int i;
 81     //对每一位进行桶分配
 82     for (i = 1; i <= loopTimes; i++)
 83     {
 84         sort2(p, n, i);
 85     }
 86 }
 87 void testBS()
 88 {
 89     int a[] = { 2, 343, 342, 1, 123, 43, 4343, 433, 687, 654, 3 };
 90     int *a_p = a;
 91     //计算数组长度
 92     int size = sizeof(a) / sizeof(int);
 93     //基数排序
 94     bucketSort3(a_p, size);
 95     //打印排序后结果
 96     int i;
 97     for (i = 0; i < size; i++)
 98     {
 99         printf("%d\n", a[i]);
100     }
101 }
102
103 int _tmain(int argc, _TCHAR* argv[])
104 {
105     testBS();
106
107     system("pause");
108     return 0;
109 }

关于基数排序性能优化一篇非常牛的文章

http://blog.csdn.net/yutianzuijin/article/details/22876017

时间: 10-02

基数排序-八大排序汇总(8)的相关文章

八大排序算法

转载:http://blog.csdn.net/hguisu/article/details/7776068 目录(?)[+] 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速

谈谈八大排序算法问题

排序算法可以说是算法的入门以及算法学习阶段的基石,排序算法显得那么的基础又是非常重要的一种算法.排序算法常常作为一些高阶算法的数据处理中间过程在实际的问题处理中被应用的最为广泛,因此算法选将阶段就从八大排序算法开始.在本节内容中既可以看到一般性的比如插入排序,冒泡排序等基础算法又可以看到比如基数排序,位图排序,快速排序等等比较难理解的算法,算法之门从排序算法说起. 1.插入排序 插入排序算法的原理很简单,默认A中有一部分数据已经排好序了,后续只要从没有排好序的序列里面每拿出一个数字就在排好序的序

数据结构与算法之——八大排序算法

附:关于这个主题,网上好的文章已经数不胜数,本篇是整合后的文章. 正文: 一.概述 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 本文所指八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短: 二.排序算法详述 1.

八大排序算法总结及C/C++实现

概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短: 1. 插入排序-直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到

[Data Structure] 八大排序算法

排序有内部排序和外部排序之分,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存.我们这里说的八大排序算法均为内部排序. 下图为排序算法体系结构图: 1. 直接插入排序(Straight Insertion Sort ) 基本思想:将待排序的无序数列看成是一个仅含有一个元素的有序数列和一个无序数列,将无序数列中的元素逐次插入到有序数列中,从而获得最终的有序数列. 算法流程: 1)初始时, a[0]自成一个有序区, 无序区为a[1

(转)详解八大排序算法

概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短: 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到

Python学习(三) 八大排序算法的实现(下)

本文Python实现了插入排序.基数排序.希尔排序.冒泡排序.高速排序.直接选择排序.堆排序.归并排序的后面四种. 上篇:Python学习(三) 八大排序算法的实现(上) 1.高速排序 描写叙述 通过一趟排序将要排序的数据切割成独立的两部分,当中一部分的全部数据都比另外一部分的全部数据都要小,然后再按此方法对这两部分数据分别进行高速排序,整个排序过程能够递归进行,以此达到整个数据变成有序序列. 1.先从数列中取出一个数作为基准数. 2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全

八大排序算法Java(转)

目录(?)[-] 概述 插入排序直接插入排序Straight Insertion Sort 插入排序希尔排序Shells Sort 选择排序简单选择排序Simple Selection Sort 选择排序堆排序Heap Sort 交换排序冒泡排序Bubble Sort 交换排序快速排序Quick Sort 归并排序Merge Sort 桶排序基数排序Radix Sort 总结 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序

(转)八大排序对比

排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短: 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已排序