sorts

bubble_sort

dramkit.sorts.bubble_sort.bubble_sort(nums_ori, ascending=True)

冒泡排序算法: 比较两个相邻的元素，将值大的元素交换到右边(升序情况)

Note

时间复杂度O(n^2)，n为待排序数的个数
缺点：时间复杂度高
优点: 不像桶排序那样只能排正整数

Parameters:

nums_ori (list) – 待排序数列表
ascending (bool) – 是否升序，默认True

Returns:

list - 返回排序之后的数据列表

bucket_sort

dramkit.sorts.bucket_sort.bucket_sort(nums, ascending=True)

桶排序算法

Note

时间复杂度O(m+n)，m为桶的个数(nums的最大值+1)，n为待排序数的个数
缺点：
- 需要事先知道最大最小值
- 浪费空间（桶的个数受最大值影响极大）
- 小数点和负数处理麻烦(可通过转化成正整数再排序)
优点: 时间复杂度低

Parameters:

nums (list) – 待排序数列表
ascending (bool) – 是否升序，默认True

Returns:

list - 返回排序之后的数据列表

insert_sort

插入排序

Todo

待排序数组中存在无效值的处理

insert_sort

dramkit.sorts.insert_sort.insert_sort(nums_ori, ascending=True)

插入排序法：将未排序的数据依次插入到有序序列中

Note

时间复杂度最坏为O(n^2)，最好为O(n)，n为待排序数的个数

Parameters:

nums_ori (list) – 待排序数组
ascending (bool) – 是否升序排列

Returns:

list - 返回排序之后的数据列表

References

https://blog.csdn.net/weixin_43790276/article/details/104033635

insert_to_sorted

dramkit.sorts.insert_sort.insert_to_sorted(nums_sorted, num, ascending=True): 在已经排序好的nums_sorted (list)中插入num并排序

返回加入新数据并排序之后的列表

rank_of_insert

dramkit.sorts.insert_sort.rank_of_insert(nums_sorted, ranks, num, ascending=True, method='dense'): 在排好序的nums_sorted中插入新元素num，并返回num的排序号

ranks为已经排好序的nums_sorted的序号列表

method意义同pandas中rank的method参数

返回顺序：num的排序号, (排好的新序列列表, 排好的新序列号列表)

insert_sort_bin

二分法改进的插入排序法

Todo

待排序数组中存在无效值的处理

References

https://cuijiahua.com/blog/2017/12/algorithm_2.html

bin_search

dramkit.sorts.insert_sort_bin.bin_search(nums_sorted, num, start=None, end=None, ascending=True)

二分法查找num应该插入到排序好的nums_sorted中的位置

Parameters:

nums_sorted (list) – 已经排序好的数据列表
num – 待插入数据
start (None, int) – 指定查找开始位置，默认为开头
end (None, int) – 指定查找结束位置，默认为结尾
ascending (bool) – 设置是否为升序排列

Note

nums_sorted和num中均不能有无效值

insert_sort_bin

dramkit.sorts.insert_sort_bin.insert_sort_bin(nums_ori, ascending=True)

二分法改进的插入排序法

Parameters:

nums_ori (list) – 待排序数组
ascending (bool) – 是否升序排列

Returns:

list - 返回排序之后的数据列表

rank_of_insert_bin

dramkit.sorts.insert_sort_bin.rank_of_insert_bin(nums_sorted, ranks, num, ascending=True, method='dense'): 在排好序的nums_sorted中插入新元素num，并返回num的排序号，用二分法改进

ranks为已经排好序的nums_sorted的序号列表

method意义同pandas中rank的method参数

返回顺序：num的排序号, (排好的新序列列表, 排好的新序列号列表)

Note

nums_sorted和num中均不能有无效值

quick_sort

dramkit.sorts.quick_sort.quick_sort(nums_ori, ascending=True)

快速排序算法: 取一个基数，大于和小于基数的书分别放两边，两边再递归

Note

时间复杂度O(N*logN)，N为待排序数的个数

Parameters:

nums_ori (list) – 待排序数列表
ascending (bool) – 是否升序，默认True

Returns:

list - 返回排序之后的数据列表