python实现常用排序
一直以来，对于排序都是比较零散的去学习和了解，用到什么就去查什么，本次决定把集中排序汇总记录下。（使用python是觉得语法更加灵活，可以省很多代码说明，还可验证结果）
首先，我们最先接触到也是最好理解的排序--冒泡排序
冒泡排序就是循环取元素，然后往后比较，如果大于后面元素则交换位置，直到比较到最后一个，重复操作，直到所有元素都比较完成，即得到排序结果
代码实现也比较简单，主要如下：
oldArr = [3, 4, 6, 2, 1, 4, 9, 10]
# 冒泡排序
def bubble_sort(arr):
for i in range(len(arr) - 1):
for j in range(len(arr) - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
print(bubble_sort(oldArr))
冒泡排序很简单，就是遍历比较大小交互位置即可
选择排序
核心思想是，从头至尾扫描序列，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序序列
def select_sort(arr):
for i in range(len(arr) - 1):
min_index = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_index]:
min_index = j
# 最小元素与起始元素调换位置
arr[min_index], arr[i] = arr[i], arr[min_index]
return arr
插入排序
# 从第二个元素开始和前面的元素进行比较，如果前面的元素比当前元素大，则将前面元素 后移，当前元素依次往前，直到找到比它小或等于它的元素插入在其后面
# 然后选择第三个元素，重复上述操作，进行插入
# 依次选择到最后一个元素，插入后即完成所有排序
def insert_sort(arr):
for i in range(len(arr)):
# 插入元素
current = arr[i]
# 比较元素
pre_index = i - 1
while pre_index >= 0 and arr[pre_index] > current:
arr[pre_index + 1] = arr[pre_index]
pre_index -= 1
arr[pre_index + 1] = current
return arr
希尔排序
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 =1( < …<d2<d1)，
即所有记录放在同一组中进行直接插入排序为止。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
def shell_sort(arr):
gap = len(arr) // 2
while gap > 0:
for i in range(gap, len(arr)):
j = i
current = arr[i]
while j - gap >= 0 and current < arr[j - gap]:
arr[j] = arr[j - gap]
j -= gap
arr[j] = current
gap //= 2
return arr
归并排序
是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组
def merge_sort(arr):
if len(arr) <= 1:
return arr
num = len(arr) // 2
left = merge_sort(arr[:num])
right = merge_sort(arr[num:])
return merge(left, right)
def merge(left, right):
l, r = 0, 0
result = []
while l < len(left) and r < len(right):
if left[l] < right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result += left[l:]
result += right[r:]
return result
快速排序
# 1.选出第一个元素
# 2.遍历每个元素，也就是从第二个开始拿，如果比第一个元素小，放到一个新数组里；如果比它大，放到另一个数组；
# 3.对两个新数组执行同样的操作
def quick_sort(arr):
if len(arr) < 2:
return arr
base = arr[0]
less = [i for i in arr[1:] if i < base]
greater = [i for i in arr[1:] if i >= base]
return quick_sort(less) + [base] + quick_sort(greater)
堆排序
def heap_sort(arr):
n = len(arr)
first = int(n / 2 - 1) # 最后一个非叶子节点
for start in range(first, -1, -1): # 构造大根堆
max_heapify(arr, start, n - 1)
for end in range(n - 1, 0, -1): # 堆排，将大根堆转换成有序数组
arr[end], arr[0] = arr[0], arr[end]
max_heapify(arr, 0, end - 1)
return arr
# 最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
# start为当前需要调整最大堆的位置，end为调整边界
def max_heapify(ary, start, end):
root = start
while True:
child = root * 2 + 1 # 调整节点的子节点
if child > end:
break
if child + 1 <= end and ary[child] < ary[child + 1]:
child = child + 1 # 取较大的子节点
if ary[root] < ary[child]: # 较大的子节点成为父节点
ary[root], ary[child] = ary[child], ary[root] # 交换
root = child
else:
break
效率比较：冒泡=插入=选择=O(n2) 希尔=归并=快速=堆=O(nlog n)
以上是 python实现常用排序 的全部内容， 来源链接： utcz.com/z/389031.html
