代码视界

Hanpeng Chen的个人博客

十大经典排序算法

本文于 605 天之前发表,文中内容可能已经过时。

前言

在上一篇文章《Javascript-数组乱序》中我们提到不同浏览器采用不同的排序算法来实现Array.prototype.sort方法,今天我们一起来学习常见的几种排序算法。

我们常说的十大经典排序算法有:冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。

算法概述

算法分类

上面的十种排序算法可以分为两类:

  • 比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破 O(nlogn),因此也称为非线性时间比较类排序。

  • 非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。

每个排序算法属于哪一类如下图所示:

算法复杂度

相关概念

在上图中我们标注了每个算法是否稳定,那么如何区分稳定和不稳定?

  • 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。

  • 不稳定:如果a原本在b前面,而a=b,排序之后a可能会出现在b的后面。

冒泡排序

冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

冒泡排序还有一种优化算法,就是立一个 flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

算法步骤:

  • 比较相邻的元素。如果第一个比第二个大,就交换他们两个。

  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

  • 针对所有的元素重复以上的步骤,除了最后一个。

  • 持续每次对越来越少的元素重复上面的步骤1-3,直到没有任何一对数字需要比较。

代码实现:

python版本

1
2
3
4
5
6
7
8
def bubble_sort(arr):
length = len(arr)
for x in range(1, length):
for i in range(0, length - x):
if arr[i] > arr[i + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]

return arr

JavaScript 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
for (var j = 0; j < len - i -1; j++) {
if (arr[j] > arr[j+1]) {
var temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}

选择排序

选择排序(Selection sort)是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

其算法思想:从数组中选择最小元素,并将其与第一个元素交换位置。再从数组中剩下的元素中选择出最小元素,将其与数组的第二个元素交换位置。不断进行这样的操作,直到将整个数组排序。

算法步骤

  • 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。

  • 再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。

  • 重复步骤2,直到所有元素均排序完毕。

代码实现

Python代码实现:

1
2
3
4
5
6
7
8
9
10
def selectionSort(arr):
for i in range(0, len(arr)):
index = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[index]:
index = j
if i != index:
arr[i], arr[index] = arr[index], arr[i]

return arr

JavaScript代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function selectionSort(arr) {
var len = arr.length;
var index, temp;
for (var i = 0; i < len - 1; i++) {
index = i;
for (var j = i + 1; j < len -1; j++) {
if (arr[j] < arr[index]) {
index = j;
}
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}
return arr;
}

插入排序

插入排序(Insertion sort)是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

插入排序的时间复杂度取决于数组的初始顺序,如果数组已经部分有序了,那么逆序较少,需要的交换次数也就较少,时间复杂度较低。

  • 平均情况下插入排序需要 N^2/4 比较以及 N^2/4 次交换;
  • 最坏的情况下需要 N^2/2 比较以及 N^2/2 次交换,最坏的情况是数组是倒序的;
  • 最好的情况下需要 N-1 次比较和 0 次交换,最好的情况就是数组已经有序了。

算法步骤

  • 从第一个元素开始,该元素可以认为已经被排序;
  • 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  • 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  • 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  • 将新元素插入到该位置后;
  • 重复步骤2~5。

代码实现

python代码实现

1
2
3
4
5
6
7
8
9
def insertionSort(arr):
for i in range(len(arr)):
preIndex = i
current = arr[i]
while preIndex >= 0 and arr[preIndex] > current:
arr[preIndex + 1] = arr[preIndex]
preIndex -= 1
arr[preIndex + 1] = current
return arr

JavaScript代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}

希尔排序

对于大规模的数组,插入排序很慢,因为它只能交换相邻的元素,每次只能将逆序数量减1。希尔排序的出现就是为了解决插入排序的这种局限性,它通过交换不相邻的元素,每次可以将逆序数量减少大于1。

希尔排序(Shell’s Sort),也称为递减增量排序算法,是插入排序的一种更高效的改进版本,但希尔排序是非稳定排序算法。

希尔排序使用插入排序对间隔h的序列进行排序。通过不断减小h,最后令h=1,就可以使得整个数组是有序的。

希尔排序的运行时间达不到平方级别,使用递增序列1,4,10,20…的希尔排序所需要的比较次数不会超过N的若干倍乘以递增序列的长度。后面介绍的高级排序算法只会比希尔排序快两倍左右。

算法步骤

  • 选择一个增量序列 t1, t2, …, tk,其中ti > tj, tk = 1;

  • 按增量序列个数k,对序列进行k趟排序;

  • 每趟排序,根据对应的增量ti, 将待排序列分割为若干长度为m的子序列,分别对各子表进行直接插入排序。仅增量因子为1时,整个序列作为一个表来处理,表长度即为整个序列的长度。

代码实现

python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def shellSort(arr):
import math
gap = 1
while(gap < len(arr)/3):
gap = gap * 3 + 1
while gap > 0:
for i in range(gap, len(arr)):
temp = arr[i]
j = i - gap
while j >= 0 and arr[j] > temp:
arr[j + gap] = arr[j]
j -= gap
arr[j + gap] = temp
gap = math.floor(gap/3)
return arr

javascript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function shellSort(arr) {
var len = arr.length,
temp,
gap = 1;
while(gap < len / 3) {
gap = gap * 3 + 1
}
for (gap; gap > 0; gap = Math.floor(gap / 3)) {
for (var i = gap; i < len; i++) {
temp = arr[i];
for (var j = i - gap; j >=0 && arr[j] > temp; j -= gap) {
arr[j + gap] = arr[j];
}
arr[j + gap] = temp;
}
}
return arr;
}

归并排序

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

归并排序是一种稳定的排序方法,和选择排序一样,性能不受输入数据的影响,但表现比选择排序好很多,因为时间复杂度始终都是O(nlogn),代价就是需要额外的内存空间。

算法步骤

  • 把长度为n的输入序列分为两个长度为n/2的子序列;
  • 对这两个子序列分别采用归并排序;
  • 将两个排好序的子序列合并成一个最终的排序序列。

代码实现

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

function mergeSort(arr) { // 采用自上而下的递归方法
var len = arr.length;
if(len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
var result = [];

while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}

while (left.length)
result.push(left.shift());

while (right.length)
result.push(right.shift());

return result;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def mergeSort(arr):
import math
if (len(arr) < 2):
return arr
middle = math.floor(len(arr) / 2)
left, right = arr[0:middle], arr[middle:]
return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0));
while left:
result.append(left.pop(0))
while right:
result.append(right.pop(0));
return result

