📄 radixsort.htm
字号:
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="css/stdlayout.css" type="text/css">
<link rel="stylesheet" href="css/print.css" type="text/css">
<meta content="text/html; charset=gb2312" http-equiv="content-type">
<title>基数排序法</title>
</head>
<body>
<h3><a href="http://caterpillar.onlyfun.net/GossipCN/index.html">From
Gossip@caterpillar</a></h3>
<h1><a href="AlgorithmGossip.htm">Algorithm Gossip: 基数排序法</a></h1>
<h2>说明</h2>
在之前所介绍过的排序方法，都是属于“比较性”的排序法，也就是每次排序时 ，都是比较整个键值的大小以进行排序。<br>
<br>
这边所要介绍的“基数排序法”（radix sort）则是属于“分配式排序”（distribution
sort），基数排序法又称“桶子法”（bucket sort）或bin
sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O
(nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。<br>
<h2>解法</h2>
基数排序的方式可以采用LSD（Least sgnificant digital）或MSD（Most sgnificant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。<br>
<br>
以LSD为例，假设原来有一串数值如下所示：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">73, 22, 93, 43, 55, 14, 28, 65, 39, 81</span><br>
</div>
<br>
首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：<br>
<table border="1" width="100%">
<tbody>
<tr>
<td align="left" valign="top"><small>0 </small></td>
<td align="left" valign="top"><small>1 </small></td>
<td align="left" valign="top"><small>2 </small></td>
<td align="left" valign="top"><small>3 </small></td>
<td align="left" valign="top"><small>4 </small></td>
<td align="left" valign="top"><small>5 </small></td>
<td align="left" valign="top"><small>6 </small></td>
<td align="left" valign="top"><small>7 </small></td>
<td align="left" valign="top"><small>8 </small></td>
<td align="left" valign="top"><small>9 </small></td>
</tr>
<tr>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="left" valign="top"><small>81 </small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="left" valign="top"><small>65 </small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="left" valign="top"><small>39 </small></td>
</tr>
<tr>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="left" valign="top"><small>43 </small></td>
<td align="left" valign="top"><small>14 </small></td>
<td align="left" valign="top"><small>55 </small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="left" valign="top"><small>28 </small></td>
<td align="right" valign="top"><small> <br>
</small></td>
</tr>
<tr>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="left" valign="top"><small>93 </small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
</tr>
<tr>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="left" valign="top"><small>22 </small></td>
<td align="left" valign="top"><small>73 </small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
</tr>
</tbody>
</table>
<br>
接下来将这些桶子中的数值重新串接起来，成为以下的数列： <br>
<em><strong></strong></em>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">81, 22, 73, 93, 43, 14, 55, 65, 28, 39</span><br>
</div>
<br>
接着再进行一次分配，这次是根据十位数来分配：<br>
<table border="1" width="100%">
<tbody>
<tr>
<td align="left" valign="top"><small>0 </small></td>
<td align="left" valign="top"><small>1 </small></td>
<td align="left" valign="top"><small>2 </small></td>
<td align="left" valign="top"><small>3 </small></td>
<td align="left" valign="top"><small>4 </small></td>
<td align="left" valign="top"><small>5 </small></td>
<td align="left" valign="top"><small>6 </small></td>
<td align="left" valign="top"><small>7 </small></td>
<td align="left" valign="top"><small>8 </small></td>
<td align="left" valign="top"><small>9 </small></td>
</tr>
<tr>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="left" valign="top"><small>28 </small></td>
<td align="left" valign="top"><small>39 </small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="right" valign="top"><small> <br>
</small></td>
</tr>
<tr>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="left" valign="top"><small>14 </small></td>
<td align="left" valign="top"><small>22 </small></td>
<td align="right" valign="top"><small> <br>
</small></td>
<td align="left" valign="top"><small>43 </small></td>
<td align="left" valign="top"><small>55 </small></td>
<td align="left" valign="top"><small>65 </small></td>
<td align="left" valign="top"><small>73 </small></td>
<td align="left" valign="top"><small>81 </small></td>
<td align="left" valign="top"><small>93 </small></td>
</tr>
</tbody>
</table>
<br>
接下来将这些桶子中的数值重新串接起来，成为以下的数列： <br>
<em><strong></strong></em>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">14, 22, 28, 39, 43, 55, 65, 73, 81, 93 </span><br>
</div>
<br>
这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。 <br>
<br>
LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好，MSD的方式恰与LSD相反，是由高位数为基底开始进行分配，其他的演
算方式则都相同。 <br>
<h2> 实作</h2>
<ul>
<li> C
</li>
</ul>
<pre>#include <stdio.h> <br>#include <stdlib.h> <br><br>int main(void) { <br> int data[10] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81}; <br> int temp[10][10] = {0}; <br> int order[10] = {0}; <br> int i, j, k, n, lsd; <br> <br> k = 0; <br> n = 1; <br><br> printf("\n排序前: "); <br> for(i = 0; i < 10; i++) <br> printf("%d ", data[i]); <br><br> putchar('\n'); <br><br> while(n <= 10) { <br> for(i = 0; i < 10; i++) { <br> lsd = ((data[i] / n) % 10); <br> temp[lsd][order[lsd]] = data[i]; <br> order[lsd]++; <br> } <br><br> printf("\n重新排列: "); <br> for(i = 0; i < 10; i++) { <br> if(order[i] != 0) <br> for(j = 0; j < order[i]; j++) { <br> data[k] = temp[i][j]; <br> printf("%d ", data[k]); <br> k++; <br> } <br> order[i] = 0; <br> } <br><br> n *= 10; <br> k = 0; <br> } <br><br> putchar('\n'); <br> printf("\n排序后: "); <br> for(i = 0; i < 10; i++) <br> printf("%d ", data[i]); <br><br> return 0; <br>} <br></pre>
<br>
<ul>
<li> Java
</li>
</ul>
<pre>public class RadixSort {<br> public static void sort(int[] number, int d) {<br> int k = 0;<br> int n = 1;<br> <br> int[][] temp = new int[number.length][number.length];<br> int[] order = new int[number.length];<br> <br> while(n <= d) { <br> for(int i = 0; i < number.length; i++) { <br> int lsd = ((number[i] / n) % 10); <br> temp[lsd][order[lsd]] = number[i]; <br> order[lsd]++; <br> } <br><br> for(int i = 0; i < number.length; i++) { <br> if(order[i] != 0) <br> for(int j = 0; j < order[i]; j++) { <br> number[k] = temp[i][j]; <br> k++; <br> } <br> order[i] = 0; <br> } <br><br> n *= 10; <br> k = 0; <br> } <br> }<br><br> public static void main(String[] args) {<br> int[] data = <br> {73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100}; <br> <br> RadixSort.sort(data, 100);<br> <br> for(int i = 0; i < data.length; i++) {<br> System.out.print(data[i] + " "); <br> }<br> }<br>}</pre>
<br>
<br>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -