![](https://csdnimg.cn/release/download_crawler_static/86280326/bg1.jpg)
GitHub:https://github.com/Max-Liuhu/keeplearning
排序篇排序篇
二路归并排序二路归并排序
介绍
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并,得
到完全有序的序列;即先使每个子序列有序,再使子序列段 间有序。若将两个有序表合并成一个有序表,称为2-路归并。
算法思路
i. 把长度为n的输入序列分成两个长度为n/2的子序列;
ii. 对这两个子序列分别采用归并排序;
iii. 将两个排序好的子序列合并成一个最终的排序序列。
复杂度与稳定性
空间复杂度:
时间复杂度:
最佳情况:最佳情况:T(n) = O(n)
最差情况:T(n) = O(nlogn)
平均情况:T(n) = O(nlogn)
属于稳定性排序
代码
def merge_array(L, first, mid, last, temp):
"""
合并的函数,合并数组
# 将序列L[first...mid]与序列L[mid+1...last]进行合并
"""
# 对i,j,k分别进行赋值
i, j, k = first, mid + 1, 0
# 当左右两边都有数时进行比较,取较小的数
while i <= mid and j <= last:
if L[i] <= L[j]:
temp[k] = L[i]
i += 1
else:
temp[k] = L[j]
j += 1
k += 1
# 以下两个while只会执行两个
# 如果左边序列还有数
while i <= mid:
temp[k] = L[i]
i += 1
k += 1
# 如果右边序列还有数
while j <= last:
temp[k] = L[j]
j += 1
k += 1
# 将temp当中该段有序元素赋值给L待排序列使之部分有序
for x in range(0, k):
L[first + x] = temp[x]
def divide_array(L, first, last, temp):
"""分组"""
if first < last:
mid = (int)((first + last) / 2)
# 使左边序列有序
divide_array(L, first, mid, temp)
# 使右边序列有序
divide_array(L, mid + 1, last, temp)
# 将两个有序序列合并
merge_array(L, first, mid, last, temp)
# 归并排序的函数
def merge_sort(L):
# 声明一个长度为len(L)的空列表
temp = len(L) * [None]
# 调用归并排序
divide_array(L, 0, len(L) - 1, temp)
return L</code></pre></li>
基数排序基数排序
介绍
基数排序也是非比较的排序算法,对每一位进行排序,从最低位开始排序,复杂度为O(kn),为数组长度,k为数组中的数的最大的位数
算法思路
i. 取得数组中的最大数,并取得位数;
ii. arr为原始数组,从最低位开始取每个位组成radix数组;
iii. 对radix进行计数排序(利用计数排序适用于小范围数的特点);
复杂度与稳定性
空间复杂度:O(k),辅助空间需要k个队列
时间复杂度: