版本记录

前言

排序算法是最常见的算法，其中包括了冒泡、选择等很多不同的排序算法，接下来几篇就会介绍相应的排序算法，其实前面几篇已经有所涉及了，以后有些东西我会慢慢移动和增加到这个专题里面。感兴趣的看下面几篇文章。
1. 排序算法（一） —— 堆排序之一个简单示例（一）

简介

以下部分内容来自百度

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

实现方法

最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。

最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。

在本章中，您将看到一个完全不同的排序模型。 到目前为止，您一直依靠比较来确定排序顺序。 基数排序（Radix sort）是一种非比较算法，用于在线性时间内对整数进行排序。

基数排序的多种实现关注于不同的问题。 为了简单起见，在本文中，您将专注于在调查基数排序的最低有效位（least significant digit - LSD）变体时对基数10整数进行排序。

Example - 示例

为了展示基数排序的原理，你首先看一下下面这个数组：

var array = [88, 410, 1772, 20]

基数排序依赖于整数的位置表示法，如下所示：

首先，根据最低有效数字的值将数组分成桶：ones digit。

然后按顺序清空这些存储桶，从而产生以下部分排序的数组：

array = [410, 20, 1772, 88]

接下来，对十位数重复此过程：

这次元素的相对顺序没有改变，但你仍然有更多的数字要检查。

要考虑的下一个数字是百位：

对于没有百位的值(或没有值的任何其他位置)，数字将被假设为零。

基于这些桶重新组装数组得到如下结果:

array = [20, 88, 410, 1772]

最后你需要考虑千位

从这些桶中重新组合数组，得到最终的排序数组:

array = [20, 88, 410, 1772]

当多个数字最终出现在同一个桶中时，它们的相对顺序不会改变。例如，在百位的零桶中，20在88之前。这是因为前面的步骤将20放在比80小的桶中，所以20在数组中在88之前结束。

Implementation - 实现

在Sources目录中，创建一个名为RadixSort.swift的新文件。向文件中添加以下内容:

extension Array where Element == Int {

  public mutating func radixSort() {

  }
}

在这里，您已经通过扩展向整数数组添加了一个radixSort方法。下面实现radixSort方法:

public mutating func radixSort() {
  // 1
  let base = 10
  // 2
  var done = false
  var digits = 1
  while !done {
  
  }
}

• 1）在这个实例中，以10个整数为基数进行排序。因为在算法中将多次使用这个值，所以将其存储在一个常量base中。
• 2）您声明两个变量来跟踪您的进度。基数排序在多个遍历中工作，因此done充当一个标志，用于确定排序是否完成。digits变量会跟踪当前的数字。

接下来，您将编写将每个元素排序为Bucket(也称为Bucket sort)的逻辑。

1. Bucket Sort

在while循环中添加如下代码：

// 1
var buckets: [[Int]] = .init(repeating: [], count: base)
// 2
forEach {
  number in
  let remainingPart = number / digits
  let digit = remainingPart % base
  buckets[digit].append(number)
}
// 3
digits *= base
self = buckets.flatMap { $0 }

下面进行详细分解：

• 1）使用二维数组实例化桶。因为是以10为底，所以需要10个桶。
• 2）将每个数字放入正确的桶中。
• 3）将digits更新到下一个要检查的数字，并使用bucket的内容更新数组。flatMap会将二维数组压平为一维数组，就像你清空桶倒进数组一样。

2. When Do You Stop? - 何时停止

您的while循环当前会永远运行，因此您需要在某个地方设置一个终止条件。您将这样做:

• 1）在while循环的开头，添加done = true。
• 2）在forEach闭包中添加以下内容:

if remainingPart > 0 {
  done = false
}

因为forEach遍历所有整数，只要其中一个整数仍然有未排序的数字，就需要继续排序。

至此，您已经了解了您的第一个非比较排序算法！回到playground页面，写下面的测试你的代码:

example(of: "radix sort") {
  var array = [88, 410, 1772, 20]
  print("Original array: \(array)")
  array.radixSort()
  print("Radix sorted: \(array)")
}

下面看一下输出结果

---Example of: radix sort---
Original: [88, 410, 1772, 20]
Radix sorted: [20, 88, 410, 1772]

基数排序是最快的排序算法之一。基数排序的平均时间复杂度是O(k×n)，k是有效数字的数量最大的数字，n是整数数组中元素个数。

当k为常数时，基数排序效果最好，当数组中所有数字的有效位数相同时，基数排序就会发生。它的时间复杂度是O(n)，基数排序还会带来O(n)空间复杂性，因为存储每个桶需要空间。

源码

下面一起看一下源码。

1. Swift

1. Radix Sort.swift

extension Array where Element == Int {
  
  public mutating func radixSort() {
    let base = 10
    var done = false
    var digits = 1
    while !done {
      done = true
      var buckets: [[Int]] = .init(repeating: [], count: base)
      forEach {
        number in
        let remainingPart = number / digits
        let digit = remainingPart % base
        buckets[digit].append(number)
        if remainingPart > 0 {
          done = false
        }
      }
      digits *= base
      self = buckets.flatMap { $0 }
    }
  }
}

