Python中实现排序算法的函数
Python作为一种最流行的编程语言之一，提供了许多内置的排序算法函数，同时也支持自定义实现排序算法的函数。本文将介绍Python内置的排序算法函数以及实现排序算法的函数。
一、Python内置的排序算法函数
Python内置了一些常见的排序算法函数，主要有sorted和sort两个函数。
sorted函数
sorted(iterable, *, key=None, reverse=False)
该函数接受一个可迭代对象作为参数，返回一个新的已排序的列表。默认按照元素的大小进行升序排列，也可以通过key参数指定自定义的排序规则。参数reverse=True可以指定降序排序。
示例：
# 默认升序排序
a = [3, 1, 4, 2, 5]
b = sorted(a)
print(b) # [1, 2, 3, 4, 5]
# 按照绝对值升序排序
a = [-3, 1, -4, 2, -5]
b = sorted(a, key=abs)
print(b) # [1, 2, -3, -4, -5]
# 按照字符串长度降序排序
a = ["hello", "world", "python", "is", "great"]
b = sorted(a, key=len, reverse=True)
print(b) # ["python", "hello", "world", "great", "is"]
sort方法
list.sort(*, key=None, reverse=False)
该方法是list类的一个方法，排序后的结果直接影响原数组。和sorted函数一样，也可以通过key参数和reverse参数自定义排序规则。
示例：
# 默认升序排序
a = [3, 1, 4, 2, 5]
a.sort()
print(a) # [1, 2, 3, 4, 5]
# 按照绝对值升序排序
a = [-3, 1, -4, 2, -5]
a.sort(key=abs)
print(a) # [1, 2, -3, -4, -5]
# 按照字符串长度降序排序
a = ["hello", "world", "python", "is", "great"]
a.sort(key=len, reverse=True)
print(a) # ["python", "hello", "world", "great", "is"]
二、自定义实现排序算法的函数
除了使用Python内置的排序算法函数外，我们还可以自己实现排序算法的函数。下面介绍一些常见的排序算法及其Python实现。
冒泡排序
冒泡排序是一种简单的排序算法，基本思路是不断交换相邻两个元素的位置，将最大的元素逐渐"冒泡"到最后。
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
插入排序
插入排序的基本思想是：将未排序的元素逐个插入到已排序的序列中。插入排序分为直接插入排序和希尔排序两种。
直接插入排序
直接插入排序的实现方式类似于打扑克牌时，手中的牌不断加入到已排序的牌中。
def insert_sort(arr):
n = len(arr)
for i in range(1, n):
j = i - 1
key = arr[i]
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
希尔排序
希尔排序的基本思想是将数据分组，每组进行直接插入排序，然后逐渐缩小组的大小，直到组大小为1，完成排序。
def shell_sort(arr):
n = len(arr)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 2
快速排序
快速排序是一种高效的排序算法，基本思路是先选定一个基准元素，将数组中小于基准元素的部分全部放到左边，大于等于基准元素的部分全部放到右边，然后对左右两个部分递归进行快速排序，直到排序完成。
def quick_sort(arr, left, right):
if left >= right:
return
pivot = arr[right]
i = left - 1
for j in range(left, right):
if arr[j] < pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[right] = arr[right], arr[i + 1]
quick_sort(arr, left, i)
quick_sort(arr, i + 2, right)
归并排序
归并排序是一种分治算法，同样也是一种效率较高的算法。它的基本思想是将待排数组分成两半，对每一半分别进行归并排序，然后将两个已排序的数组归并成一个有序的数组。
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
三、总结
本文介绍了Python内置的排序算法函数sorted和sort以及自定义实现排序算法的函数。不同的排序算法适用于不同的场景，选择合适的排序算法能够提高程序效率。在实际应用中，我们可以根据排序的数据规模、数据类型以及时间复杂度等因素来选择适合的排序算法。