2021年的最后一个博客文章
排序算法
参考网址：
算法分类
相关概念
比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
算法复杂度
相关概念
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
正文介绍
说明，本文只提供概念和结果，需要了解执行过程的可以通过编辑器断点调试获取执行过程。
- 冒泡排序（Bubble Sort）
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 重复步骤1~3，直到排序完成。
- 选择排序（Selection Sort）
- 初始状态：无序区为R[1…n]，有序区为空。
- 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
- n-1趟结束，数组有序化了。
- 插入排序（Insertion Sort）
- 从第一个元素开始，该元素可以认为已经被排序。
- 取出下一个元素，在已经排序的元素序列中从后向前扫描。
- 如果该元素（已排序）大于新元素，将该元素移到下一位置。
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
- 将新元素插入到该位置后。
- 重复步骤2~5。
- 希尔排序（Shell Sort）
- 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1。
- 按增量序列个数k，对序列进行k 趟排序。
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
- 归并排序（Merge Sort）
- 把长度为n的输入序列分成两个长度为n/2的子序列。
- 对这两个子序列分别采用归并排序。
- 将两个排序好的子序列合并成一个最终的排序序列。
- 快速排序（Quick Sort）
- 从数列中挑出一个元素，称为 “基准”（pivot）。
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
- 堆排序（Heap Sort）
- 将初始待排序关键字序列(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，则整个排序过程完成。
- 计数排序（Counting Sort）
- 找出待排序的数组中最大和最小的元素。
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项。
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）。
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
- 桶排序（Bucket Sort）【数据的长度必须完全一样】
- 设置一个定量的数组当作空桶。
- 遍历输入数据，并且把数据一个一个放到对应的桶里去。
- 对每个不是空的桶进行排序。
- 从不是空的桶里把排好序的数据拼接起来。
- 基数排序（Radix Sort）
- 取得数组中的最大数，并取得位数。
- arr为原始数组，从最低位开始取每个位组成radix数组。
- 对radix进行计数排序（利用计数排序适用于小范围数的特点）。
JavaScript编码案例
1.冒泡排序（Bubble Sort）
function bubbleSort(arr) {
var len = arr.length;
for(var i = 0; i < len - 1; i++) {
for(var j = 0; j < len - 1 - i; j++) {
if(arr[j] > arr[j+1]) { // 相邻元素两两对比
var temp = arr[j+1]; // 元素交换
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
2.选择排序（Selection Sort）
function selectionSort(arr) {
var len = arr.length;
var minIndex, temp;
for(var i = 0; i < len - 1; i++) {
minIndex = i;
for(var j = i + 1; j < len; j++) {
if(arr[j] < arr[minIndex]) { // 寻找最小的数
minIndex = j; // 将最小数的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
3.插入排序（Insertion Sort）
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;
}
4.希尔排序（Shell Sort）
function shellSort(arr) {
var len = arr.length;
for(var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
// 注意：这里和动图演示的不一样，动图是分组执行，实际操作是多个分组交替执行
for(var i = gap; i < len; i++) {
var j = i;
var current = arr[i];
while(j - gap >= 0 && current < arr[j - gap]) {
arr[j] = arr[j - gap];
j = j - gap;
}
arr[j] = current;
}
}
return arr;
}
5.归并排序（Merge Sort）
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>0 && right.length>0) {
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;
}
6.快速排序（Quick Sort）
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;
}
7.堆排序（Heap Sort）
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;
}
8.计数排序（Counting Sort）
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;
}
9.桶排序（Bucket Sort）
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;
}
10.基数排序（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编码案例
array_list = [13, 27, 11, 18, 41, 25, 36, 29, -7, 111, 18, 33, -3]
# 所有的 n 表示局部判断次数、 n_ 表示局部赋值次数，所有的 i 表示全局判断次数、 i_ 表示全局赋值次数。
1.冒泡排序（Bubble Sort）
def bubble(array):
n = 0
n_ = 0
for _ in range(1, len(array)): # TODO：第一层 for 表示循环的遍数
for __ in range(0, len(array) - _): # TODO：第二层 for 表示具体比较哪两个元素
n += 1
if array[__] > array[__ + 1]: # TODO：如果前面的大于后面的
n_ += 1
array[__], array[__ + 1] = array[__ + 1], array[__] # TODO：交换这两个元素的位置
print(f'冒泡排序共判断 {n} 次，执行赋值 {n_} 次。')
return array
print(bubble(list(array_list)))
2.选择排序（Selection Sort）
def selection(array):
n = 0
n_ = 0
for _ in range(len(array) - 1): # TODO：第一层 for 表示循环的遍数
n_ += 1
__ = _ # TODO：将起始元素设为最小元素
for ___ in range(_ + 1, len(array)): # TODO：第二层 for 表示最小元素和后面的元素逐个比较
n += 1
if array[__] > array[___]: # TODO：如果当前元素比最小元素小
n_ += 1
__ = ___ # TODO：把当前元素角标标记为最小元素角标
n_ += 1
array[_], array[__] = array[__], array[_] # TODO：查找一遍后将最小元素与起始元素互换
print(f'选择排序共判断 {n} 次，执行赋值 {n_} 次。')
return array
print(selection(list(array_list)))
3.插入排序（Insertion Sort）
def insertion(array):
n = 0
n_ = 0
for _ in range(1, len(array)): # TODO：第一层 for 表示循环的遍数
n_ += 1
__ = array[_] # TODO：设置当前需要插入的元素
n += 1
while _ and array[_ - 1] > __: # TODO：当比较元素大于当前元素（此时变量 _ 被用于标记与当前元素比较的比较元素）
n += 1
n_ += 2
array[_] = array[_ - 1] # TODO：把比较元素后移
_ -= 1 # TODO：往前选择下一个比较元素
n_ += 1
array[_] = __ # TODO：当比较元素小于当前元素，则将当前元素插入在其后面
print(f'插入排序共判断 {n} 次，执行赋值 {n_} 次。')
return array
print(insertion(list(array_list)))
4.希尔排序（Shell Sort）
def shell(array, sep=2):
n = 0
n_ = 0
n_ += 1
_ = len(array) // sep # TODO：取整计算增量（间隔）值
n += 1
while _:
for __ in range(_, len(array)): # TODO：从增量值开始遍历比较
n_ += 1
___ = array[__] # TODO：设置当前需要插入的元素
n += 1
while __ - _ >= 0 and array[__ - _] > ___: # TODO：当比较元素大于当前元素（此时变量 __ 被用于标记与当前元素比较的比较元素）
n += 1
n_ += 2
array[__] = array[__ - _] # TODO：把比较元素后移
__ -= _ # TODO：往前选择下一个比较元素
n_ += 1
array[__] = ___ # TODO：当比较元素小于当前元素，则将当前元素插入在其后面
n_ += 1
_ //= sep # TODO：缩小增量（间隔）值
print(f'希尔排序共判断 {n} 次，执行赋值 {n_} 次。')
return array
print(shell(list(array_list)))
5.归并排序（Merge Sort）
i = 0
i_ = 0
# merge = lambda _: _ if len(_) == 1 else merge_sort(merge(_[:len(_) // 2]), merge(_[len(_) // 2:])) # TODO：使用递归运算二分法后的数列
# merge = lambda _: len(_) == 1 and _ or merge_sort(merge(_[:len(_) // 2]), merge(_[len(_) // 2:])) # TODO：使用递归运算二分法后的数列
def merge(array):
global i, i_
i += 1
if len(array) < 2:
return array
i_ += 2
return merge_sort(merge(array[:len(array) // 2]), merge(array[len(array) // 2:])) # TODO：使用递归运算二分法后的数列
def merge_sort(left, right):
global i, i_
i_ += 1
_ = [] # TODO：排序合并两个数列
i += 1
while left and right: # TODO：两个数列都有值
i += 2
i_ += 1
# _.append((lambda _, __: _[0] <= __[0] and _.pop(0) or __.pop(0))(left, right)) # TODO：左右两个数列第一个最小放前面【 _.append((lambda _, __: _.pop(0) if _[0] <= __[0] else __.pop(0))(left, right)) 】
if left[0] <= right[0]: # TODO：左右两个数列第一个最小放前面
_.append(left.pop(0))
else:
_.append(right.pop(0))
i_ += 1
_.extend(left and left or right) # TODO：只要数列中还有值，直接添加【 _ += left if left else right 】
return _
_ = merge(list(array_list))
print(f'归并排序共判断 {i} 次，执行赋值 {i_} 次。\n{_}')
6.快速排序（Quick Sort）
i = 0
i_ = 0
def quick(array):
global i, i_
i += 1
if len(array) < 2: # TODO：基线条件：为空或只包含一个元素的数组是“有序”的
return array
i += 2 * len(array[1:])
i_ += 2 * len(array[1:])
return quick([_ for _ in array[1:] if _ <= array[0]]) + [array[0]] + quick([_ for _ in array[1:] if _ > array[0]]) # TODO：由所有小于等于、基准元素、大于基准值的元素（递归条件）组成的子数组重新组合
_ = quick(list(array_list))
print(f'快速排序共判断 {i} 次，执行赋值 {i_} 次。\n{_}')
7.堆排序（Heap Sort）
i = 0
i_ = 0
def heap(array):
global i, i_
for _ in range(len(array) // 2, -1, -1):
array = heap_sort(array, _, len(array)) # TODO：从第一个非叶子结点从下至上，从右至左调整结构（构建大顶堆）
for __ in range(len(array) - 1, 0, -1):
i_ += 1
array[0], array[__] = array[__], array[0] # TODO：将堆顶元素与末尾元素进行交换
array = heap_sort(array, 0, __) # TODO：重新对堆进行调整（循环时候排序最后一个元素）
return array
def heap_sort(array, _, __): # TODO：堆调整
global i, i_
___ = _
i += 1
if 2 * _ + 1 < __ and array[2 * _ + 1] > array[___]: # TODO：找出较大的一个子节点（当左子结点较大）
i_ += 1
___ = 2 * _ + 1
i += 1
if 2 * _ + 2 < __ and array[2 * _ + 2] > array[___]: # TODO：找出较大的一个子节点（当右子结点较大）
i_ += 1
___ = 2 * _ + 2
i += 1
if ___ != _: # TODO：如果堆项有调整则再次递归
i_ += 2
array[_], array[___] = array[___], array[_] # TODO：将堆顶元素与末尾元素进行交换
heap_sort(array, ___, __) # TODO：重新对堆进行调整
return array
_ = heap(list(array_list))
print(f'堆排序共判断 {i} 次，执行赋值 {i_} 次。\n{_}')
8.计数排序（Counting Sort）
def counting(array):
n = 0
n_ = 0
n_ += 1 + 2 * (max(array) - min(array))
_ = [0] * len(array) # TODO：存放排序后的数组
__ = [array.count(_) for _ in range(min(array), max(array) + 1)] # TODO：通过下标索引，记录数中有哪些数字，相同值的共有几个
__ = [sum(__[:_]) for _ in range(1, len(__) + 1)] # TODO：数组中小于某个数的数字个数，用于排序
for ___ in array[::-1]:
n_ += 3
___ -= min(array) # TODO：针对负数与下标关系优化，使最小负数下标正好为 0
_[__[___] - 1] = ___ + min(array) # TODO：下标值为次序，还原负数与下标关系的优化
__[___] -= 1 # TODO：每插入一个数，当前下标就减一
print(f'计数排序共判断 {n} 次，执行赋值 {n_} 次。')
return _
print(counting(list(array_list)))
9.桶排序（Bucket Sort）
def bucket(array):
n = 0
n_ = 0
n_ += max(array) - min(array) + 1
_ = [] # TODO：存放排序后的数组
__ = [array.count(_) for _ in range(min(array), max(array) + 1)] # TODO：通过下标索引，记录数中有哪些数字，相同值的共有几个
for ___, ____ in enumerate(__):
for _____ in range(____): # TODO：执行数字出现次数次操作（对计数排序的优化）
n_ += 1
_.append(___ + min(array)) # TODO：下标值为次序，还原负数与下标关系的优化
print(f'桶排序共判断 {n} 次，执行赋值 {n_} 次。')
return _
print(bucket(list(array_list)))
10.基数排序（Radix Sort）
def radix(array):
n = 0
n_ = 0
n_ += len(array)
_ = [__ - min(array) for __ in array] # TODO：针对负数与下标关系优化，使最小负数下标正好为 0，构造没有负数的数组
for __ in range(len(str(max(_)))): # TODO：按最大数字长度做多轮操作，从个位到十位到百位...
n_ += 10
____ = [[] for _ in range(10)] # TODO：因为每一位数字都是 0-9 ，故建立10个桶
for ___ in _:
n_ += 1
____[int(___ / (10 ** __) % 10)].append(___) # TODO：按个位、十位、百位...放入桶中
n_ += 1
_ = [___ for __ in ____ for ___ in __] # TODO：按当前桶的顺序重排列表
print(f'基数排序共判断 {n} 次，执行赋值 {n_} 次。')
return [__ + min(array) for __ in _]
print(radix(list(array_list)))
Python十大经典排序类
说明：在上面的编码案例中，主要统计了每个排序方法判断以及赋值次数，用以表示详细的数据，接下来做出来的这个类，可以判断整个排序执行的时间，用以宏观表示各个函数执行的快慢，以现有默认值（最大递归深度设置10000，列表从-2000~2000中选5000个数）进行排序，这样几乎每个排序都会有用时且对我电脑不会出现栈溢出的情况。
import time
time_show = True # 是否显示执行时间
# 计算函数运行时长
def calc_time(decorator):
def calc(function=None, *arg, **kwargs):
if time_show:
start = time.time()
fun = decorator(function, *arg, **kwargs)
print(f'{decorator.__name__} 函数执行时间为：{time.time() - start:.3f}')
return fun
else:
return decorator(function, *arg, **kwargs)
return calc
# 通用处理数字列表值正确性的装饰器函数，如果传入值 array 有效，则替换实例属性 array
def check(function):
def num_array_check(self: object = None, array: list = None, *args: tuple, **kwargs: dict):
if array and isinstance(array, list) and set([type(a) for a in array]).issubset({int, float}):
self.array = array
elif hasattr(self, 'array'):
if self.array:
array = self.array
else:
raise ValueError("The valid list value is empty !")
else:
self.array = []
array = []
return function(self, array, *args, **kwargs)
return num_array_check
class Sort:
@check
# 数字列表选择性初始化
def __init__(self, array: list = None):
self.array = array
@check
@calc_time
# 冒泡排序（Bubble Sort）
def bubble(self, array: list = None):
for _ in range(1, len(array)): # TODO：第一层 for 表示循环的遍数
for __ in range(0, len(array) - _): # TODO：第二层 for 表示具体比较哪两个元素
if array[__] > array[__ + 1]: # TODO：如果前面的大于后面的
array[__], array[__ + 1] = array[__ + 1], array[__] # TODO：交换这两个元素的位置
return array
@check
@calc_time
# 选择排序（Selection Sort）
def selection(self, array: list = None):
for _ in range(len(array) - 1): # TODO：第一层 for 表示循环的遍数
__ = _ # TODO：将起始元素设为最小元素
for ___ in range(_ + 1, len(array)): # TODO：第二层 for 表示最小元素和后面的元素逐个比较
if array[__] > array[___]: # TODO：如果当前元素比最小元素小
__ = ___ # TODO：把当前元素角标标记为最小元素角标
array[_], array[__] = array[__], array[_] # TODO：查找一遍后将最小元素与起始元素互换
return array
@check
@calc_time
# 插入排序（Insertion Sort）
def insertion(self, array: list = None):
for _ in range(1, len(array)): # TODO：第一层 for 表示循环的遍数
__ = array[_] # TODO：设置当前需要插入的元素
while _ and array[_ - 1] > __: # TODO：当比较元素大于当前元素（此时变量 _ 被用于标记与当前元素比较的比较元素）
array[_] = array[_ - 1] # TODO：把比较元素后移
_ -= 1 # TODO：往前选择下一个比较元素
array[_] = __ # TODO：当比较元素小于当前元素，则将当前元素插入在其后面
return array
@check
@calc_time
# 希尔排序（Shell Sort）
def shell(self, array: list = None, sep: int = 2):
if not isinstance(sep, int):
sep = 2
_ = len(array) // sep # TODO：取整计算增量（间隔）值
while _:
for __ in range(_, len(array)): # TODO：从增量值开始遍历比较
___ = array[__] # TODO：设置当前需要插入的元素
while __ - _ >= 0 and array[__ - _] > ___: # TODO：当比较元素大于当前元素（此时变量 __ 被用于标记与当前元素比较的比较元素）
array[__] = array[__ - _] # TODO：把比较元素后移
__ -= _ # TODO：往前选择下一个比较元素
array[__] = ___ # TODO：当比较元素小于当前元素，则将当前元素插入在其后面
_ //= sep # TODO：缩小增量（间隔）值
return array
@check
@calc_time
# 归并排序（Merge Sort）—— 1
def merge(self, array: list = None):
return self.__merge(array)
# 归并排序（Merge Sort）—— 2
def __merge(self, array: list = None):
if len(array) < 2:
return array
return self.__merge_sort(self.__merge(array[:len(array) // 2]), self.__merge(array[len(array) // 2:])) # TODO：使用递归运算二分法后的数列
@staticmethod
# 归并排序（Merge Sort）—— 3
def __merge_sort(left, right):
_ = [] # TODO：排序合并两个数列
while left and right: # TODO：两个数列都有值
if left[0] <= right[0]: # TODO：左右两个数列第一个最小放前面
_.append(left.pop(0))
else:
_.append(right.pop(0))
_.extend(left and left or right) # TODO：只要数列中还有值，直接添加【 _ += left if left else right 】
return _
@check
@calc_time
# 快速排序（Quick Sort）—— 1
def quick(self, array: list = None):
return self.__quick(array)
# 快速排序（Quick Sort）—— 2
def __quick(self, array: list = None):
if len(array) < 2: # TODO：基线条件：为空或只包含一个元素的数组是“有序”的
return array
return self.__quick([_ for _ in array[1:] if _ <= array[0]]) + [array[0]] + self.__quick([_ for _ in array[1:] if _ > array[0]]) # TODO：由所有小于等于、基准元素、大于基准值的元素（递归条件）组成的子数组重新组合
@check
@calc_time
# 堆排序（Heap Sort）—— 1
def heap(self, array: list = None):
for _ in range(len(array) // 2, -1, -1):
array = self.__heap_sort(array, _, len(array)) # TODO：从第一个非叶子结点从下至上，从右至左调整结构（构建大顶堆）
for __ in range(len(array) - 1, 0, -1):
array[0], array[__] = array[__], array[0] # TODO：将堆顶元素与末尾元素进行交换
array = self.__heap_sort(array, 0, __) # TODO：重新对堆进行调整（循环时候排序最后一个元素）
return array
# 堆排序（Heap Sort）—— 2
def __heap_sort(self, array, _, __): # TODO：堆调整
___ = _
if 2 * _ + 1 < __ and array[2 * _ + 1] > array[___]: # TODO：找出较大的一个子节点（当左子结点较大）
___ = 2 * _ + 1
if 2 * _ + 2 < __ and array[2 * _ + 2] > array[___]: # TODO：找出较大的一个子节点（当右子结点较大）
___ = 2 * _ + 2
if ___ != _: # TODO：如果堆项有调整则再次递归
array[_], array[___] = array[___], array[_] # TODO：将堆顶元素与末尾元素进行交换
self.__heap_sort(array, ___, __) # TODO：重新对堆进行调整
return array
@check
@calc_time
# 计数排序（Counting Sort）
def counting(self, array: list = None):
_ = [0] * len(array) # TODO：存放排序后的数组
__ = [array.count(_) for _ in range(min(array), max(array) + 1)] # TODO：通过下标索引，记录数中有哪些数字，相同值的共有几个
__ = [sum(__[:_]) for _ in range(1, len(__) + 1)] # TODO：数组中小于某个数的数字个数，用于排序
for ___ in array[::-1]:
___ -= min(array) # TODO：针对负数与下标关系优化，使最小负数下标正好为 0
_[__[___] - 1] = ___ + min(array) # TODO：下标值为次序，还原负数与下标关系的优化
__[___] -= 1 # TODO：每插入一个数，当前下标就减一
return _
@check
@calc_time
# 桶排序（Bucket Sort）
def bucket(self, array: list = None):
_ = [] # TODO：存放排序后的数组
__ = [array.count(_) for _ in range(min(array), max(array) + 1)] # TODO：通过下标索引，记录数中有哪些数字，相同值的共有几个
for ___, ____ in enumerate(__):
for _____ in range(____): # TODO：执行数字出现次数次操作（对计数排序的优化）
_.append(___ + min(array)) # TODO：下标值为次序，还原负数与下标关系的优化
return _
@check
@calc_time
# 基数排序（Radix Sort）
def radix(self, array: list = None):
_ = [__ - min(array) for __ in array] # TODO：针对负数与下标关系优化，使最小负数下标正好为 0，构造没有负数的数组
for __ in range(len(str(max(_)))): # TODO：按最大数字长度做多轮操作，从个位到十位到百位...
____ = [[] for _ in range(10)] # TODO：因为每一位数字都是 0-9 ，故建立10个桶
for ___ in _:
____[int(___ / (10 ** __) % 10)].append(___) # TODO：按个位、十位、百位...放入桶中
_ = [___ for __ in ____ for ___ in __] # TODO：按当前桶的顺序重排列表
return [__ + min(array) for __ in _]
if __name__ == '__main__':
import sys
import random
time_show = True # 是否显示执行时间
# 设置最大递归深度，默认最大递归 1000 次，设置最大递归深度后有效递归深度跟python版本、cpu性能、操作系统等有关
sys.setrecursionlimit(10000)
# array_list = [13, 27, 11, 18, 41, 25, 36, 29, -7, 111, 18, 33, -3]
array_list = [random.randint(-2000, 2000) for _ in range(5000)]
print('待排序的列表')
print(array_list)
print(f'待排序列表长度：{len(array_list)}')
s = Sort(array_list)
s.bubble()
s.selection()
s.insertion()
s.shell()
s.merge()
s.quick()
s.heap()
s.counting()
s.bucket()
s.radix()
# print(s.bubble())
# print(s.selection())
# print(s.insertion())
# print(s.shell())
# print(s.merge())
# print(s.quick())
# print(s.heap())
# print(s.counting())
# print(s.bucket())
# print(s.radix())
测试结果
这里执行了3次，可以发现，插入排序几乎不消耗时间，其次就是希尔排序与归并排序，冒泡排序几乎是最费事的，基数排序几乎是最不稳定的。
再看判断赋值次数情况，这里执行了2次，当然肯定不准，因为我看着看着就明白没把列表推导式里的赋值算进去了，不然最后三种非比较排序执行次数这么少可能时间还用那么久。我们看到插入排序赋值次数最多，这里猜测赋值操作几乎不消耗时间。
结束语
这是我今年（2021年）发表的最后也是最长的一篇博客了，我对JavaScript不太熟，所以并没有测试JavaScript，就拿Python来开刀。本篇博客到此结束了，希望喜欢的能一键三连，提前祝大家：新年快乐！