1、写在前面的话
本篇博客并不涉及到排序算法的理论讲解，具体理论可以参考reference的链接，并且强烈推荐数据结构和算法的可视化网站【0】。本文给出八种经典的排序算法的Python实现代码和部分注解，算是一个总结，也感谢网络众多优秀的博主分享他们的idea，站在巨人的肩膀上果然成长很迅速。排序可以说在经典算法中是很重要的一部分，对于常见的排序算法要做到本能的敲出代码，了解各种算法的时间复杂度和空间复杂度，关于时间复杂度和空间复杂度具体可以参考【1】。对于外部排序和线性时间的排序也请参考reference的链接。对于稳定性的判断，请记住口诀，不稳定：快选堆希稳定：插冒归基。
2、Show me the code
冒泡排序：
def bubble(nums):
if not isinstance(nums, list) or not nums:
return -1
#i控制几趟
for i in range(1, len(nums)):
# len(nums)-i因为最后有排好的数字
for j in range(0, len(nums)-i):
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
return nums
选择排序:
def select(nums):
if not isinstance(nums, list) or not nums:
return -1for i in range(len(nums)-1):
min_index = i
# i+1 是开始从i之后的元素找到最小值，并用minindex标记上
for j in range (i+1, len(nums)):
if nums[j] < nums[min_index]:
min_index = j
#如果和最开始的标记的最小元素不等，就交换两个元素
if min_index != i:
nums[i], nums[min_index] = nums[min_index], nums[i]
return nums插入排序：
def insertionSort(nums):
if not isinstance(nums, list) or not nums:
return -1#i是控制处理的第几个元素
for i in range(1,len(nums)):
for j in range(i, 0, -1):
# 如果比前面的元素小，则往前移动
if nums[j] < nums[j-1]:
nums[j], nums[j-1] = nums[j-1], nums[j]
# 否则代表比前面的所有元素都小，不需要再移动
else:
break
return nums【Python|Python实现八大经典排序算法】希尔排序：
def shell_sort(nums):
if not isinstance(nums, list) or not nums:
return -1n = len(nums)
gap = n//2#定义增量
#gap等于一的时候相当于最后一步是一插入排序
while gap >=1:
for j in range(gap, n):
i = j
#增量的插入排序版本
while (i-gap)>=0:
if nums[i] < nums[i-gap]:
nums[i], nums[i-gap] = nums[i-gap], nums[i]
i -= gap
else:
break
gap //=2return nums快速排序:
def quick_sort(nums, start, end):
if start >= end:
return
pivot = nums[start]
left = start
right = end
while left < right:
while left < right and nums[right] >= pivot:
right -= 1
nums[left] = nums[right]
while left < right and nums[left] < pivot:
left += 1
nums[right] = nums[left]
nums[left] = pivotquick_sort(nums, start, left-1)
quick_sort(nums, left+1, end)
return numsdef quick_sort(nums):
if len(nums) < 2:
return nums
else:
midpivot = nums[0]
less_before_midpivot = [i for i in nums[1:] if i <= midpivot]
bigger_before_midpivot = [i for i in nums[1:] if i > midpivot]
finnal_nums = quick_sort(less_before_midpivot) + [midpivot] + quick_sort(bigger_before_midpivot)
return finnal_nums归并排序：
def merge_sort(nums):
if not isinstance(nums, list) or not nums:
return -1n = len(nums)
if n == 1:
return nums
mid = n//2
left_list = merge_sort(nums[: mid])
right_list = merge_sort(nums[mid:])
return merge(left_list, right_list)def merge(left_list, right_list):
left , right =0, 0
merge_result = []
while left < len(left_list) and right < len(right_list):
if left_list[left] <= right_list[right]:
merge_result.append(left_list[left])
left += 1
else:
merge_result.append(right_list[right])
right += 1
merge_result += left_list[left:]
merge_result += right_list[right:]return merge_result堆排序：
#nums的0位是无效
def heap_sort(nums):
N = len(nums)-1
buildHeap(nums)
for i in range(1,N):
deleteMin(nums, N+1-i)
return nums[:0:-1]def deleteMin(nums, heap_size):
swap(nums, 1, heap_size)
heap_size -=1
sink(nums, 1, heap_size)def buildHeap(nums):
heap_size = len(nums) -1
for i in range(heap_size//2 ,0 ,-1):
sink(nums, i, heap_size)def sink(nums, parentIndex, heap_size):
if parentIndex*2 > heap_size:
return
minNodeIndex = minIndex(nums, parentIndex, heap_size)
if minNodeIndex != parentIndex:
swap(nums, minNodeIndex, parentIndex)
sink(nums, minNodeIndex, heap_size)def swap(nums, i , j):
nums[i] , nums[j] = nums[j], nums[i]def minIndex(nums, parentIndex, heap_size):
minIndex = parentIndex
leftIndex = 2*parentIndex
if leftIndex <= heap_size:
minIndex = leftIndex if nums[leftIndex] < nums[parentIndex] else parentIndex
rightIndex = 2*parentIndex+1
if rightIndex <= heap_size:
minIndex = rightIndex if nums[rightIndex] < nums[minIndex] else minIndex
return minIndex基数排序：
def RadixSort(nums):
#就算n为了计算最高位
max_num = max(nums)
n = 1
while max_num > 10**n:
n += 1for k in range(n):
#初始化0-9个桶来排序呢
buckets = [[] for i in range(10)]
for subnum in nums:
buckets[int(subnum/(10**k)%10)].append(subnum)
nums = [num for bucket in buckets for num in bucket ]
return nums
【0】https://visualgo.net/zh
【1】时间复杂度和空间复杂度速查表
【2】图解冒泡排序
【3】图解选择排序
【4】图解插入排序
【5】图解希尔排序
【6】图解快速排序
【7】图解归并排序
【9】图解堆排序
【10】图解基数排序
【11】 Python的线性时间排序--计数排序 桶排序 基排序
【12】外部排序
【13】github动图图解十大排序算法
如果图解的链接失效的话，请自行到微信公众号“趣谈编程”上自己查看（用搜狗微信搜索功能就可以直接搜）
推荐阅读
- 数据结构|二叉树需要掌握的基本知识
- 算法初探|八大经典排序算法（java）
- 排序算法|Java实现十大经典排序算法--上
- 数据结构|八大经典排序算法
- 数据仓库|数据仓库也SaaS，Snowflake市值缘何超700亿美元（）
- python|snowflake 数据库_Snowflake数据分析教程
- 前端|JavaScript基础大总结
- Pytorch|Pytorch丨expand函数
- PyTorch自定义损失函数