2. Helper

public func example(of description: String, action: () -> Void) {
  print("---Example of: \(description)---")
  action()
  print()
}

//测试代码
example(of: "radix sort") {
  var array = [88, 410, 1772, 20]
  print("Original array: \(array)")
  array.radixSort()
  print("Radix sorted: \(array)")
}

//输出结果
---Example of: radix sort---
Original array: [88, 410, 1772, 20]
Radix sorted: [20, 88, 410, 1772]

2. C

#include<math.h>
testBS()
{
    inta[] = {2, 343, 342, 1, 123, 43, 4343, 433, 687, 654, 3};
    int *a_p = a;
    //计算数组长度
    intsize = sizeof(a) / sizeof(int);
    //基数排序
    bucketSort3(a_p, size);
    //打印排序后结果
    inti;
    for(i = 0; i < size; i++)
    {
        printf("%d\n", a[i]);
    }
    intt;
    scanf("%d", t);
}
//基数排序
voidbucketSort3(int *p, intn)
{
    //获取数组中的最大数
    intmaxNum = findMaxNum(p, n);
    //获取最大数的位数，次数也是再分配的次数。
    intloopTimes = getLoopTimes(maxNum);
    inti;
    //对每一位进行桶分配
    for(i = 1; i <= loopTimes; i++)
    {
        sort2(p, n, i);
    }
}
//获取数字的位数
intgetLoopTimes(intnum)
{
    intcount = 1;
    inttemp = num / 10;
    while(temp != 0)
    {
        count++;
        temp = temp / 10;
    }
    returncount;
}
//查询数组中的最大数
intfindMaxNum(int *p, intn)
{
    inti;
    intmax = 0;
    for(i = 0; i < n; i++)
    {
        if(*(p + i) > max)
        {
            max = *(p + i);
        }
    }
    returnmax;
}
//将数字分配到各自的桶中，然后按照桶的顺序输出排序结果
voidsort2(int *p, intn, intloop)
{
    //建立一组桶此处的20是预设的根据实际数情况修改
    intbuckets[10][20] = {};
    //求桶的index的除数
    //如798个位桶index=(798/1)%10=8
    //十位桶index=(798/10)%10=9
    //百位桶index=(798/100)%10=7
    //tempNum为上式中的1、10、100
    inttempNum = (int)pow(10, loop - 1);
    inti, j;
    for(i = 0; i < n; i++)
    {
        introw_index = (*(p + i) / tempNum) % 10;
        for(j = 0; j < 20; j++)
        {
            if(buckets[row_index][j] == NULL)
            {
                buckets[row_index][j] = *(p + i);
                break;
            }
        }
    }
    //将桶中的数，倒回到原有数组中
    intk = 0;
    for(i = 0; i < 10; i++)
    {
        for(j = 0; j < 20; j++)
        {
            if(buckets[i][j] != NULL)
            {
                *(p + k) = buckets[i][j];
                buckets[i][j] = NULL;
                k++;
            }
        }
    }
}

3. Java

public class RadixSort
{
    public static void sort(int[] number, int d) //d表示最大的数有多少位
    {
        intk = 0;
        intn = 1;
        intm = 1; //控制键值排序依据在哪一位
        int[][]temp = newint[10][number.length]; //数组的第一维表示可能的余数0-9
        int[]order = newint[10]; //数组orderp[i]用来表示该位是i的数的个数
        while(m <= d)
        {
            for(inti = 0; i < number.length; i++)
            {
                intlsd = ((number[i] / n) % 10);
                temp[lsd][order[lsd]] = number[i];
                order[lsd]++;
            }
            for(inti = 0; i < 10; i++)
            {
                if(order[i] != 0)
                    for(intj = 0; j < order[i]; j++)
                    {
                        number[k] = temp[i][j];
                        k++;
                    }
                order[i] = 0;
            }
            n *= 10;
            k = 0;
            m++;
        }
    }
    public static void main(String[] args)
    {
        int[]data =
        {73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100};
        RadixSort.sort(data, 3);
        for(inti = 0; i < data.length; i++)
        {
            System.out.print(data[i] + "");
        }
    }
}

4. pascal

type link=^node;
node=record
data:integer;
next:link;
end;
var
i,j,l,m,k,n:integer;
a:array[1..100] of integer;
s:string;
q,head:array[0..9] of link;
p,p1:link;
begin
readln(n);
writeln('Enterdata:');
for i:=1 to n do read(a[i]);
for i:=5 downto 1 do
begin
for j:=0 to 9 do
begin
new(head[j]);
head[j]^.next:=nil;
q[j]:=head[j]
end;
for j:=1 to n do
begin
str(a[j],s);
for k:=1 to 5-length(s) do
s:='0'+s;
m:=ord(s[i])-48;
new(p);
p^.data:=a[j];
p^.next:=nil;
q[m]^.next:=p;
q[m]:=p;
end;
l:=0;
for j:=0 to 9 do
begin
p:=head[j];
while p^.next<>nil do
begin
l:=l+1;
p1:=p;
p:=p^.next;
dispose(p1);
a[l]:=p^.data;
end;
end;
end;
writeln('Sorteddata:');
for i:=1 to n do
write(a[i]:6);
end.

