排序算法是计算机科学中的一个重要主题，它通过对一组元素进行排列，使其按照特定的顺序展示。Python作为一种功能强大且易于理解的编程语言，提供了多种排序算法的实现。本文将介绍Python中常用的十大排序算法，并且提供每个算法的代码示例。
一、冒泡排序
冒泡排序是一种简单的排序算法，它通过重复地交换相邻元素直到排序完成。该算法的时间复杂度为O(n^2)。
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]
return arr
冒泡排序通过比较相邻的元素并交换它们的位置，将最大的元素逐渐“冒泡”到最后。这个过程像是气泡在水中逐渐上浮，因此得名冒泡排序。
二、选择排序
选择排序是一种简单直观的排序算法，它将待排序的序列分为已排序和未排序两部分，每次从未排序部分选择最小的元素放到已排序部分的末尾。该算法的时间复杂度也为O(n^2)。
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]
return arr
选择排序每次从未排序的部分中选择最小的元素，然后将其与未排序部分的第一个元素交换位置。这样不断地选择最小的元素，直到整个序列有序。
三、插入排序
插入排序是一种简单、稳定且高效的排序算法，它将序列分为已排序和未排序两部分，每次从未排序部分选择一个元素插入已排序部分的合适位置。该算法的时间复杂度为O(n^2)。
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
插入排序类似于玩扑克牌时的整理牌堆操作，每次从未排序的部分选择一张牌插入已排序部分的合适位置。这个过程反复进行，直到整个序列有序。
四、希尔排序
希尔排序是一种基于插入排序的高效排序算法，它通过比较相隔一定步长的元素并交换它们的位置，逐渐缩小步长直到整个序列有序。该算法的时间复杂度为O(nlogn)。
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
return arr
希尔排序是插入排序的改进版，通过设置不同的步长来分组进行插入排序，逐渐减小步长直到为1。这样可以在保持插入排序简单性的同时，提高排序的效率。
五、归并排序
归并排序是一种高效稳定的排序算法，它采用分而治之的思想，将待排序序列分为若干子序列，分别进行排序后再合并。该算法的时间复杂度为O(nlogn)。
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):
result = []
i = 0
j = 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.extend(left[i:])
result.extend(right[j:])
return result
归并排序将待排序序列分为若干子序列，递归地对子序列进行排序，然后再将排好序的子序列进行合并。这个过程类似于两个有序序列的合并操作。
六、快速排序
快速排序是一种高效的排序算法，它采用分而治之的思想和基准元素的策略，将待排序序列分为两个子序列，然后递归地对子序列进行排序。该算法的时间复杂度为O(nlogn)。
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
less = [x for x in arr[1:] if x <= pivot]
greater = [x for x in arr[1:] if x > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
快速排序通过选择一个基准元素，将待排序序列分成两部分，使得左边的元素都小于基准元素，右边的元素都大于基准元素。然后递归地对两个子序列进行排序，最终将它们合并为有序的序列。
七、堆排序
堆排序是一种高效的排序算法，它利用堆这种数据结构进行排序。堆是一种完全二叉树，具有最大堆和最小堆两种形式。该算法的时间复杂度为O(nlogn)。
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[l] > arr[largest]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
for i in range(n//2, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
return arr
堆排序利用最大堆或最小堆的性质进行排序，在构建堆和调整堆的过程中完成排序操作。它通过不断地将最大(最小)元素与堆顶交换，并调整堆使其满足堆的性质。
八、计数排序
计数排序是一种基于计数的排序算法，它通过统计待排序序列中每个元素出现的次数，然后根据统计结果对元素进行排序。该算法的时间复杂度为O(n+k)，其中k是序列中元素的取值范围。
def counting_sort(arr):
n = len(arr)
max_val = max(arr)
count = [0] * (max_val+1)
for i in range(n):
count[arr[i]] += 1
index = 0
for i in range(max_val+1):
for _ in range(count[i]):
arr[index] = i
index += 1
return arr
计数排序通过统计每个元素的出现次数，然后根据统计结果构建有序序列。它适用于元素范围较小且重复值较多的情况。
九、桶排序
桶排序是一种基于映射的排序算法，它将待排序序列分组为若干个桶，并在每个桶内进行排序，然后按照桶的顺序依次输出。该算法的时间复杂度为O(n+k)，其中k是桶的个数。
def bucket_sort(arr):
min_val = min(arr)
max_val = max(arr)
bucket_size = (max_val - min_val) / len(arr)
buckets = [[] for _ in range(len(arr))]
for i in range(len(arr)):
index = int((arr[i] - min_val) / bucket_size)
buckets[index].append(arr[i])
for i in range(len(arr)):
buckets[i] = sorted(buckets[i])
result = []
for bucket in buckets:
result.extend(bucket)
return result
桶排序将待排序序列分为一定数量的桶，每个桶内进行排序，然后按照桶的顺序依次输出所有元素。它适用于元素分布均匀的情况。
十、基数排序
基数排序是一种基于数字位数的排序算法，它通过将待排序序列按照每个数字的位数进行排序，最终得到一个有序序列。该算法的时间复杂度为O(kn)，其中k是数字的位数。
def radix_sort(arr):
max_val = max(arr)
exp = 1
while max_val // exp > 0:
counting_sort_by_digit(arr, exp)
exp *= 10
return arr
def counting_sort_by_digit(arr, exp):
count = [0] * 10
n = len(arr)
result = [0] * n
for i in range(n):
index = arr[i] // exp
count[index % 10] += 1
for i in range(1, 10):
count[i] += count[i - 1]
i = n - 1
while i >= 0:
index = arr[i] // exp
result[count[index % 10] - 1] = arr[i]
count[index % 10] -= 1
i -= 1
for i in range(n):
arr[i] = result[i]
基数排序按照数字的位数进行排序，先按照个位数排序，再按照十位数排序，依次进行直到最高位数。每一轮排序都利用计数排序的思想对数字进行排序。