排序算法是计算机程序设计中的经典问题，通过对一组元素进行排序，可以更方便地进行查找、统计和分析等操作。Python作为一门高级编程语言，具有简洁的语法和丰富的库函数，非常适合实现各种排序算法。本文将从多个方面对Python实现经典的排序算法进行详细的阐述。
一、冒泡排序
冒泡排序是一种简单但效率较低的排序算法，在每一轮比较中，通过不断交换相邻的元素来将最大的元素逐渐移动到末尾。以下是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]
return arr
# 测试示例
arr = [64, 34, 25, 12, 22, 11, 90]
result = bubble_sort(arr)
print("排序结果：", result)
冒泡排序的时间复杂度为O(n^2)，空间复杂度为O(1)。
二、插入排序
插入排序是一种简单且稳定的排序算法，将数组分为有序和无序两部分，每次将无序部分的第一个元素插入到有序部分的适当位置。以下是Python实现插入排序的代码：
def insertion_sort(arr):
for i in range(1, len(arr)):
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
# 测试示例
arr = [64, 34, 25, 12, 22, 11, 90]
result = insertion_sort(arr)
print("排序结果：", result)
插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。
三、选择排序
选择排序是一种简单但不稳定的排序算法，每一轮选择最小（或最大）的元素放到已排序部分的末尾。以下是Python实现选择排序的代码：
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# 测试示例
arr = [64, 34, 25, 12, 22, 11, 90]
result = selection_sort(arr)
print("排序结果：", result)
选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)。
四、快速排序
快速排序是一种高效的排序算法，通过选取一个基准元素，将数组分为小于基准和大于基准两部分，然后递归地对这两部分进行排序。以下是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)
# 测试示例
arr = [64, 34, 25, 12, 22, 11, 90]
result = quick_sort(arr)
print("排序结果：", result)
快速排序的时间复杂度为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):
result = []
i = 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 += left[i:]
result += right[j:]
return result
# 测试示例
arr = [64, 34, 25, 12, 22, 11, 90]
result = merge_sort(arr)
print("排序结果：", result)
归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。
六、堆排序
堆排序是一种不稳定但高效的排序算法，通过构建最大（或最小）堆，每次从堆顶取出最大（或最小）元素，并将剩下的元素重新调整为最大（或最小）堆，依次执行直到排序完成。以下是Python实现堆排序的代码：
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[i] < arr[left]:
largest = left
if right < n and arr[largest] < arr[right]:
largest = right
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, -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
# 测试示例
arr = [64, 34, 25, 12, 22, 11, 90]
result = heap_sort(arr)
print("排序结果：", result)
堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)。
七、希尔排序
希尔排序是一种不稳定的排序算法，通过将数组分组进行插入排序，不断缩小每个组的元素数量，直到最后整个数组有序。以下是Python实现希尔排序的代码：
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
# 测试示例
arr = [64, 34, 25, 12, 22, 11, 90]
result = shell_sort(arr)
print("排序结果：", result)
希尔排序的时间复杂度取决于步长序列，平均时间复杂度为O(nlogn)，空间复杂度为O(1)。
八、计数排序
计数排序是一种稳定的线性时间复杂度排序算法，适用于元素范围较小的情况。该算法统计每个元素出现的次数，然后根据统计结果进行排序。以下是Python实现计数排序的代码：
def counting_sort(arr):
max_value = max(arr)
min_value = min(arr)
count = [0] * (max_value - min_value + 1)
for num in arr:
count[num - min_value] += 1
sorted_arr = []
for i in range(len(count)):
sorted_arr += [min_value + i] * count[i]
return sorted_arr
# 测试示例
arr = [64, 34, 25, 12, 22, 11, 90]
result = counting_sort(arr)
print("排序结果：", result)
计数排序的时间复杂度为O(n+k)，其中k为最大元素和最小元素差值的大小，空间复杂度为O(n+k)。
总结
本文详细介绍了Python实现经典的排序算法，包括冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序和计数排序。每种算法都有其特点和适用场景，在实际开发中可以根据具体需求选择合适的算法。通过了解和掌握这些经典的排序算法，可以提高编程开发工程师的算法能力，为解决实际问题提供可靠的解决方案。
原创文章，作者：QAQT，如若转载，请注明出处：https://www.beidandianzhu.com/g/6915.html
