在面试题中可能会遇到排序算法,毕竟作为程序员内功心法,熟练掌握排序算法是很重要的,本文总结了八大经典排序算法的 Python 实现。排序算法是《数据结构与算法》中最基本的算法之一。排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。
名词解释:
关于时间复杂度:
关于稳定性:
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢 “浮” 到数列的顶端。 这个算法的名字由来是因为越小的元素会经由交换慢慢 “浮” 到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名 “冒泡排序”。
算法原理:
动图演示过程如下:
算法实现:
def bubble_sort(nums):
for pass_num in range(len(nums) - 1, 0, -1): # n-1趟
flag = True # 每一趟置flag为True
for i in range(pass_num):
if nums[i] > nums[i + 1]:
nums[i], nums[i + 1] = nums[i + 1], nums[i]
flag = False # 有交换:flag置为False
# 每一趟结束后大的数会往后冒泡
# flag为True 说明到这趟已经没有交换 提前跳出循环 提高算法效率
# print(nums)
if flag:
break
return nums
s = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
print(s)
print(bubble_sort(s))
# 结果如下:
[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
算法原理:
动图演示如下:
算法实现:
def select_sort(nums):
for pass_num in range(len(nums) - 1, 0, -1): # n-1趟
pos_max = 0
for location in range(1, pass_num + 1):
if nums[location] > nums[pos_max]:
pos_max = location
# 每一趟只交换一次
nums[pass_num], nums[pos_max] = nums[pos_max], nums[pass_num]
return nums
s = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
print(s)
print(select_sort(s))
# 结果如下:
[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。
算法原理:
动态图演示如下:
算法实现:
def insert_sort(arr):
for index_ in range(1, len(arr)):
position = index_
current_value = arr[index_] # 插入项
# 比对 移动 直到找到第一个比它小的项
while position > 0 and arr[position - 1] > current_value:
arr[position] = arr[position - 1]
position = position - 1
# 插入新项
arr[position] = current_value
return arr
s = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
print(s)
print(insert_sort(s))
# 结果如下:
[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是不稳定排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的:
算法原理:
动图演示如下:
算法实现:
def shell_sort(nums):
n = len(nums)
gap = n // 2 # 定义增量
# gap等于1的时候相当于最后一步是一插入排序
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 //= 2
return nums
s = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
print(shell_sort(s))
# 结果如下:
# [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法:
和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。
算法原理:
动态图演示如下:
算法实现:
from math import floor
def merge_sort(arr):
if(len(arr) < 2):
return arr
# 二分
middle = floor(len(arr) / 2)
left, right = arr[0:middle], arr[middle:]
# 递归
return merge(merge_sort(left), merge_sort(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
s = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
print(merge_sort(s))
# 结果如下:
# [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
快速排序的名字起的是简单粗暴,因为一听到这个名字你就知道它存在的意义,就是快,而且效率高!它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²),但是人家就是优秀,在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好。查阅资料了解到:快速排序的最坏运行情况是 O(n²),比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn),且 O(nlogn) 记号中隐含的常数因子很小,比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。
算法原理
递归的最底部情形,是数列的大小是0或1,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
动态图演示如下:
算法实现:
def quick_sort(arr, left=None, right=None):
left = 0 if not isinstance(left,(int, float)) else left
right = len(arr) - 1 if not isinstance(right,(int, float)) else right
if left < right:
partitionIndex = partition(arr, left, right)
quick_sort(arr, left, partitionIndex - 1)
quick_sort(arr, partitionIndex + 1, right)
return arr
def partition(arr, left, right):
pivot = left
index = pivot + 1
i = index
while i <= right:
if arr[i] < arr[pivot]:
swap(arr, i, index)
index += 1
i+=1
swap(arr, pivot, index - 1)
return index - 1
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
s = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
print(quick_sort(s))
# 结果如下:
# [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:
算法原理:
动态图演示如下:
算法实现:
from math import floor
def buildMaxHeap(arr):
for i in range(floor(len(arr)/2), -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 heap_sort(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
s = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
print(heap_sort(s))
# 结果如下:
# [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。 三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异案例看大家发的:
基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。
算法原理:
动图演示如下:
算法实现:
def radix_sort(nums):
# 算n:为了计算最高位
max_num = max(nums)
n = 1
while max_num > 10 ** n:
n += 1
for 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
s = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
print(radix_sort(s))
# 结果如下:
# [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]