数据结构七种排序算法
以下是七种常见的排序算法及其基本原理:
冒泡排序(Bubble Sort):
- 基本原理:比较相邻的两个元素,如果顺序错误则交换位置,每次循环将最大的元素移动到末尾。
- 代码示例:
def bubble_sort(arr): n = len(arr) for i in range(n-1): for j in range(n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr
选择排序(Selection Sort):
- 基本原理:每次从未排序的部分选择最小的元素,放到已排序部分的末尾。
- 代码示例:
def selection_sort(arr): n = len(arr) for i in range(n-1): 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
插入排序(Insertion Sort):
- 基本原理:将未排序的元素逐个插入到已排序部分的正确位置。
- 代码示例:
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
希尔排序(Shell Sort):
- 基本原理:将待排序的元素按照一定的间隔分组,对每组使用插入排序,逐渐缩小间隔直至为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 return arr
归并排序(Merge Sort):
- 基本原理:将待排序的序列递归地分成两半,对每半进行排序,然后将两个有序的半合并成一个有序序列。
- 代码示例: ```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 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
快速排序(Quick Sort):
- 基本原理:选择一个基准元素,将小于基准的元素放在左边,大于基准的元素放在右边,然后递归地对左右两部分进行快速排序。
- 代码示例:
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)
堆排序(Heap Sort):
- 基本原理:将待排序的序列构建成一个大顶堆,然后依次取出堆顶元素并调整堆,直到堆为空。
- 代码示例: ```python 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
def heapify(arr, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest) ```