排序算法 (Sorting Algorithms)

sortingalgorithmsLeetCodeinterviewdata structures

排序算法 (Sorting Algorithms)

排序算法是计算机科学中最基础也是最重要的算法之一。不同的排序算法有不同的时间复杂度和空间复杂度。

基础排序算法

1. 冒泡排序 (Bubble Sort)

过程演示: [5,3,8,4,2]
步骤1: [3,5,8,4,2]  比较5,3
步骤2: [3,5,8,4,2]  比较5,8
步骤3: [3,5,4,8,2]  比较8,4
步骤4: [3,5,4,2,8]  比较8,2
...直到没有交换发生
def bubbleSort(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]

2. 选择排序 (Selection Sort)

过程演示: [5,3,8,4,2]
步骤1: [2,3,8,4,5]  找最小值2
步骤2: [2,3,8,4,5]  找剩余最小值3
步骤3: [2,3,4,8,5]  找剩余最小值4
步骤4: [2,3,4,5,8]  找剩余最小值5
def selectionSort(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]

3. 插入排序 (Insertion Sort)

过程演示: [5,3,8,4,2]
步骤1: [3,5,8,4,2]  插入3
步骤2: [3,5,8,4,2]  插入8
步骤3: [3,4,5,8,2]  插入4
步骤4: [2,3,4,5,8]  插入2
def insertionSort(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

高级排序算法

1. 快速排序 (Quick Sort)

过程演示: [5,3,8,4,2], 选择5为pivot
步骤1: [3,4,2] 5 [8]    分区
步骤2: [2] 3 [4] 5 [8]  递归排序
结果:  [2,3,4,5,8]
def quickSort(arr, low, high):
    def partition(low, high):
        pivot = arr[high]
        i = low - 1
        for j in range(low, high):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        arr[i+1], arr[high] = arr[high], arr[i+1]
        return i + 1
    
    if low < high:
        pi = partition(low, high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)

2. 归并排序 (Merge Sort)

过程演示: [5,3,8,4]
分解:  [5,3] [8,4]
      [5] [3] [8] [4]
合并:  [3,5] [4,8]
      [3,4,5,8]
def mergeSort(arr):
    if len(arr) > 1:
        mid = len(arr)//2
        L = arr[:mid]
        R = arr[mid:]
        
        mergeSort(L)
        mergeSort(R)
        
        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] <= R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
            
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
            
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

3. 堆排序 (Heap Sort)

过程演示: [5,3,8,4,2]
构建最大堆:
       8
      / \
     4   5
    / \
   2   3

提取最大值:
8 [4,3,5,2]
5 [4,3,2]
4 [3,2]
3 [2]
2 []
def heapSort(arr):
    def heapify(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(n, largest)
    
    n = len(arr)
    # 构建最大堆
    for i in range(n//2-1, -1, -1):
        heapify(n, i)
    
    # 一个个提取元素
    for i in range(n-1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(i, 0)

经典问题

1. 数组中的第K个最大元素

LeetCode 215 - Kth Largest Element in an Array

使用快速选择算法:

输入: [3,2,1,5,6,4], k=2

快速选择过程:
1. 选择4为pivot: [3,2,1,4,6,5]
2. 4的位置是第3大，需要在右半部分继续查找
3. 选择5为pivot: [5,6]
4. 5是第2大的元素，返回5
def findKthLargest(nums, k):
    def quickSelect(left, right, k):
        pivot = nums[right]
        p = left
        
        for i in range(left, right):
            if nums[i] <= pivot:
                nums[p], nums[i] = nums[i], nums[p]
                p += 1
        
        nums[p], nums[right] = nums[right], nums[p]
        
        count = right - p + 1
        if count == k:
            return nums[p]
        elif count > k:
            return quickSelect(p+1, right, k)
        else:
            return quickSelect(left, p-1, k-count)
    
    return quickSelect(0, len(nums)-1, k)

2. 合并区间

LeetCode 56 - Merge Intervals

先排序后合并:

输入: [[1,3],[2,6],[8,10],[15,18]]

排序后:
[1,3],[2,6],[8,10],[15,18]
  ↓
合并[1,3]和[2,6]:
[1,6],[8,10],[15,18]

输出: [[1,6],[8,10],[15,18]]
def merge(intervals):
    if not intervals:
        return []
    
    # 按开始时间排序
    intervals.sort(key=lambda x: x[0])
    
    merged = [intervals[0]]
    for interval in intervals[1:]:
        if interval[0] <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], interval[1])
        else:
            merged.append(interval)
    
    return merged

3. 排序链表

LeetCode 148 - Sort List

使用归并排序:

输入: 4->2->1->3

分解:
4->2->1->3
4->2 1->3
4 2 1 3

合并:
2->4 1->3
1->2->3->4
def sortList(head):
    if not head or not head.next:
        return head
    
    # 找到中点
    slow = fast = head
    prev = None
    while fast and fast.next:
        fast = fast.next.next
        prev = slow
        slow = slow.next
    prev.next = None
    
    # 递归排序
    l1 = sortList(head)
    l2 = sortList(slow)
    
    # 合并
    dummy = ListNode(0)
    curr = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    
    curr.next = l1 or l2
    return dummy.next

4. 颜色分类

LeetCode 75 - Sort Colors

使用三指针（荷兰国旗问题）:

输入: [2,0,2,1,1,0]

过程:
[2,0,2,1,1,0] p0=0, p2=5
[0,0,2,1,1,2] p0=2, p2=4
[0,0,1,1,2,2] p0=2, p2=3

输出: [0,0,1,1,2,2]
def sortColors(nums):
    p0 = curr = 0
    p2 = len(nums) - 1
    
    while curr <= p2:
        if nums[curr] == 0:
            nums[p0], nums[curr] = nums[curr], nums[p0]
            p0 += 1
            curr += 1
        elif nums[curr] == 2:
            nums[curr], nums[p2] = nums[p2], nums[curr]
            p2 -= 1
        else:
            curr += 1

高级应用

1. 外部排序

大文件排序:
1. 分块读入内存
2. 对每块排序
3. 归并所有块

2. 多路归并

K个有序数组:
[1,4,7]
[2,5,8] → 归并 → [1,2,3,4,5,6,7,8,9]
[3,6,9]

3. 计数排序

输入: [4,2,2,8,3,3,1]

计数数组:
索引: 0 1 2 3 4 5 6 7 8
计数: 0 1 2 2 1 0 0 0 1

输出: [1,2,2,3,3,4,8]

常见技巧

  1. 选择合适的排序算法
  2. 自定义比较函数
  3. 处理特殊情况
  4. 稳定性考虑
  5. 空间复杂度优化

相关题目