十大排序算法汇总

好的，下面为你整理一篇面试全覆盖、极其深入的十大排序算法总结博客，涵盖算法原理、复杂度、稳定性、应用场景、工程实践、C++与Python实现（含详细注释），并对比分析各种排序的优缺点与适用情境。内容力求结构清晰、讲解透彻，适合面试复习与深入学习。

十大排序算法全解析（面试高频+工程实用）

一、排序算法总览

稳定性：相等元素排序后相对顺序是否保持不变。
空间复杂度：是否原地排序，是否需要辅助数组。
适用场景：数据规模、分布、是否有负数、是否链表等。

二、三种元素交换方法（C++/Python）

1. 临时变量法（推荐，安全）

void swap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

2. 加减法（需防溢出，i!=j）

void swap(int &a, int &b) {
    if (&a == &b) return;
    a = a + b;
    b = a - b;
    a = a - b;
}

3. 异或法（仅限整数，i!=j）

void swap(int &a, int &b) {
    if (&a == &b) return;
    a ^= b;
    b ^= a;
    a ^= b;
}

三、十大排序算法详解

1. 冒泡排序（Bubble Sort）

原理

• 每轮将最大（或最小）元素“冒泡”到末尾。
• 优化：若一轮无交换，提前结束。

复杂度

• 时间：O(n²)，最好O(n)（已排序）
• 空间：O(1)
• 稳定性：稳定

C++实现

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 1; j < n - i; ++j) {
            if (arr[j-1] > arr[j]) {
                swap(arr[j-1], arr[j]);
                swapped = true;
            }
        }
        if (!swapped) break; // 已有序，提前结束
    }
}

Python实现

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        swapped = False
        for j in range(1, n-i):
            if arr[j-1] > arr[j]:
                arr[j-1], arr[j] = arr[j], arr[j-1]
                swapped = True
        if not swapped:
            break

应用场景

• 小规模、基本有序数组
• 代码简单，教学常用

2. 选择排序（Selection Sort）

原理

• 每轮选择最小（或最大）元素放到前面。

复杂度

• 时间：O(n²)
• 空间：O(1)
• 稳定性：不稳定（跨越交换）

C++实现

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n-1; ++i) {
        int minIdx = i;
        for (int j = i+1; j < n; ++j)
            if (arr[j] < arr[minIdx]) minIdx = j;
        if (minIdx != i) swap(arr[i], arr[minIdx]);
    }
}

Python实现

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
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]

应用场景

• 小规模、交换次数少
• 不要求稳定性

3. 插入排序（Insertion Sort）

原理

• 每次将一个元素插入到已排序部分的合适位置。

复杂度

• 时间：O(n²)，最好O(n)
• 空间：O(1)
• 稳定性：稳定

C++实现

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int key = arr[i], j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            --j;
        }
        arr[j+1] = key;
    }
}

Python实现

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

应用场景

• 小规模、基本有序
• 链表排序

4. 希尔排序（Shell Sort）

原理

• 分组插入排序，逐步缩小gap，最终gap=1变插入排序。
• 增量序列影响复杂度（Shell/Hibbard/Knuth/Sedgewick等）。

复杂度

• 时间：O(n^1.3~2)，依赖gap序列
• 空间：O(1)
• 稳定性：不稳定

C++实现（Shell增量）

