0.概述
01.算法分类
在排序算法中，根据时间复杂度的不同可以将排序算法分为两类：
比较类排序
：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)（下限），因此称为非线性时间比较类排序。
非比较类排序
：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。
02.算法复杂度
03.稳定和不稳定
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
一：比较类排序
交换排序
1. 冒泡排序
2. 快速排序
插入排序
3. 简单插入排序
4. 希尔排序
选择排序
5. 简单选择排序
6. 堆排序
归并排序
7. 归并排序
二：比较类排序
8. 计数排序
9.桶排序
10.基数排序
详细介绍
1.冒泡排序
1.1算法思想
冒泡排序是一种简单的排序算法。通过重复地遍历要排序的数列，一次比较两个元素，从最开始的一对到最后的一对（相当于一个长度为2的滑动窗口），如果它们的顺序错误（看从小到达排列还是从大到小排列）就把它们交换过来。如果是升序排列的话，每次遍历都会把最大值交换到最右边。然后重复这个过程，直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的头部，就像冒泡一样。
这个算法不需要额外的空间，空间复杂度为o（1），同时对n个数据要进行n-1次比较，才能将最大的数固定在数列尾部，所以要固定好n个数，需要进行（n-1）+（n-2）+……+1+0次操作，时间复杂度为o（n^2）
1.2算法过程
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。
1.3 python实现
def
bubbleSort
(
numList
)
:
n
=
len
(
numList
)
if
n
==
0
or
n
==
1
:
return
numList
for
i
in
range
(
n
)
:
# i在这里起到一个类似于计数的作用，看目前有多少个数排好序了
for
j
in
range
(
n
-
i
-
1
)
:
# 由于目前数组中，有i+1个数已经固定到数组尾部，因此只要对前n-i-1对数进行比较即可
if
numList
[
j
]
>
numList
[
j
+
1
]
:
temp
=
numList
[
j
]
numList
[
j
]
=
numList
[
j
+
1
]
numList
[
j
+
1
]
=
temp
return
numList
numList
=
[
3
,
10
,
7
,
1
,
3
,
5
,
6
,
2
,
6
]
print
(
bubbleSort
(
numList
)
)
# 输出结果为 ：[1, 2, 3, 3, 5, 6, 6, 7, 10]
2.快速排序
2.1 算法思想
快速排序是对冒泡排序的一种改进。通过一次排序（
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一次快速排序
）将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序的时间复杂度为o（nlogn），空间复杂度为o（nlogn）
2.2 算法过程
- 从数列中挑出一个元素，称为 “基准”（pivot），通常选取数组的第一个数；
- 遍历数组，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边，因此这不是稳定的排序算法）。分区完成之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归把小于基准值元素的子数列和大于基准值元素的子数列排序，具体过程合步骤1、2一样。
2.3 python实现
def
quickSort
(
numList
)
:
n
=
len
(
numList
)
if
n
==
0
or
n
==
1
:
return
numList
pivot
=
numList
[
0
]
left
=
[
]
right
=
[
]
for
i
in
range
(
1
,
n
)
:
# 分区
if
numList
[
i
]
<
pivot
:
left
.
append
(
numList
[
i
]
)
else
:
right
.
append
(
numList
[
i
]
)
return
quickSort
(
left
)
+
[
pivot
]
+
quickSort
(
right
)
# 对左右两个子数组粉笔进行快排，并连同基准值一块返回
numlist
=
[
3
,
2
,
5
,
6
,
7
,
4
,
1
,
8
]
print
(
quickSort
(
numlist
)
)
# 输出结果为：[1,2,3,4,5,6,7,8]
3. 插入排序（简单插入排序）
3.1算法思想
如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、长度增加1的有序数据。
插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
同样，这个算法不需要额外的存储空间，空间复杂度为o（1），时间复杂度为o（n^2）
3.2算法过程
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。直到排完序为止。
3.3 python实现
def
insertionSort
(
numList
)
:
n
=
len
(
numList
)
if
n
==
0
or
n
==
1
:
return
numList
for
i
in
range
(
n
)
:
preIndex
=
i
-
1
current
=
numList
[
i
]
while
preIndex
>=
0
and
current
<
numList
[
preIndex
]
:
numList
[
preIndex
+
1
]
=
numList
[
preIndex
]
preIndex
-=
1
numList
[
preIndex
+
1
]
=
current
return
numList
numlist
=
[
5
,
3
,
2
,
1
,
6
,
8
,
4
,
2
,
6
]
print
(
insertionSort
(
numlist
)
)
# 输出结果为：[1, 2, 2, 3, 4, 5, 6, 6, 8]
4.希尔排序（缩小增量排序）
4.1 算法思想
希尔排序是插入排序的一种优化，又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。
希尔排序是把记录
按下标的一定增量分组
，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
先取一个正整数d1
4.2 算法分析
希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n²)，而Hibbard增量的希尔排序的时间复杂度为O( n^(3/2) )，希尔排序时间复杂度的下界是n*log2n。希尔排序没有快速排序算法快 O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。
Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征：
① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
这种算法不需要额外的空间，时间复杂度为o(1)
4.3 算法过程
先将整个待排序的元素序列按照增量分割成为若干子序列分别进行直接插入排序，具体算法描述：
- 选择一个增量序列t1，t2，…，tk，其中t1>t2>……>tk，tk=1；
- 按增量序列个数k，对序列进行k 次排序；
- 每次排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量为1 时，即把所有的元素进行一个插入排序处理，表长度即为整个序列的长度。
4.4 python代码
def
shellSort
(
numList
)
:
n
=
len
(
numList
)
if
n
==
0
or
n
==
1
:
return
numList
gap
=
n
//
2
while
gap
>=
1
:
for
i
in
range
(
gap
,
n
)
:
# 把前gap个空出来，以便进行各组之间的插入排序(插入排序也是把第一个元素空出来，当成已经排好序的序列)
tempindex
=
i
while
tempindex
>=
gap
and
numList
[
tempindex
-
gap
]
>
numList
[
tempindex
]
:
numList
[
i
-
gap
]
,
numList
[
tempindex
]
=
numList
[
tempindex
]
,
numList
[
tempindex
-
gap
]
tempindex
-=
gap
# 先把一个子序列中的元素排好序，某个子序列中的元素下标之间的间隔为gap
gap
=
gap
//
2
return
numList
numlist
=
[
4
,
5
,
7
,
8
,
6
,
1
,
2
,
3
,
4
]
print
(
shellSort
(
numlist
)
)
# 输出结果为：[1, 2, 3, 4, 4, 5, 6, 7, 8]
5.选择排序
5.1算法思想
选择排序(Selection-sort)的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
这种算法不需要额外的空间，空间复杂度为o（1）。由于每找一个最小（大）元素，都要遍历一遍这个数组，因此时间复杂度为o（n^2）
5.2算法过程
无序数组为num
- 初始状态：num[0,1,……,n-1]，有序区为空；
- 第i次排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为num[0,1,……,i-1]以及num[i,……,n-1]。该趟排序从当前无序区中选出最小的元素 num[k]，将它与无序区的第1个元素交换，使num[1,……,i]和num[i+1……n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
- 当进行完n-1次排序之后，数组变成有序数组。
5.3举例
例如:给定n=8，数组R中的8个元素的排序码为(8,3,2,1,7,4,6,5),则直接选择排序的过程如下
所示：
初始状态 [ 8 3 2 1 7 4 6 5 ] 8<—>1
第一次 [ 1 3 2 8 7 4 6 5 ] 3 <—> 2
第二次 [ 1 2 3 8 7 4 6 5 ] 3 <—> 3
第三次 [ 1 2 3 8 7 4 6 5 ] 8<—> 4
第四次 [ 1 2 3 4 7 8 6 5 ] 7 <—> 5
第五次 [ 1 2 3 4 5 8 6 7 ] 8 <—>6
第六次 [ 1 2 3 4 5 6 8 7 ] 8 <—> 7
第七次 [ 1 2 3 4 5 6 7 8 ] 排序完成
5.4 python实现
def
selectionSort
(
numList
)
:
n
=
len
(
numList
)
if
n
==
0
or
n
==
1
:
return
numList
minIndex
=
-
1
# 记录当前最小值所在的下标
for
i
in
range
(
n
)
:
minIndex
=
i
for
j
in
range
(
i
+
1
,
n
)
:
if
numList
[
j
]
<
numList
[
minIndex
]
:
minIndex
=
j
temp
=
numList
[
i
]
numList
[
i
]
=
numList
[
minIndex
]
numList
[
minIndex
]
=
temp
return
numList
numlist
=
[
5
,
3
,
2
,
1
,
6
,
8
,
4
,
2
,
6
]
print
(
selectionSort
(
numlist
)
)
# 输出结果为：[1, 2, 2, 3, 4, 5, 6, 6, 8]
6.堆排序
6.1算法思想
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点（同层节点不进行比较）。并且一般来说，升序排列通过构造大顶堆来实现，降序排列通过构造小顶堆来实现。
这种算法不用额外的空间，空间复杂度为o（1），时间复杂度为o（nlogn）
6.1.1堆
堆是一种完全二叉树（完全二叉树 是 一种除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐的树）
堆有两种类型: 大顶堆和小顶堆：
大顶堆：每个结点的值都大于或等于左右孩子结点
小顶堆：每个结点的值都小于或等于左右孩子结点
大顶堆和小顶堆可以通过下面的图进行直观的感受：
6.2 算法过程
- 首先将待排序的数组构造出一个大顶堆（这里以升序排列为例）
- 取出这个大顶堆的堆顶节点(最大值)，与堆的最下最右的元素进行交换，然后把剩下的元素再构造出一个大根堆。
- 重复第二步，直到这个大根堆的长度为1，此时完成排序
ps：将数组中的元素构造成大顶堆的时候，堆顶元素就是所有元素的最大值，而堆的最下最右是数组的最后一个元素，这就相当于把最大值放在了数组的最后，然后在对剩下的元素进行相同操作。
对于这个算法的具体过程的图示，大家可以看一下堆排序图解这篇博客。
过程动图如下
6.3 python代码
6.3.1 递归（不对原数组引入一个辅助元素）
global
length
# 定义全局变量
def
buildMaxHeap
(
numList
)
:
# 构建最大堆，
global
length
length
=
len
(
numList
)
for
i
in
range
(
length
//
2
,
-
1
,
-
1
)
:
# 从最后一个有子节点的根节点节点开始构建的时候从下往上，从右向左构建
heapify
(
numList
,
i
)
def
heapify
(
numList
,
i
)
:
# 堆调整，将剩下的元素调整成最大堆
global
left
,
right
,
largest
,
length
leftChildren
=
2
*
i
+
1
rightChildren
=
2
*
i
+
2
largest
=
i
if
leftChildren
<
length
and
numList
[
leftChildren
]
>
numList
[
largest
]
:
# leftChildren < length先判断是否有子节点，因为python数组下标从零开始的缘故，下标为length/2的元素可能会没有子节点。
largest
=
leftChildren
if
rightChildren
<
length
and
numList
[
rightChildren
]
>
numList
[
largest
]
:
largest
=
rightChildren
if
largest
!=
i
:
# 如果largest（最大的节点所在的下标），不是根节点，说明这三个借点不满足堆的规则，
# 需要进行调整，根节点的下标是i，最大节点的下标是largest，交换即可。
swap
(
numList
,
i
,
largest
)
# 当当前的根节点和子节点满足堆的关系之后，由子节点作为根节点的树可能又不满足了，必须在对下一层的树进行检查和调整。
heapify
(
numList
,
largest
)
def
swap
(
numList
,
i
,
j
)
:
numList
[
i
]
,
numList
[
j
]
=
numList
[
j
]
,
numList
[
i
]
def
heapSort
(
numList
)
:
global
length
buildMaxHeap
(
numList
)
for
i
in
range
(
len
(
numList
)
-
1
,
0
,
-
1
)
:
swap
(
numList
,
0
,
i
)
length
-=
1
# 在调整的时候就不会在调整最后一个元素了
heapify
(
numList
,
0
)
# 由于交换之前，已经都调整为最大堆了，而交换之后，大部分都符合堆的规则，
# 只从堆顶元素（下标为1）开始，只进行局部的调整就好，
# 这时候不用再像刚开始构建最大堆一样从下往上，从右往左调整交换了。
return
numList
numlist
=
[
4
,
5
,
4
,
1
,
8
,
7
,
2
,
6
,
3
]
print
(
heapSort
(
numlist
)
)
6.3.2非递归（引入一个辅助因素，将数组的下标往后加1）
def
swap
(
arr
,
i
,
j
)
:
arr
[
i
]
,
arr
[
j
]
=
arr
[
j
]
,
arr
[
i
]
def
heapAdjust
(
arr
,
start
,
end
)
:
i
=
start
temp
=
arr
[
start
]
j
=
2
*
i
while
j
<=
end
:
if
j
<
end
and
arr
[
j
]
<
arr
[
j
+
1
]
:
j
+=
1
if
arr
[
i
]
<
arr
[
j
]
:
arr
[
i
]
=
arr
[
j
]
i
=
j
j
=
2
*
i
else
:
break
arr
[
i
]
=
temp
def
heapSort
(
numList
)
:
numList
.
insert
(
0
,
0
)
# 由于python，数组的下标从0开始，因此需要加入一个辅助元素，是所有的元素的下标都往后移动一位。
length
=
len
(
numList
)
-
1
firstAdjustRoot
=
length
//
2
for
i
in
range
(
firstAdjustRoot
)
:
# 在构造最大堆的时候，不会对最左侧的0进行处理，因为i不会取到firstAdjustRoot。
heapAdjust
(
numList
,
firstAdjustRoot
-
i
,
length
)
for
i
in
range
(
length
-
1
)
:
swap
(
numList
,
1
,
length
-
i
)
# 由于大顶堆的堆顶元素是最大的，把它和数组最后的元素（堆的最下层最右元素）
# 进行互换，就相当于把最大值放在了最后，下一次，把最后一个元素撇出来，对剩下来的在排序
heapAdjust
(
numList
,
1
,
length
-
i
-
1
)
# 由于交换之前，已经都调整为最大堆了，而交换之后，大部分都符合堆的规则，
# 只从堆顶元素（下标为1）开始，只进行局部的调整就好，
# 这时候不用再像刚开始构建最大堆一样从下往上，从右往左调整交换了。
return
[
numList
[
i
]
for
i
in
range
(
1
,
len
(
numList
)
)
]
numlist
=
[
50
,
16
,
30
,
10
,
60
,
90
,
2
,
80
,
70
]
print
(
heapSort
(
numlist
)
)
参考文章
有辅助元素的堆排序
https://www.cnblogs.com/chengxiao/p/6129630.html
https://www.cnblogs.com/onepixel/articles/7674659.html
7.归并排序
7.1算法思想
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序是一种稳定的排序方法。时间复杂度为O(nlogn）。但是和的排序算法不同，归并排序需要需要额外的空间，空间复杂度为o（n）。
7.2算法过程
归并排序算法的过程是先分在合，即：
- 将一个序列从中间位置分成两个序列；
- 在将这两个子序列按照第一步继续二分下去；
-
直到所有子序列的长度都为1，也就是不可以再二分截止。这时候再一步一步往上子序列两两合并，最终合并成一个有序序列即可。
详细的过程可以通过下面这个图来理解（来源于百度）：
7.3 python代码
def
mergeSort
(
numList
)
:
if
len
(
numList
)
==
0
or
len
(
numList
)
==
1
:
return
numList
# 分，将原来的序列分成从中间分成两个子序列
mid
=
len
(
numList
)
//
2
left
=
numList
[
:
mid
]
right
=
numList
[
mid
:
]
# 分别对左子序列和右子序列进行递归，得到排好序的左右子序列
sortedLeft
=
mergeSort
(
left
)
# 同样的进行分分合合
sortedRight
=
mergeSort
(
right
)
# 将左右两个排好序的子序列在合并成一个总的排好序的序列，并返回
return
merge
(
sortedLeft
,
sortedRight
)
def
merge
(
left
,
right
)
:
# 将两个排好序的子序列合并成一个排好序的子序列
result
=
[
]
# 需要额外的存储空间来存储最后的排好序的结果，所以空间复杂度是o（n）
while
len
(
left
)
>
0
and
len
(
right
)
>
0
:
# left和right可能不等长。
if
left
[
0
]
<=
right
[
0
]
:
result
.
append
(
left
.
pop
(
0
)
)
else
:
result
.
append
(
right
.
pop
(
0
)
)
# 这里也可以不用pop，而是利用两个移动指针，达到遍历两个数组的目的。
#最后根据两个指针是否等于数组长度来判断这个子序列里的元素是否已经都进入result中了。
# 循环结束，不管最后哪个非空，都加上就行。
result
+=
right
result
+=
left
return
result
numlist
=
[
2
,
4
,
7
,
5
,
8
,
1
,
3
,
6
]
print
(
mergeSort
(
numlist
)
)
# 输出结果为：[1,2,3,4,5,6,7,8]
8.计数排序
8.1 算法思想
计数排序是一个非基于比较的排序算法。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），当o（k）< o（nlogn）时快于任何比较排序算法。这是一种 牺牲空间换取时间 的做法，而且当O(k)>O(n log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n log(n)), 如归并排序，堆排序）。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数（此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定）。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。
计数排序只需遍历一次数据，在计数数组中记录，输出计数数组中有记录的下标，时间复杂度为O(n+k)。
这种算法同时也有额外空间开销计数数组和结果数组，空间复杂度为o（n+k）
8.2 算法过程
- 找出待排序的数组中最大和最小的元素；
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项； （由于这个原因，要排序的数必须在大于等于0，且由于时间复杂度的问题，数组元素的上限也有一定的限制，否则，时间复杂度不如比较类排序。）
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1.
8.2.1 算法举例
以下说明下计数排序的过程。以《算法导论》这本书的一个例子进行说明：
初始化数组： A[2,5,3,0,2,3,0,3]
假设我们已经事先知道A数组的最大值5，排序过程如下：
a）创建一个长度为6的临时存储数组空间C，并将C数组每一个元素初始化为0。
b）统计重复元素的个数。A数组的元素作为数组C的下标，扫描数组A，A数组元素每出现一次，数组C等于该元素的下标位置的元素加一。例如第一次扫描到的是2，则C[2]=0+1=1,…,第五次再次扫描到了2，C[2]=1+1=2，说明这个数组2的个数为2个。C[2,0,2,3,0,1]
c）计算有多少（y）个元素小于或等于数组C的下标。根据计数数组累加得到C[2,2,4,7,7,8] (小于等于0的有2个，小于等于1的有2个，小于等于2的4个，…小于等于5的有8个)
d）倒序扫描数组A的元素x，依次将元素放置于输出序列res[y]位置,y为小于或者等于这个元素的个数,同时临时数组C[x]=C[x]-1;重复这个过程直至扫描到数组A的首位元素。res[0,0,2,2,3,3,3,5]
因为倒叙遍历原数组，不会改变原来相等元素的相对位置，所以这是稳定的
简而言之就是先统计出数组A元素x小于或等于自身的元素个数y，将x放置于res[y]处，y-1，接着重复这个过程。
简而言之
以[5,3,6,6]数组为例，小于等于5的元素个数为2，小于等于3的元素个数为1，小于等于6的元素个数为4。res = [0,0,0,0]，从后往前遍历原数组，6，小于等于6的元素个数为4，最后一个6，放在res[4-1]的位置，这是在剩下的元素中，小于等于6的个数为4-1=3；在继续遍历，6，小于等于6的元素个数为3，放在res[3-1]的位置。再继续遍历，3，这时候小于等于3的元素个数为1，不变，放在res[1-1]的位置；5，小于等于5的元素个数为2，放在res[2-1]的位置。
8.3 python代码
def
countingSort
(
numList
)
:
n
=
len
(
numList
)
if
n
==
0
or
n
==
1
:
return
numList
maxVal
=
max
(
numList
)
countArr
=
[
0
for
i
in
range
(
maxVal
+
1
)
]
for
i
in
numList
:
countArr
[
i
]
+=
1
for
i
in
range
(
1
,
len
(
countArr
)
)
:
countArr
[
i
]
+=
countArr
[
i
-
1
]
res
=
[
0
for
i
in
range
(
n
)
]
for
i
in
range
(
n
-
1
,
-
1
,
-
1
)
:
res
[
countArr
[
numList
[
i
]
]
-
1
]
=
numList
[
i
]
countArr
[
numList
[
i
]
]
-=
1
# 必须要减1，由于待排序元素在res中的位置是由计数数组的值来决定的。
# 当遍历了元素x之后，小于x的元素不会受影响，大于x的元素不会受影响，
# 只有等于x的元素会受影响，在往res中压的时候，要比x的位置往前移动一位，
# 因此需要将计数数组中的下标为x的值减1，使得下次在遍历到x的时候，
# 压入的位置在前一个x的位置之前
return
res
numlist
=
[
5
,
8
,
9
,
3
,
2
,
5
,
1
,
6
,
8
]
print
(
countingSort
(
numlist
)
)
# 输出结果为：[1, 2, 3, 5, 5, 6, 8, 8, 9]
9.桶排序
9.1 算法思想
桶排序假设待排序的一组数均匀独立的分布在一个范围中，并将这一范围划分成几个子范围（桶）。然后基于某种映射函数f （ 高效与否的关键就在于这个映射函数的确定 ），将待排序列的关键字 k 映射到第i个桶中 (即桶数组B 的下标i) ，那么该关键字k 就作为 B[i]中的元素。接着将各个桶中的数据分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排） 。然后依次枚举输出 B[0]….B[M] 中的全部内容即完成了一个数组的桶排列。
ps：桶排序可以有很多方法，具体区别在于映射函数、桶、以及桶内排序的方法不同。
由于要构造桶，因此需要额外的空间，空间复杂度为o（n+k），时间复杂度为o（n+k），最好是o(N)，且桶排序是稳定的。
9.2 算法过程
- 设置一个定量的数组当作空桶；（当数字少的时候，可以设置n个桶，只把相等的数放在同一个桶，不过这种方法空桶过多，数字多的时候回消耗极大的空间。数字多的时候可以少设置几个桶，利用映射关系将多个数放在一个桶。） （类似于系统抽样，是指尽可能均匀分布在各个桶里）
- 遍历输入数据，并且把数据映射完之后，一个一个放到对应的桶里去；
- 对每个不是空的桶进行排序；
-
从不是空的桶里把排好序的数据拼接起来。
桶的数量等于待排序元素数量展示，其中范围分别是[0,9),[10,19),……，[90,99)
9.3 python代码
def
bucktetSort
(
numList
,
bucketNum
)
:
if
len
(
numList
)
==
0
or
len
(
numList
)
==
1
:
return
numList
maxNum
=
numList
[
0
]
minNum
=
numList
[
0
]
for
i
in
range
(
1
,
len
(
numList
)
)
:
# 找到最大最小值
if
numList
[
i
]
<
minNum
:
minNum
=
numList
[
i
]
elif
numList
[
i
]
>
maxNum
:
maxNum
=
numList
[
i
]
else
:
continue
bucketSize
=
(
maxNum
-
minNum
+
1
)
//
bucketNum
# 根据桶的数量找到每个桶的范围
buckets
=
[
[
]
for
i
in
range
(
bucketNum
)
]
for
i
in
range
(
len
(
numList
)
)
:
# 将各个数分配到各个桶
buckets
[
(
numList
[
i
]
-
minNum
)
//
bucketSize
]
.
append
(
numList
[
i
]
)
for
i
in
range
(
bucketNum
)
:
# 桶内排序，可以使用各种排序方法
buckets
[
i
]
.
sort
(
)
res
=
[
]
for
i
in
range
(
len
(
buckets
)
)
:
# 分别将各个桶内的数提出来，压入结果
for
j
in
range
(
len
(
buckets
[
i
]
)
)
:
res
.
append
(
buckets
[
i
]
[
j
]
)
return
res
numlist
=
[
11
,
34
,
23
,
56
,
8
,
20
,
66
,
45
,
54
,
87
,
78
]
print
(
bucktetSort
(
numlist
,
5
)
)
# 利用5个桶
# 输出结果为：[8, 11, 20, 23, 34, 45, 54, 56, 66, 78, 87]
10.基数排序
10.1 算法思想
基数排序是对桶排序的扩展。
第一类：最低位优先法，简称LSD法：先从最低位开始排序，再对次低位排序，直到对最高位排序后得到一个有序序列；
第二类：最高位优先法，简称MSD法：先从最高位开始排序，再逐个对各分组按次高位进行子排序，循环直到最低位。（位没有数的话，补0）
这里以LSD为例，由于待排序元素每一位上的数字的取值范围是0—9，因此每按照某一位，需要10个桶，这样每一位上相同的数字会分配到一个桶里。
10.2 算法过程
假设有一未排序数组：
3,44,38,5,47,15,36,26,27,2,46,4,19,50,48
首先根据个位数的数值，在遍历数值时将它们分配至编号0到9的桶中：
0：50
1：
2： 2
3： 3
4： 44,4
5： 5,15
6：36,26,46
7：47,27
8：38,48
9：19,
第二步
接下来将这些桶中的数值重新串接起来，成为以下的数列：
50,2,3,44,4,5,15,36,26,46,47,27,38,48,19
接着再进行一次分配，这次是根据十位数来分配：
0：2,3,4,5
1：15,19
2：26,27
3：36,38
4：44,46,47,48
5：50,
6：
7：
8：
9：
第三步
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
2,3,4,5,15,19,26,27,36,38,44,46,47,48,50
这时候整个数列已经排序完毕。
如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。
10.3 python代码
def
getbit
(
num
,
i
)
:
# 获取元素第i位的数
return
(
num
%
(
i
*
10
)
-
(
num
%
i
)
)
//
i
def
getMax
(
numList
)
:
# 获取数组中的最大值
if
len
(
numList
)
==
1
:
return
numList
[
0
]
maxNum
=
numList
[
0
]
for
i
in
range
(
len
(
numList
)
)
:
if
numList
[
i
]
>
maxNum
:
maxNum
=
numList
[
i
]
return
maxNum
def
radixSort
(
numList
)
:
if
len
(
numList
)
==
0
or
len
(
numList
)
==
1
:
return
numList
maxNum
=
getMax
(
numList
)
bitCount
=
0
index
=
1
while
maxNum
//
index
:
bitCount
+=
1
index
*=
10
currentBit
=
1
# 统计一下最大值的bitCount（有多少位），因为比较多少次，是有最大值的位数决定的
while
currentBit
<=
10
**
(
bitCount
-
1
)
:
# 开始循环的进行每一个位的比较
res
=
[
]
buckets
=
[
[
]
for
i
in
range
(
10
)
]
# 桶排序
for
i
in
numList
:
currentBitNum
=
getbit
(
i
,
currentBit
)
buckets
[
currentBitNum
]
.
append
(
i
)
for
i
in
range
(
10
)
:
for
j
in
range
(
len
(
buckets
[
i
]
)
)
:
res
.
append
(
buckets
[
i
]
[
j
]
)
numList
=
res
currentBit
*=
10
return
numList
numlist
=
[
12
,
3
,
45
,
3543
,
214
,
1
,
4553
]
print
(
radixSort
(
numlist
)
)
# 输出结果为：[1, 3, 12, 45, 214, 3543, 4553]
参考文章
https://www.cnblogs.com/onepixel/articles/7674659.html
