常见排序算法python实现

在编程领域，排序算法是数据处理的核心部分，它用于对一系列元素进行有序排列。Python作为一门强大且广泛应用的编程语言，提供了多种实现排序算法的方法。本文将深入探讨七种常见的排序算法及其Python实现：选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序，以及对应的测试用例。 1. **选择排序（Selection Sort）**： 选择排序的基本思想是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。Python实现如下： ```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] ``` 2. **插入排序（Insertion Sort）**： 插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。Python实现如下： ```python def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i-1 while j >=0 and key < arr[j] : arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key ``` 3. **希尔排序（Shell Sort）**： 希尔排序是插入排序的优化版本，通过设置间隔序列，使得大元素有机会快速下沉。Python实现如下： ```python def shell_sort(arr): gap = len(arr) // 2 while gap > 0: for i in range(gap, len(arr)): 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 ``` 4. **归并排序（Merge Sort）**： 归并排序采用分治策略，将大问题分解为小问题来解决，再将小问题的结果合并。Python实现如下： ```python 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.extend(left[i:]) result.extend(right[j:]) return result ``` 5. **快速排序（Quick Sort）**： 快速排序也是基于分治法，通过选取一个基准值，将数组分为两部分，一部分所有元素小于基准，另一部分所有元素大于基准，然后递归地对这两部分进行排序。Python实现如下： ```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) ``` 6. **堆排序（Heap Sort）**： 堆排序利用了完全二叉树的特性，通过建立堆结构，将最大（或最小）元素放到末尾，然后重新调整堆。Python实现如下： ```python def heapify(arr, n, i): largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr[i] < arr[l]: largest = l if r < n and arr[largest] < arr[r]: 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, -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) ``` 每个排序算法都有其特定的适用场景和性能特点，如选择排序和插入排序简单直观但效率较低，适合小规模数据；希尔排序、归并排序和快速排序在中大规模数据上表现优秀；堆排序则在处理动态数据流时具有优势。实际应用中，应根据数据特性和需求选择合适的排序算法。为了验证这些排序算法的正确性，可以编写测试用例，如生成随机数组，比较排序前后是否符合预期。 以上就是七种常见排序算法的Python实现，通过理解它们的原理和代码，我们可以更好地掌握排序算法，并在实际编程中灵活运用。