使用 Python 实现几种常见的排序算法
排序是非常常见的算法，今天就来分享几种常见排序算法的 Python 实现
冒泡排序
冒泡排序是最为基础的排序算法，其核心思想就是相邻元素两两比较，把较大的元素放到后面，在一轮比较完成之后，最大的元素就位于最后一个位置了，就好像是气泡，慢慢的浮出了水面一样。
def bubble_sort(data, reverse=False):
"""
:param data: list type data
:param reverse:
:return: list type data
"""
if not reverse:
for i in range(len(data) - 1):
for j in range(len(data) - 1 -i):
if data[j] > data[j+1]:
data[j], data[j+1] = data[j+1], data[j]
return data
else:
for i in range(len(data) - 1):
for j in range(len(data) - 1 -i):
if data[j] < data[j+1]:
data[j], data[j + 1] = data[j + 1], data[j]
return data其实冒泡排序算法还是比较好理解的，只需要进行两次循环，最外层的循环代表排序元素的个数，内部循环则进行两两比较，时间复杂度为 O(n^2)。
选择排序
选择排序，是逐个确定元素位置的思想。同样是 n 遍循环，第一轮时，每一个元素都与第一个元素比较，如果比第一个元素大，则与之交换，这样一轮过后，第一个元素就是最小的了，第二轮开始每个元素与第二个位置的元素比较，如果大，则与第二位置的元素交换，以此类推，达到排序的目的
def selection_sort(data, reverse=False):
"""
:param data: list type data
:param reverse:
:return: list type data
"""
if not reverse:
for i in range(len(data)-1):
min_index = i
for j in range(i+1, len(data)):
if data[j] < data[min_index]:
min_index = j
data[i], data[min_index] = data[min_index], data[i]
return data
else:
for i in range(len(data) - 1):
min_index = i
for j in range(i+1, len(data)):
if data[j] > data[min_index]:
min_index = j
data[i], data[min_index] = data[min_index], data[i]
return data选择排序和冒泡排序还是很相似的，但是选择排序会比冒泡排序少一次交换的过程，但是同样是两层循环，所有时间复杂度也是 O(n^2)
插入排序
插入排序的思想是把一个数据插入到一个有序序列中，从而得到一个新的序列加一的有序序列，可以通过下图来进一步加深理解
def insert_sort(data, reverse=False):
if not reverse:
for i in range(1, len(data)):
key = data[i]
j = i - 1
while j >= 0:
if data[j] > key:
data[j+1] = data[j]
data[j] = key
j -= 1
return data
else:
for i in range(1, len(data)):
key = data[i]
j = i - 1
while j >= 0:
if data[j] < key:
data[j+1] = data[j]
data[j] = key
j -= 1
return data由于每次遍历有序序列时，都会有序列中所有的数据做对比，故而时间复杂度为O(n^2)
快速排序
快排的思想为首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序，之后再递归排序两边的数据。
def quick_sort(data):
if not data:
return data
first = data[0]
left = quick_sort([l for l in data[1:] if l < first])
right = quick_sort([r for r in data[1:] if r >= first])
return left + [first] + right好了，今天的分享就到这里了。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-03-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录