void shellSort(vector<int>& arr) {
    int n = arr.size();
    for (int gap = n/2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; ++i) {
            int temp = arr[i], j = i;
            while (j >= gap && arr[j-gap] > temp) {
                arr[j] = arr[j-gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

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

应用场景

• 中等规模
• 插入排序的优化

5. 归并排序（Merge Sort）

原理

• 分治法，递归分成两半，合并时排序。

复杂度

• 时间：O(nlogn)
• 空间：O(n)（非原地）
• 稳定性：稳定

C++实现

void merge(vector<int>& arr, int l, int m, int r) {
    vector<int> left(arr.begin()+l, arr.begin()+m+1);
    vector<int> right(arr.begin()+m+1, arr.begin()+r+1);
    int i = 0, j = 0, k = l;
    while (i < left.size() && j < right.size())
        arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
    while (i < left.size()) arr[k++] = left[i++];
    while (j < right.size()) arr[k++] = right[j++];
}
void mergeSort(vector<int>& arr, int l, int r) {
    if (l >= r) return;
    int m = l + (r-l)/2;
    mergeSort(arr, l, m);
    mergeSort(arr, m+1, r);
    merge(arr, l, m, r);
}

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:])
    res = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    res.extend(left[i:])
    res.extend(right[j:])
    return res

应用场景

• 大规模、链表排序
• 外部排序（磁盘/大数据）

6. 快速排序（Quick Sort）

原理

• 分治法，选主元分区，递归排序两侧。
• 主元选取方式影响性能（首位/随机/三数取中）。

复杂度

• 时间：O(nlogn)，最坏O(n²)
• 空间：O(logn)（递归栈）
• 稳定性：不稳定

C++实现（随机主元）

int partition(vector<int>& arr, int l, int r) {
    int pivot = arr[l];
    int i = l+1, j = r;
    while (true) {
        while (i <= j && arr[i] < pivot) ++i;
        while (i <= j && arr[j] > pivot) --j;
        if (i >= j) break;
        swap(arr[i++], arr[j--]);
    }
    swap(arr[l], arr[j]);
    return j;
}
void quickSort(vector<int>& arr, int l, int r) {
    if (l >= r) return;
    int mid = l + rand() % (r-l+1);
    swap(arr[l], arr[mid]);
    int p = partition(arr, l, r);
    quickSort(arr, l, p-1);
    quickSort(arr, p+1, r);
}

Python实现

import random
def quick_sort(arr, l, r):
    if l >= r:
        return
    pivot_idx = random.randint(l, r)
    arr[l], arr[pivot_idx] = arr[pivot_idx], arr[l]
    pivot = arr[l]
    i, j = l+1, r
    while True:
        while i <= j and arr[i] < pivot:
            i += 1
        while i <= j and arr[j] > pivot:
            j -= 1
        if i >= j:
            break
        arr[i], arr[j] = arr[j], arr[i]
        i += 1
        j -= 1
    arr[l], arr[j] = arr[j], arr[l]
    quick_sort(arr, l, j-1)
    quick_sort(arr, j+1, r)

应用场景

• 工程常用，STL/Java/Python底层排序
• 大规模、内存排序

7. 堆排序（Heap Sort）

原理

• 构建大顶堆，每次取堆顶与末尾交换，重建堆。

复杂度

• 时间：O(nlogn)
• 空间：O(1)
• 稳定性：不稳定

C++实现

void heapify(vector<int>& arr, int n, int i) {
    int largest = i, l = 2*i+1, r = 2*i+2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}
void heapSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = n/2-1; i >= 0; --i)
        heapify(arr, n, i);
    for (int i = n-1; i > 0; --i) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

Python实现

def heapify(arr, n, i):
    largest = i
    l, r = 2*i+1, 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(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[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

应用场景

• 原地排序，内存受限
• TopK问题（优先队列）

8. 计数排序（Counting Sort）

原理

• 统计每个数出现次数，累加输出。
• 适合整数、范围小。

复杂度

• 时间：O(n+k)
• 空间：O(n+k)
• 稳定性：稳定（优化后）

C++实现

vector<int> countingSort(const vector<int>& arr) {
    if (arr.empty()) return {};
    int minVal = *min_element(arr.begin(), arr.end());
    int maxVal = *max_element(arr.begin(), arr.end());
    vector<int> count(maxVal-minVal+1, 0);
    for (int num : arr) count[num-minVal]++;
    vector<int> res;
    for (int i = 0; i < count.size(); ++i)
        for (int j = 0; j < count[i]; ++j)
            res.push_back(i+minVal);
    return res;
}

Python实现

def counting_sort(arr):
    if not arr:
        return []
    min_val, max_val = min(arr), max(arr)
    count = [0] * (max_val - min_val + 1)
    for num in arr:
        count[num - min_val] += 1
    res = []
    for i, c in enumerate(count):
        res.extend([i + min_val] * c)
    return res

应用场景

• 整数、范围小
• 计分、桶分布

9. 基数排序（Radix Sort）

原理

• 按位（低到高/高到低）多轮计数排序。
• 适合整数、字符串。

复杂度

• 时间：O(d(n+k))，d为位数
• 空间：O(n+k)
• 稳定性：稳定

C++实现

void radixSort(vector<int>& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());
    for (int exp = 1; maxVal/exp > 0; exp *= 10) {
        vector<int> output(arr.size()), count(10, 0);
        for (int num : arr) count[(num/exp)%10]++;
        for (int i = 1; i < 10; ++i) count[i] += count[i-1];
        for (int i = arr.size()-1; i >= 0; --i) {
            int idx = (arr[i]/exp)%10;
            output[--count[idx]] = arr[i];
        }
        arr = output;
    }
}

Python实现

def radix_sort(arr):
    if not arr:
        return []
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        count = [0] * 10
        output = [0] * len(arr)
        for num in arr:
            count[(num // exp) % 10] += 1
        for i in range(1, 10):
            count[i] += count[i-1]
        for i in range(len(arr)-1, -1, -1):
            idx = (arr[i] // exp) % 10
            output[count[idx]-1] = arr[i]
            count[idx] -= 1
        arr = output[:]
        exp *= 10
    return arr

应用场景

• 大量整数、字符串排序
• 电话号码、身份证号等

10. 桶排序（Bucket Sort）

原理

• 划分区间到多个桶，桶内排序，合并输出。
• 适合均匀分布、浮点数。

复杂度

• 时间：O(n)~O(n²)
• 空间：O(n+k)
• 稳定性：取决于桶内排序

C++实现

void bucketSort(vector<float>& arr) {
    int n = arr.size();
    vector<vector<float>> buckets(n);
    for (float num : arr) {
        int idx = n * num; // 假设[0,1)
        buckets[idx].push_back(num);
    }
    for (auto& bucket : buckets)
        sort(bucket.begin(), bucket.end());
    int idx = 0;
    for (auto& bucket : buckets)
        for (float num : bucket)
            arr[idx++] = num;
}

Python实现

def bucket_sort(arr):
    n = len(arr)
    buckets = [[] for _ in range(n)]
    for num in arr:
        idx = int(n * num)  # 假设[0,1)
        buckets[idx].append(num)
    for bucket in buckets:
        bucket.sort()
    res = []
    for