用Python实现常见的排序函数
Python是一门强大且易学的编程语言，它是一种高级编程语言，广泛应用于数据科学、机器学习、人工智能等领域。常见的排序算法是计算机科学中的基本算法之一，对于Python来说也同样适用。Python中提供了很多自带的排序函数，如sort()、sorted()等。本文将介绍几种常见的排序算法及其Python实现。
1.冒泡排序
冒泡排序是最简单的排序算法之一，它比较相邻的元素，如果它们的顺序不对就交换它们的位置，并继续下一轮比较，最终将最大的元素移到最后一位。该算法的复杂度为O(n2)。
Python实现：
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
2.选择排序
选择排序是一种简单的排序算法，它从未排序的元素中选择最小的元素，并放到已排序的末尾。该算法的复杂度为O(n2)。
Python实现：
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
3.插入排序
插入排序是一种将未排序元素插入到已排序部分的排序算法。 它将一个元素插入到有序数组中的正确位置，以便继续对其余元素进行排序。该算法的复杂度为O(n2)。
Python实现：
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i-1
while j >= 0 and key < arr[j] :
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
4.快速排序
快速排序是一种基于分治思想的排序算法，它将一个大问题分解成若干个小问题，并递归解决。该算法的复杂度为O(nlogn)。
Python实现：
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr)//2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
5.归并排序
归并排序是一种基于分治思想的排序算法。它将一个大问题分解成若干个小问题，并将小问题合并为一个有序数组。该算法的复杂度为O(nlogn)。
Python实现：
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
def merge(left, right):
res = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
res.append(left[i])
i += 1
else:
res.append(right[j])
j += 1
res += left[i:]
res += right[j:]
return res
总结
除了上述的排序算法，Python还内置了许多其他的排序方式。选择排序和冒泡排序的速度较慢，适用于小数组；插入排序和快速排序的速度较快，适用于大数组；归并排序速度中等，也适用于大数组。在实际应用中，需要根据具体的场景选择合适的排序算法，以达到最优化的效果。