5. c++

int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{
    int d = 1; //保存最大的位数
    int p = 10;
    for(int i = 0; i < n; ++i)
    {
        while(data[i] >= p)
        {
            p *= 10;
            ++d;
        }
    }
    return d;
}
void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n);
    int *tmp = newint[n];
    int *count = newint[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete[]tmp;
    delete[]count;
}

6. C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LearnSort
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = CreateRandomArray(10); //产生随机数组
            Print(arr);//输出数组
            RadixSort(refarr);//排序
            Print(arr);//输出排序后的结果
            Console.ReadKey();
        }
        public static void RadixSort(ref int[] arr)
        {
            int iMaxLength = GetMaxLength(arr);
            RadixSort(ref arr, iMaxLength);
        }
        //排序
        private static void RadixSort(ref int[] arr, int iMaxLength)
        {
            List<int> list = newList<int>(); //存放每次排序后的元素
            List<int>[] listArr = newList<int>[10]; //十个桶
            char currnetChar;//存放当前的字符比如说某个元素123中的2
            string currentItem;//存放当前的元素比如说某个元素123
            for(int i = 0; i < listArr.Length; i++) //给十个桶分配内存初始化。
                listArr[i] = newList<int>();
            for(int i = 0; i < iMaxLength; i++) //一共执行iMaxLength次，iMaxLength是元素的最大位数。
            {
                foreach(int number in arr)//分桶
                {
                    currentItem = number.ToString(); //将当前元素转化成字符串
                    try
                    {
                        currnetChar = currentItem[currentItem.Length - i - 1];   //从个位向高位开始分桶
                    }
                    catch
                    {
                        listArr[0].Add(number);    //如果发生异常，则将该数压入listArr[0]。比如说5是没有十位数的，执行上面的操作肯定会发生越界异常的，这正是期望的行为，我们认为5的十位数是0，所以将它压入listArr[0]的桶里。
                        continue;
                    }
                    switch(currnetChar)//通过currnetChar的值，确定它压人哪个桶中。
                    {
                    case'0':
                        listArr[0].Add(number);
                        break;
                    case'1':
                        listArr[1].Add(number);
                        break;
                    case'2':
                        listArr[2].Add(number);
                        break;
                    case'3':
                        listArr[3].Add(number);
                        break;
                    case'4':
                        listArr[4].Add(number);
                        break;
                    case'5':
                        listArr[5].Add(number);
                        break;
                    case'6':
                        listArr[6].Add(number);
                        break;
                    case'7':
                        listArr[7].Add(number);
                        break;
                    case'8':
                        listArr[8].Add(number);
                        break;
                    case'9':
                        listArr[9].Add(number);
                        break;
                    default:
                        throw new Exception("unknowerror");
                    }
                }
                for(int j = 0; j < listArr.Length; j++) //将十个桶里的数据重新排列，压入list
                    foreach(int number in listArr[j].ToArray<int>())
                    {
                        list.Add(number);
                        listArr[j].Clear();//清空每个桶
                    }
                arr = list.ToArray<int>(); //arr指向重新排列的元素
                //Console.Write("{0}times:",i);
                Print(arr);//输出一次排列的结果
                list.Clear();//清空list
            }
        }
        //得到最大元素的位数
        private static int GetMaxLength(int[] arr)
        {
            int iMaxNumber = Int32.MinValue;
            foreach(int i in arr)//遍历得到最大值
            {
                if(i > iMaxNumber)
                    iMaxNumber = i;
            }
            return iMaxNumber.ToString().Length;//这样获得最大元素的位数是不是有点投机取巧了...
        }
        //输出数组元素
        public static void Print(int[] arr)
        {
            foreach(intiinarr)
                System.Console.Write(i.ToString() + '\t');
            System.Console.WriteLine();
        }
        //产生随机数组。随机数的范围是0到1000。参数iLength指产生多少个随机数
        public static int[] CreateRandomArray(int iLength)
        {
            int[] arr = new int[iLength];
            Random random = new Random();
            for(inti = 0; i < iLength; i++)
                arr[i] = random.Next(0, 1001);
            return arr;
        }
    }
}

7. python

#!/usr/bin/env python
#encoding=utf-8
 
import math
 
def sort(a, radix=10):
    """a为整数列表， radix为基数"""
    K = int(math.ceil(math.log(max(a), radix))) # 用K位数可表示任意整数
    bucket = [[] for i in range(radix)] # 不能用 [[]]*radix
    for i in range(1, K+1): # K次循环
        for val in a:
            bucket[val%(radix**i)/(radix**(i-1))].append(val) # 析取整数第K位数字 （从低到高）
        del a[:]
        for each in bucket:
            a.extend(each) # 桶合并
        bucket = [[] for i in range(radix)]

后记

本篇主要讲述了基数排序，感兴趣的给个赞或者关注~~~