排序算法是计算机科学中的基本算法之一，用于将一组元素按照一定顺序排列。快速排序、归并排序和堆排序是三种常见的排序算法，各有其特点和适用场景。
快速排序 (Quick Sort)
快速排序是一种经典的分而治之的排序算法。其基本思想是选择一个基准元素，将数组分成两个子数组，小于基准的放在左边，大于基准的放在右边，然后对左右子数组递归地应用同样的方法。
实现
def quick_sort(arr):if len(arr) <= 1:return arrstack = [(0, len(arr) - 1)] # 使用栈来保存待排序子数组的起始和结束索引while stack:low, high = stack.pop() # 取出栈顶的子数组范围if low < high:pivot = arr[high] # 选取最后一个元素作为基准left = low - 1 # 左指针for right in range(low, high): # 右指针if arr[right] <= pivot:left += 1arr[left], arr[right] = arr[right], arr[left]arr[left + 1], arr[high] = arr[high], arr[left + 1] # 将基准元素放到正确的位置# 将左右子数组的范围入栈stack.append((low, left))stack.append((left + 2, high))return arr复杂度与稳定性
- 时间复杂度：平均情况下为O(nlogn)，最坏情况下为O(n^2)。
- 空间复杂度：O(logn)。
- 稳定性：不稳定。
归并排序 (Merge Sort)
归并排序是另一种分而治之的排序算法，其基本思想是将数组递归地分成两个子数组，分别排序，然后将已排序的子数组合并起来。
实现
def merge_sort(arr):if len(arr) <= 1:return arrelse:mid = len(arr) // 2left_half = merge_sort(arr[:mid])right_half = merge_sort(arr[mid:])return merge(left_half, right_half)def merge(left, right):merged = []i = j = 0while i < len(left) and j < len(right):if left[i] < right[j]:merged.append(left[i])i += 1else:merged.append(right[j])j += 1merged.extend(left[i:])merged.extend(right[j:])return merged
复杂度与稳定性
- 时间复杂度：始终为O(nlogn)。
- 空间复杂度：O(n)。
- 稳定性：稳定。
堆排序 (Heap Sort)
堆排序是一种基于二叉堆的选择排序。它利用堆的性质将数组构建成一个最大堆（或最小堆），然后逐步取出堆顶元素并调整堆，直到整个数组有序。
实现
def heapify(arr, n, i):largest = ileft = 2 * i + 1right = 2 * i + 2if left < n and arr[left] > arr[largest]:largest = leftif right < n and arr[right] > arr[largest]:largest = rightif 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)
复杂度与稳定性
- 时间复杂度：始终为O(nlogn)。
- 空间复杂度：O(1)。
- 稳定性：不稳定。
结论
- 快速排序在平均情况下性能优秀，但在最坏情况下性能较差。
- 归并排序始终保持O(nlogn)的时间复杂度，适用于大规模数据的排序。
- 堆排序是一种原地排序算法，不需要额外的存储空间，但不是稳定的排序算法。
7.彩蛋
关注公众号，获取更多AI算法、工程实践相关的精彩内容~