快速排序

快速排序(quick sort)通过一个切分元素将数组分为两个子数组,左子数组小于等于切分元素,右子数组大于等于切分元素,将这两个子数组排序也就将整个数组排序了。

算法步骤

  • 从数列中挑出一个元素,称为 “基准”(pivot);
  • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;

性能分析

快速排序是原地排序,不需要辅助数组,但是递归调用需要辅助栈。

最坏情况下,第一次从最小的元素切分,第二次从第二小的元素切分,如此这般。因此最坏的情况下需要比较 N^2/2。为了防止数组最开始就是有序的,在进行快速排序时需要随机打乱数组。

快速排序的最坏运行情况是 O(n²),比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn),且 O(nlogn) 记号中隐含的常数因子很小,比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。

代码实现

javascript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function quickSort(arr, left, right) {
var len = arr.length,
partitionIndex,
left = typeof left != 'number' ? 0 : left,
right = typeof right != 'number' ? len - 1 : right;

if (left < right) {
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex-1);
quickSort(arr, partitionIndex+1, right);
}
return arr;
}

function partition(arr, left ,right) { // 分区操作
var pivot = left, // 设定基准值(pivot)
index = pivot + 1;
for (var i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index-1;
}

function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def quickSort(arr, left=None, right=None):
left = 0 if not isinstance(left,(int, float)) else left
right = len(arr)-1 if not isinstance(right,(int, float)) else right
if left < right:
partitionIndex = partition(arr, left, right)
quickSort(arr, left, partitionIndex-1)
quickSort(arr, partitionIndex+1, right)
return arr

def partition(arr, left, right):
pivot = left
index = pivot+1
i = index
while i <= right:
if arr[i] < arr[pivot]:
swap(arr, i, index)
index+=1
i+=1
swap(arr,pivot,index-1)
return index-1

def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]

