- 归并排序(merge sort)
- 插入排序(insertion sort)
- 堆排序(heapSort)
- 桶排序(BucketSort):
- 代码
- 参考
1. eg: input '[3, 44, 38, 5, 47, 15, 36]' sorted: '[3, 5, 15, 36, 38, 44, 47]'
2. 手推排序: （从小到大排）
3, 44, 38, 5, 47, 15, 36
step1: 两两比较
3, 44, ... ... (其他不变/先忽略)
3, 44| 5, 38, ... ...
step2: 进行了两组两两比较后, 比较这两组
先比较两组最小的[下标小的], 记为1组和2组:
- 3<5, 1组的3输出: 3
- 将5与1组的下一个比较: 44>5, 2组的5输出: 3, 5
- 将44与2组的下一个比较: 44>38, 2组的38输出: 3, 5, 38
- 只剩1组的1个数: 44, 直接输出: 3, 5, 38, 44
step3: step2完成了前4个数的排序, 同理进行后面的:
3, 5, 38, 44 | 47, 15, 36
- 先将后面3个数分组两两比较:
47, 15 | 36
15, 47 | 36
- 再比较1组的第一个数，和2组的第一个数: 15 < 36, 15输出: 15
- 将36与1组的下一个数比较: 36<47, 36输出: 15, 36
- 只剩下1组的47, 直接输出: 15, 36, 47
至此，分组排序的结果是: 3, 5, 38, 44 | 15, 36, 47
step4: 和step2/step3相同的比较方法，将竖线两端（视为两组）进行比较排序：
> 从两组最小的两个数开始, 输出小的数, 大的数与另一组的下一个比较:
- 3<15, 输出: 3
- 将15和5比较 5<15, 输出: 3, 5
- 将15和38比较 15<38, 输出: 3, 5, 15
- 38和36比较 38 > 36, 输出: 3, 5, 15, 36
- ... ...
- 依次比较, 最终输出: 3, 5, 15, 36, 38, 44, 47
3. 代码解释:
- "merge(left,right)": 对两组数中，两两元素的比较; 每次比较把较小的值输出并从该值所属的列表中删除。
- "mergeSort(arr)": 将输出的一个数值列表(数组), 递归进行二等分, 直到列表的长度<2(即列表只有1个元素)，这里每一次的二等分都会调用"merge(left, right)"。
插入排序(insertion sort)
1. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。 2. 代码中: 默认排序的同时改变原来的列表堆排序(heapSort)
- step1: 构建堆, 调整堆节点的每个三角(从右往左)按父节点大于子节点排序; - step2: 堆顶(堆首)即为最大值, 输出最大值; 把堆尾(最小值)放在堆顶, 调整堆大小(三角关系满足父节点比子节点大); - step3: 重复step2, 直到堆只有一个元素, 按顺序输出的值，即为从大到小排列的数组。桶排序(BucketSort):
- step1: 根据输入数组中最大数m，构建m+1个元素为0的列表, eg: m=5, 构建的列表: [0]*6 - step2: 遍历输入数组，元素数值对应构建列表的下标，比如输入数值是[2,5,3,3]，则构建列表更新为: [0, 0, 1, 2, 0, 1] - step3: 根据更新的列表, 遍历输出排序后的数值: 2,3,3,5代码
# https://sort.hust.cc
import copy
# ==============
# insertion sort
# ==============
def insertionSort(r_arr, copy_a=False):
if copy_a:
arr = copy.deepcopy(r_arr)
else:
arr = r_arr
len_arr = len(arr)
for i in range(len_arr):
preIndex = i-1
current = arr[i]
while preIndex >= 0 and arr[preIndex] > current:
arr[preIndex+1] = arr[preIndex]
preIndex-=1
arr[preIndex+1] = current
return arr
# ==========
# merge sort
# ==========
def mergeSort(arr):
import math
if(len(arr)<2):
return arr
middle = int(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
# =========
# Heap sort
# =========
def buildMaxHeap(arr):
import math
half_len = int(math.floor(len(arr)/2))
for i in range(half_len,-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(r_arr, copy_a=False):
if copy_a:
arr = copy.deepcopy(r_arr)
else:
arr = r_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
# ===========
# bucket sort
# ===========
def bucketSort(arr):
max_a = max(arr)
len_bk = max_a + 1
bucket = [0] * len_bk
for i in arr:
bucket[i] += 1
# print(len_bk, bucket)
sort_arr = []
for j in range(len_bk):
if bucket[j] != 0:
sort_arr.extend([j]*bucket[j])
return sort_arr
if __name__ == '__main__':
# lst = [3, 44, 38, 5, 47, 15, 36]
lst = [3, 5, 44, 38, 5, 47, 15, 36]
print("#SorttInputtOutput")
mgsort_lst = mergeSort(lst) # not change original list
print("mergeSortt%st%s" % (lst, mgsort_lst))
inssort_lst = insertionSort(lst, copy_a=True) # default change original list
print("insertionSortt%st%s" % (lst, inssort_lst))
heapsort_lst = heapSort(lst, copy_a=True) # default change original list
print("heapSortt%st%s" % (lst, heapsort_lst))
bksort_lst = bucketSort(lst)
print("bucketSortt%st%s" % (lst, bksort_lst))
参考
十大经典排序算法
参考的文章中有动图演示各种排序算法，更能直观理解。