堆排序

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:

  • 大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;
  • 小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列;

堆排序的平均时间复杂度为 Ο(nlogn)。

算法步骤

  • 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;

  • 将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];

  • 由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。

代码实现

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
var len;    // 因为声明的多个函数都需要数据长度,所以把len设置成为全局变量

function buildMaxHeap(arr) { // 建立大顶堆
len = arr.length;
for (var i = Math.floor(len/2); i >= 0; i--) {
heapify(arr, i);
}
}

function heapify(arr, i) { // 堆调整
var left = 2 * i + 1,
right = 2 * i + 2,
largest = i;

if (left < len && arr[left] > arr[largest]) {
largest = left;
}

if (right < len && arr[right] > arr[largest]) {
largest = right;
}

if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest);
}
}

function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

function heapSort(arr) {
buildMaxHeap(arr);

for (var i = arr.length-1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0);
}
return arr;
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def buildMaxHeap(arr):
import math
for i in range(math.floor(len(arr)/2),-1,-1):
heapify(arr,i)

def heapify(arr, i):
left = 2*i+1
right = 2*i+2
largest = i
if left < arrLen and arr[left] > arr[largest]:
largest = left
if right < arrLen and arr[right] > arr[largest]:
largest = right

if largest != i:
swap(arr, i, largest)
heapify(arr, largest)

def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):
global arrLen
arrLen = len(arr)
buildMaxHeap(arr)
for i in range(len(arr)-1,0,-1):
swap(arr,0,i)
arrLen -=1
heapify(arr, 0)
return arr

计数排序

计数排序(Counting Sort)不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

计数排序的特征

当输入的元素是 n 个 0 到 k 之间的整数时,它的运行时间是 Θ(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。

由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。例如:计数排序是用来排序0到100之间的数字的最好的算法,但是它不适合按字母顺序排序人名。但是,计数排序可以用在基数排序中的算法来排序数据范围很大的数组。

通俗地理解,例如有 10 个年龄不同的人,统计出有 8 个人的年龄比 A 小,那 A 的年龄就排在第 9 位,用这个方法可以得到其他每个人的位置,也就排好了序。当然,年龄有重复时需要特殊处理(保证稳定性),这就是为什么最后要反向填充目标数组,以及将每个数字的统计减去 1 的原因。

算法的步骤

  • 找出待排序的数组中最大和最小的元素
  • 统计数组中每个值为i的元素出现的次数,存入数组C的第i项
  • 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)
  • 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1

代码实现

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function countingSort(arr, maxValue) {
var bucket = new Array(maxValue+1),
sortedIndex = 0;
arrLen = arr.length,
bucketLen = maxValue + 1;

for (var i = 0; i < arrLen; i++) {
if (!bucket[arr[i]]) {
bucket[arr[i]] = 0;
}
bucket[arr[i]]++;
}

for (var j = 0; j < bucketLen; j++) {
while(bucket[j] > 0) {
arr[sortedIndex++] = j;
bucket[j]--;
}
}

return arr;
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def countingSort(arr, maxValue):
bucketLen = maxValue+1
bucket = [0]*bucketLen
sortedIndex =0
arrLen = len(arr)
for i in range(arrLen):
if not bucket[arr[i]]:
bucket[arr[i]]=0
bucket[arr[i]]+=1
for j in range(bucketLen):
while bucket[j]>0:
arr[sortedIndex] = j
sortedIndex+=1
bucket[j]-=1
return arr

桶排序

桶排序(Bucket Sort)是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。

算法步驟

  • 设置一个定量的数组当作空桶;
  • 遍历输入数据,并且把数据一个一个放到对应的桶里去;
  • 对每个不是空的桶进行排序;
  • 从不是空的桶里把排好序的数据拼接起来。

算法分析

为了使桶排序更加高效,我们需要做到这两点:

在额外空间充足的情况下,尽量增大桶的数量
使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时,对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要。

  1. 什么时候最快
    当输入的数据可以均匀的分配到每一个桶中。

  2. 什么时候最慢
    当输入的数据被分配到了同一个桶中。

代码实现

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
function bucketSort(arr, bucketSize) {
if (arr.length === 0) {
return arr;
}

var i;
var minValue = arr[0];
var maxValue = arr[0];
for (i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i]; // 输入数据的最小值
} else if (arr[i] > maxValue) {
maxValue = arr[i]; // 输入数据的最大值
}
}

//桶的初始化
var DEFAULT_BUCKET_SIZE = 5; // 设置桶的默认数量为5
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
var buckets = new Array(bucketCount);
for (i = 0; i < buckets.length; i++) {
buckets[i] = [];
}

//利用映射函数将数据分配到各个桶中
for (i = 0; i < arr.length; i++) {
buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
}

arr.length = 0;
for (i = 0; i < buckets.length; i++) {
insertionSort(buckets[i]); // 对每个桶进行排序,这里使用了插入排序
for (var j = 0; j < buckets[i].length; j++) {
arr.push(buckets[i][j]);
}
}

return arr;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def bucket_sort(array, n):
# 1.创建n个空桶
new_list = [[] for _ in range(n)]

# 2.把arr[i] 插入到bucket[n*array[i]]
for data in array:
index = int(data * n)
new_list[index].append(data)

# 3.桶内排序
for i in range(n):
new_list[i].sort()

# 4.产生新的排序后的列表
index = 0
for i in range(n):
for j in range(len(new_list[i])):
array[index] = new_list[i][j]
index += 1
return array


def main():
array = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
n = len(array)
array = bucket_sort(array, n)
print(array)


if __name__ == '__main__':
main()

基数排序

基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将数据按位数切割成不同的数字,然后按每个位数分别比较。

基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。

算法步骤

  • 取得数组中的最大数,并取得位数;
  • arr为原始数组,从最低位开始取每个位组成radix数组;
  • 对radix进行计数排序(利用计数排序适用于小范围数的特点)。

算法分析

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:

  • 基数排序:根据键值的每位数字来分配桶;
  • 计数排序:每个桶只存储单一键值;
  • 桶排序:每个桶存储一定范围的数值;

代码实现

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for(var j = 0; j < arr.length; j++) {
var bucket = parseInt((arr[j] % mod) / dev);
if(counter[bucket]==null) {
counter[bucket] = [];
}
counter[bucket].push(arr[j]);
}
var pos = 0;
for(var j = 0; j < counter.length; j++) {
var value = null;
if(counter[j]!=null) {
while ((value = counter[j].shift()) != null) {
arr[pos++] = value;
}
}
}
}
return arr;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#确定排序的次数
#排序的顺序跟序列中最大数的位数相关
def radix_sort_nums(L):
maxNum = L[0]
#寻找序列中的最大数
for x in L:
if maxNum < x:
maxNum = x
#确定序列中的最大元素的位数
times = 0
while (maxNum > 0):
maxNum = (int)(maxNum/10)
times = times+1
return times
#找到num从低到高第pos位的数据
def get_num_pos(num,pos):
return ((int)(num/(10**(pos-1))))%10
#基数排序
def radix_sort(L):
count = 10*[None] #存放各个桶的数据统计个数
bucket = len(L)*[None] #暂时存放排序结果
#从低位到高位依次执行循环
for pos in range(1,radix_sort_nums(L)+1):
#置空各个桶的数据统计
for x in range(0,10):
count[x] = 0
#统计当前该位(个位,十位,百位....)的元素数目
for x in range(0,len(L)):
#统计各个桶将要装进去的元素个数
j = get_num_pos(int(L[x]),pos)
count[j] = count[j]+1
#count[i]表示第i个桶的右边界索引
for x in range(1,10):
count[x] = count[x] + count[x-1]
#将数据依次装入桶中
for x in range(len(L)-1,-1,-1):
#求出元素第K位的数字
j = get_num_pos(L[x],pos)
#放入对应的桶中,count[j]-1是第j个桶的右边界索引
bucket[count[j]-1] = L[x]
#对应桶的装入数据索引-1
count[j] = count[j]-1
# 将已分配好的桶中数据再倒出来,此时已是对应当前位数有序的表
for x in range(0,len(L)):
L[x] = bucket[x]

文章参考资料:

欢迎关注微信公众号: 『前端极客技术』『代码视界』
支付宝打赏 微信打赏

赞赏是不耍流氓的鼓励