sort-template

给我这些排序的特点、原理、cpp可实现代码，方便我学习以及亲自手敲代码#

选择排序（多次“打擂台”）
冒泡排序
插入排序
计数排序
基数排序
快速排序
归并排序（分治）
堆排序
桶排序
希尔排序（并非常见）
锦标赛排序（并非常见）
Tim排序（并非常见）

以下是各类排序算法的特点、原理及C++实现代码，按常用程度和逻辑复杂度排序，方便学习和手敲练习：

1. 选择排序（Selection Sort）#

特点#

原理简单，不稳定排序（如[2,2,1]会交换第一个2和1，破坏稳定性）。
时间复杂度：O(n²)，空间复杂度：O(1)。
适合小规模数据，交换次数少（最多n-1次）。

原理#

每次从待排序区间选择最小（或最大）元素，放到区间起始位置，重复直到排序完成。

C++实现#

1
#include <vector>
2
using namespace std;
3

4
void selectionSort(vector<int>& arr) {
5
    int n = arr.size();
6
    for (int i = 0; i < n - 1; ++i) {
7
        int minIdx = i;  // 记录最小值索引
8
        for (int j = i + 1; j < n; ++j) {
9
            if (arr[j] < arr[minIdx]) {
10
                minIdx = j;
11
            }
12
        }
13
        swap(arr[i], arr[minIdx]);  // 交换到当前位置
14
    }
15
}

2. 冒泡排序（Bubble Sort）#

特点#

原理直观，稳定排序（相等元素不交换）。
时间复杂度：O(n²)，空间复杂度：O(1)。
适合几乎有序的数据（可优化提前终止）。

原理#

重复遍历数组，每次比较相邻元素，顺序错误则交换，直到没有元素交换（排序完成）。

C++实现#

1
#include <vector>
2
using namespace std;
3

4
void bubbleSort(vector<int>& arr) {
5
    int n = arr.size();
6
    bool swapped;  // 优化：判断是否已有序
7
    for (int i = 0; i < n - 1; ++i) {
8
        swapped = false;
9
        for (int j = 0; j < n - i - 1; ++j) {  // 尾部已排序，无需再比较
10
            if (arr[j] > arr[j + 1]) {
11
                swap(arr[j], arr[j + 1]);
12
                swapped = true;
13
            }
14
        }
15
        if (!swapped) break;  // 无交换，提前终止
16
    }
17
}

3. 插入排序（Insertion Sort）#

特点#

稳定排序，适合小规模或部分有序数据。
时间复杂度：O(n²)，空间复杂度：O(1)。
实际应用中比冒泡排序高效（移动操作比交换少）。

原理#

将数组分为「已排序」和「未排序」两部分，每次从后者取一个元素，插入前者的合适位置。

C++实现#

1
#include <vector>
2
using namespace std;
3

4
void insertionSort(vector<int>& arr) {
5
    int n = arr.size();
6
    for (int i = 1; i < n; ++i) {
7
        int key = arr[i];  // 待插入元素
8
        int j = i - 1;
9
        // 移动已排序部分中大于key的元素
10
        while (j >= 0 && arr[j] > key) {
11
            arr[j + 1] = arr[j];
12
            j--;
13
        }
14
        arr[j + 1] = key;  // 插入key
15
    }
16
}

4. 希尔排序（Shell Sort）#

特点#

插入排序的优化版，不稳定排序。
时间复杂度：O(n^1.3)（取决于步长），空间复杂度：O(1)。
通过「分组插入排序」减少数据移动距离。

原理#

按递减步长将数组分组，对每组进行插入排序，最终步长为1（退化为普通插入排序）。

C++实现（步长采用n/2递减）#

1
#include <vector>
2
using namespace std;
3

4
void shellSort(vector<int>& arr) {
5
    int n = arr.size();
6
    // 步长从n/2开始，每次减半
7
    for (int gap = n / 2; gap > 0; gap /= 2) {
8
        // 对每个分组进行插入排序
9
        for (int i = gap; i < n; ++i) {
10
            int key = arr[i];
11
            int j;
12
            for (j = i; j >= gap && arr[j - gap] > key; j -= gap) {
13
                arr[j] = arr[j - gap];
14
            }
15
            arr[j] = key;
16
        }
17
    }
18
}

5. 快速排序（Quick Sort）#

特点#

分治思想，不稳定排序，实际应用中最快的排序之一。
时间复杂度：平均O(n log n)，最坏O(n²)（可通过随机选枢轴优化），空间复杂度：O(log n)（递归栈）。

原理#

选一个「枢轴」元素，将数组分为两部分：左部≤枢轴，右部≥枢轴。
递归对左右两部分排序。

C++实现（随机枢轴优化）#

1
#include <vector>
2
#include <cstdlib>
3
#include <ctime>
4
using namespace std;
5

6
// 划分函数：返回枢轴最终位置
7
int partition(vector<int>& arr, int low, int high) {
8
    // 随机选枢轴，避免最坏情况
9
    srand(time(0));
10
    int pivotIdx = low + rand() % (high - low + 1);
11
    swap(arr[pivotIdx], arr[high]);
12
    int pivot = arr[high];
13

14
    int i = low - 1;  // 记录小于枢轴的区域边界
15
    for (int j = low; j < high; ++j) {
16
        if (arr[j] <= pivot) {
17
            i++;
18
            swap(arr[i], arr[j]);
19
        }
20
    }
21
    swap(arr[i + 1], arr[high]);  // 枢轴归位
22
    return i + 1;
23
}
24

25
void quickSort(vector<int>& arr, int low, int high) {
26
    if (low < high) {
27
        int pi = partition(arr, low, high);  // 划分
28
        quickSort(arr, low, pi - 1);         // 左半部分
29
        quickSort(arr, pi + 1, high);        // 右半部分
30
    }
31
}
32

33
// 对外接口
34
void quickSort(vector<int>& arr) {
35
    if (arr.empty()) return;
36
    quickSort(arr, 0, arr.size() - 1);
37
}

6. 归并排序（Merge Sort）#

特点#

分治思想，稳定排序，时间复杂度稳定。
时间复杂度：O(n log n)，空间复杂度：O(n)（需临时数组）。
适合大规模数据，可并行化。

原理#

将数组递归分为两半，直到子数组长度为1（天然有序）。
合并两个有序子数组为一个有序数组。

C++实现#

1
#include <vector>
2
using namespace std;
3

4
// 合并两个有序子数组[low,mid]和[mid+1,high]
5
void merge(vector<int>& arr, int low, int mid, int high) {
6
    int n1 = mid - low + 1;
7
    int n2 = high - mid;
8
    vector<int> L(n1), R(n2);  // 临时数组
9

10
    // 复制数据到临时数组
11
    for (int i = 0; i < n1; ++i) L[i] = arr[low + i];
12
    for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j];
13

14
    // 合并临时数组到原数组
15
    int i = 0, j = 0, k = low;
16
    while (i < n1 && j < n2) {
17
        if (L[i] <= R[j]) {
18
            arr[k] = L[i++];
19
        } else {
20
            arr[k] = R[j++];
21
        }
22
        k++;
23
    }
24
    // 处理剩余元素
25
    while (i < n1) arr[k++] = L[i++];
26
    while (j < n2) arr[k++] = R[j++];
27
}
28

29
void mergeSort(vector<int>& arr, int low, int high) {
30
    if (low < high) {
31
        int mid = low + (high - low) / 2;  // 避免溢出
32
        mergeSort(arr, low, mid);          // 左半部分排序
33
        mergeSort(arr, mid + 1, high);     // 右半部分排序
34
        merge(arr, low, mid, high);        // 合并
35
    }
36
}
37

38
// 对外接口
39
void mergeSort(vector<int>& arr) {
40
    if (arr.empty()) return;
41
    mergeSort(arr, 0, arr.size() - 1);
42
}

7. 堆排序（Heap Sort）#

特点#

利用堆数据结构，不稳定排序。
时间复杂度：O(n log n)，空间复杂度：O(1)（原地排序）。
适合大数据量，堆顶可快速获取极值。

原理#

将数组构建为大顶堆（父节点≥子节点）。
反复将堆顶（最大值）与末尾元素交换，缩小堆范围并重新调整堆结构。

C++实现#

1
#include <vector>
2
using namespace std;
3

4
// 调整以root为根的子树为大顶堆
5
void heapify(vector<int>& arr, int n, int root) {
6
    int largest = root;       // 初始化最大值为根
7
    int left = 2 * root + 1;  // 左子节点
8
    int right = 2 * root + 2; // 右子节点
9

10
    if (left < n && arr[left] > arr[largest]) largest = left;
11
    if (right < n && arr[right] > arr[largest]) largest = right;
12

13
    // 若最大值不是根，则交换并递归调整
14
    if (largest != root) {
15
        swap(arr[root], arr[largest]);
16
        heapify(arr, n, largest);
17
    }
18
}
19

20
void heapSort(vector<int>& arr) {
21
    int n = arr.size();
22
    // 构建大顶堆（从最后一个非叶子节点开始）
23
    for (int i = n / 2 - 1; i >= 0; --i) {
24
        heapify(arr, n, i);
25
    }
26

27
    // 逐个提取最大值
28
    for (int i = n - 1; i > 0; --i) {
29
        swap(arr[0], arr[i]);  // 堆顶（最大值）移到末尾
30
        heapify(arr, i, 0);    // 调整剩余元素为大顶堆
31
    }
32
}

8. 计数排序（Counting Sort）#

特点#

非比较排序，稳定排序，适用于整数且范围不大的场景。
时间复杂度：O(n + k)（k为数据范围），空间复杂度：O(n + k)。

原理#

统计每个元素出现的次数（计数数组）。
根据计数数组计算元素的位置，填充到结果数组。

C++实现（假设数据范围为[minVal, maxVal]）#

1
#include <vector>
2
#include <algorithm>
3
using namespace std;
4

5
void countingSort(vector<int>& arr) {
6
    if (arr.empty()) return;
7
    int minVal = *min_element(arr.begin(), arr.end());
8
    int maxVal = *max_element(arr.begin(), arr.end());
9
    int range = maxVal - minVal + 1;
10

11
    vector<int> count(range, 0);  // 计数数组
12
    vector<int> output(arr.size());  // 结果数组
13

14
    // 统计每个元素出现次数
15
    for (int num : arr) {
16
        count[num - minVal]++;
17
    }
18

19
    // 计算前缀和（确定元素位置）
20
    for (int i = 1; i < range; ++i) {
21
        count[i] += count[i - 1];
22
    }
23

24
    // 填充结果数组（从后往前保证稳定性）
25
    for (int i = arr.size() - 1; i >= 0; --i) {
26
        output[count[arr[i] - minVal] - 1] = arr[i];
27
        count[arr[i] - minVal]--;
28
    }
29

30
    // 复制回原数组
31
    arr = output;
32
}

9. 基数排序（Radix Sort）#

特点#

非比较排序，基于计数排序实现，稳定排序。
时间复杂度：O(d*(n + k))（d为位数，k为基数，通常取10），空间复杂度：O(n + k)。
适合大整数或字符串排序（按位处理）。

原理#

按低位到高位（或高位到低位）依次排序。
每一位排序使用计数排序（保证稳定性）。

C++实现（按低位排序，基数为10）#

1
#include <vector>
2
#include <algorithm>
3
using namespace std;
4

5
// 获取数字的第d位（从0开始，d=0为个位）
6
int getDigit(int num, int d) {
7
    for (int i = 0; i < d; ++i) {
8
        num /= 10;
9
    }
10
    return num % 10;
11
}
12

13
// 对第d位进行计数排序（基数为10）
14
void countSortByDigit(vector<int>& arr, int d) {
15
    int n = arr.size();
16
    vector<int> output(n);
17
    vector<int> count(10, 0);  // 0-9共10个数字
18

19
    // 统计第d位的次数
20
    for (int i = 0; i < n; ++i) {
21
        int digit = getDigit(arr[i], d);
22
        count[digit]++;
23
    }
24

25
    // 计算前缀和
26
    for (int i = 1; i < 10; ++i) {
27
        count[i] += count[i - 1];
28
    }
29

30
    // 填充结果（从后往前保证稳定性）
31
    for (int i = n - 1; i >= 0; --i) {
32
        int digit = getDigit(arr[i], d);
33
        output[count[digit] - 1] = arr[i];
34
        count[digit]--;
35
    }
36

37
    arr = output;
38
}
39

40
void radixSort(vector<int>& arr) {
41
    if (arr.empty()) return;
42
    // 找到最大数，确定最大位数
43
    int maxVal = *max_element(arr.begin(), arr.end());
44
    int maxDigits = 0;
45
    while (maxVal > 0) {
46
        maxVal /= 10;
47
        maxDigits++;
48
    }
49

50
    // 按每位排序
51
    for (int d = 0; d < maxDigits; ++d) {
52
        countSortByDigit(arr, d);
53
    }
54
}

10. 桶排序（Bucket Sort）#

特点#

非比较排序，稳定性取决于桶内排序算法。
时间复杂度：平均O(n + k)，最坏O(n²)（桶内用插入排序时），空间复杂度：O(n + k)（k为桶数）。
适合均匀分布的数据（如浮点数、范围已知的整数）。

原理#

将数据分到多个桶中（每个桶对应一个范围）。
对每个桶内数据单独排序（如插入排序）。
合并所有桶的结果。

C++实现（假设数据范围为[0,1)的浮点数）#

1
#include <vector>
2
#include <algorithm>
3
using namespace std;
4

5
void bucketSort(vector<float>& arr) {
6
    int n = arr.size();
7
    if (n == 0) return;
8

9
    // 创建n个桶
10
    vector<vector<float>> buckets(n);
11

12
    // 将元素分配到桶中
13
    for (float num : arr) {
14
        int bucketIdx = n * num;  // 映射到[0, n-1]
15
        buckets[bucketIdx].push_back(num);
16
    }
17

18
    // 对每个桶排序
19
    for (auto& bucket : buckets) {
20
        sort(bucket.begin(), bucket.end());  // 此处用库函数，也可替换为插入排序
21
    }
22

23
    // 合并桶
24
    int idx = 0;
25
    for (auto& bucket : buckets) {
26
        for (float num : bucket) {
27
            arr[idx++] = num;
28
        }
29
    }
30
}

11. 锦标赛排序（Tournament Sort）#

特点#

基于堆的排序，稳定排序，适合外部排序（数据不能全部加载到内存）。
时间复杂度：O(n log n)，空间复杂度：O(n)（需构建锦标赛树）。

原理#

构建完全二叉树（锦标赛树），叶子节点为待排序元素，非叶子节点为子节点的最小值（或最大值）。
提取根节点（最小值），标记为已提取，更新路径上的节点为剩余子节点的最小值，重复直到所有元素提取完毕。

C++实现（最小值锦标赛）#

1
#include <vector>
2
#include <climits>
3
using namespace std;
4

5
// 构建锦标赛树
6
void buildTournamentTree(const vector<int>& arr, vector<int>& tree, vector<bool>& isExtracted, int n) {
7
    int size = 1;
8
    while (size < n) size <<= 1;  // 找到大于等于n的最小2的幂
9

10
    // 初始化叶子节点
11
    for (int i = 0; i < n; ++i) {
12
        tree[size - 1 + i] = arr[i];
13
    }
14
    for (int i = n; i < size; ++i) {
15
        tree[size - 1 + i] = INT_MAX;  // 虚拟节点（无穷大）
16
    }
17

18
    // 构建非叶子节点
19
    for (int i = size - 2; i >= 0; --i) {
20
        tree[i] = min(tree[2 * i + 1], tree[2 * i + 2]);
21
    }
22
}
23

24
// 提取最小值并更新树
25
int extractMin(vector<int>& tree, vector<bool>& isExtracted, int size, int n) {
26
    int minVal = tree[0];
27
    int i = 0;
28

29
    // 找到最小值对应的叶子节点
30
    while (i < size - 1) {
31
        int left = 2 * i + 1;
32
        int right = 2 * i + 2;
33
        if (tree[left] == tree[i]) {
34
            i = left;
35
        } else {
36
            i = right;
37
        }
38
    }
39

40
    isExtracted[i - (size - 1)] = true;  // 标记为已提取
41
    tree[i] = INT_MAX;  // 置为无穷大
42

43
    // 向上更新树
44
    i = (i - 1) / 2;  // 父节点
45
    while (i >= 0) {
46
        int newVal = min(tree[2 * i + 1], tree[2 * i + 2]);
47
        if (tree[i] == newVal) break;  // 无需继续更新
48
        tree[i] = newVal;
49
        if (i == 0) break;
50
        i = (i - 1) / 2;
51
    }
52

53
    return minVal;
54
}
55

56
void tournamentSort(vector<int>& arr) {
57
    int n = arr.size();
58
    if (n <= 1) return;
59

60
    int size = 1;
61
    while (size < n) size <<= 1;  // 树的大小（2的幂）
62
    vector<int> tree(2 * size - 1);  // 锦标赛树
63
    vector<bool> isExtracted(n, false);  // 标记是否已提取
64

65
    buildTournamentTree(arr, tree, isExtracted, n);
66

67
    // 提取所有元素
68
    for (int i = 0; i < n; ++i) {
69
        arr[i] = extractMin(tree, isExtracted, size, n);
70
    }
71
}

12. Tim排序#

特点#

Python和Java的内置排序算法，结合归并排序和插入排序，稳定排序。
时间复杂度：O(n log n)，空间复杂度：O(n)。
对现实数据（常有部分有序）优化极佳。

原理#

将数组分为多个「运行段」（Run，已排序的子序列），短运行段用插入排序扩展。
按规则合并运行段（类似归并排序，控制合并顺序避免失衡）。

C++实现（简化版，实际实现复杂）#

1
#include <vector>
2
#include <algorithm>
3
using namespace std;
4

5
const int MIN_RUN = 32;  // 最小运行段长度（可调）
6

7
// 插入排序，对[left, right]区间排序
8
void insertionSort(vector<int>& arr, int left, int right) {
9
    for (int i = left + 1; i <= right; ++i) {
10
        int key = arr[i];
11
        int j = i - 1;
12
        while (j >= left && arr[j] > key) {
13
            arr[j + 1] = arr[j];
14
            j--;
15
        }
16
        arr[j + 1] = key;
17
    }
18
}
19

20
// 合并两个有序区间[left, mid]和[mid+1, right]
21
void merge(vector<int>& arr, int left, int mid, int right) {
22
    int n1 = mid - left + 1;
23
    int n2 = right - mid;
24
    vector<int> L(arr.begin() + left, arr.begin() + mid + 1);
25
    vector<int> R(arr.begin() + mid + 1, arr.begin() + right + 1);
26

27
    int i = 0, j = 0, k = left;
28
    while (i < n1 && j < n2) {
29
        if (L[i] <= R[j]) {
30
            arr[k++] = L[i++];
31
        } else {
32
            arr[k++] = R[j++];
33
        }
34
    }
35
    while (i < n1) arr[k++] = L[i++];
36
    while (j < n2) arr[k++] = R[j++];
37
}
38

39
void timSort(vector<int>& arr) {
40
    int n = arr.size();
41
    if (n <= MIN_RUN) {
42
        insertionSort(arr, 0, n - 1);
43
        return;
44
    }
45

46
    // 划分并排序运行段
47
    for (int i = 0; i < n; i += MIN_RUN) {
48
        int end = min(i + MIN_RUN - 1, n - 1);
49
        insertionSort(arr, i, end);
50
    }
51

52
    // 合并运行段，从长度MIN_RUN开始，每次翻倍
53
    for (int size = MIN_RUN; size < n; size *= 2) {
54
        for (int left = 0; left < n; left += 2 * size) {
55
            int mid = min(left + size - 1, n - 1);
56
            int right = min(left + 2 * size - 1, n - 1);
57
            if (mid < right) {  // 若有右段则合并
58
                merge(arr, left, mid, right);
59
            }
60
        }
61
    }
62
}

学习建议#

先掌握基础：选择、冒泡、插入排序是理解排序思想的基础，重点理解「比较-交换/移动」逻辑。
深入分治排序：快速排序（ pivot 选择）、归并排序（合并逻辑）是面试高频考点。
非比较排序：计数、基数、桶排序适用于特定场景，需理解其适用条件（如数据范围、分布）。
动手实践：每敲完一种排序，用测试用例（如空数组、重复元素、逆序数组）验证正确性，观察算法行为。

通过对比不同算法的时间/空间复杂度和适用场景，能更深刻理解排序的本质~

如果我想偷懒调用库函数，如何写，或者调用?#

在 C++ 中，直接调用标准库的排序函数是最便捷的方式，无需自己实现排序算法。标准库提供了 std::sort（最常用）和 std::stable_sort（稳定排序），位于 <algorithm> 头文件中，适用于大多数场景。

1. 调用 `std::sort`（快速排序的优化版本，非稳定排序）#

特点：#

平均时间复杂度 O(n log n)，效率极高。
非稳定排序（相等元素的相对顺序可能改变）。
支持任意可随机访问的容器（如 vector、array、原生数组等）。

使用方法：#

1
#include <iostream>
2
#include <vector>
3
#include <algorithm> // 包含 std::sort
4

5
int main() {
6
    // 示例1：排序 vector<int>
7
    std::vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};
8
    std::sort(arr.begin(), arr.end()); // 默认升序排序
9

10
    // 输出结果
11
    for (int num : arr) {
12
        std::cout << num << " "; // 输出：1 1 2 3 4 5 6 9
13
    }
14
    std::cout << std::endl;
15

16
    // 示例2：排序原生数组
17
    int nums[] = {5, 2, 7, 3, 1};
18
    int n = sizeof(nums) / sizeof(nums[0]);
19
    std::sort(nums, nums + n); // 原生数组用指针范围
20

21
    for (int i = 0; i < n; ++i) {
22
        std::cout << nums[i] << " "; // 输出：1 2 3 5 7
23
    }
24
    std::cout << std::endl;
25

26
    // 示例3：降序排序（自定义比较函数）
27
    std::vector<int> arr2 = {3, 1, 4, 1, 5};
28
    std::sort(arr2.begin(), arr2.end(), std::greater<int>()); // 降序
29

30
    for (int num : arr2) {
31
        std::cout << num << " "; // 输出：5 4 3 1 1
32
    }
33
    std::cout << std::endl;
34

35
    return 0;
36
}

2. 调用 `std::stable_sort`（稳定排序）#

特点：#

时间复杂度 O(n log n)，但空间复杂度略高（可能为 O(n)）。
稳定排序（相等元素的相对顺序保持不变）。
使用场景：需要保留相等元素原始顺序时（如先按成绩排序，再按姓名排序，需保留姓名的原始顺序）。

使用方法：#

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4

5
int main() {
6
    // 示例：稳定排序（保留相等元素的原始顺序）
7
    std::vector<std::pair<int, int>> arr = {{2, 1}, {1, 2}, {2, 3}, {1, 4}};
8
    // 按第一个元素排序（值相等时，保留原始顺序）
9
    std::stable_sort(arr.begin(), arr.end(),
10
        [](const auto& a, const auto& b) { return a.first < b.first; });
11

12
    for (auto& p : arr) {
13
        std::cout << "(" << p.first << "," << p.second << ") ";
14
        // 输出：(1,2) (1,4) (2,1) (2,3) （注意第二个元素的顺序与输入一致）
15
    }
16
    return 0;
17
}

3. 对自定义类型排序（需提供比较规则）#

如果排序对象是自定义结构体/类，需通过重载 < 运算符或自定义比较函数告诉 std::sort 如何排序。

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4

5
// 自定义结构体
6
struct Student {
7
    std::string name;
8
    int score;
9
};
10

11
int main() {
12
    std::vector<Student> students = {
13
        {"Alice", 85},
14
        {"Bob", 75},
15
        {"Charlie", 90}
16
    };
17

18
    // 方法1：使用 lambda 表达式定义比较规则（按分数升序）
19
    std::sort(students.begin(), students.end(),
20
        [](const Student& a, const Student& b) {
21
            return a.score < b.score; // 分数小的在前
22
        });
23

24
    // 输出排序结果
25
    for (auto& s : students) {
26
        std::cout << s.name << " (" << s.score << "), ";
27
        // 输出：Bob (75), Alice (85), Charlie (90),
28
    }
29

30
    return 0;
31
}

总结：#

大多数情况直接用 std::sort 即可，效率高且用法简单。
需要稳定排序时用 std::stable_sort。
支持升序、降序或自定义排序规则（通过比较函数或 lambda）。
适用容器：vector、array、deque 等可随机访问的容器，以及原生数组。

调用标准库函数是工程中最推荐的做法，因为其经过严格优化，且避免了手写排序的潜在 bug。

sort和qsort区别在哪里？#

sort（C++标准库函数）和qsort（C标准库函数）都是用于排序的库函数，但它们来自不同的语言标准，在使用方式、功能和性能上有显著区别。以下是详细对比：

1. 所属标准与头文件#

qsort：
来自 C标准库（C89及以后），定义在 <stdlib.h> 头文件中。
C++中也可使用（需包含 <cstdlib>），但本质是C的遗留函数。
sort：
来自 C++标准库（C++98及以后），定义在 <algorithm> 头文件中，是C++ STL的一部分。

2. 函数原型与参数#

`qsort` 原型：#

1
void qsort(
2
    void* base,        // 待排序数组的起始地址（void* 泛型指针）
3
    size_t nmemb,      // 数组元素个数
4
    size_t size,       // 每个元素的字节大小
5
    int (*compar)(const void*, const void*)  // 比较函数指针
6
);

必须显式指定数组地址、元素个数、每个元素的大小。
比较函数需手动处理指针类型转换（因为参数是 void*）。

`sort` 原型（简化版）：#

1
template <class RandomIt>
2
void sort(
3
    RandomIt first,    // 排序范围的起始迭代器
4
    RandomIt last      // 排序范围的结束迭代器（前闭后开）
5
);
6

7
// 带自定义比较器的版本
8
template <class RandomIt, class Compare>
9
void sort(
10
    RandomIt first,
11
    RandomIt last,
12
    Compare comp       // 比较函数/函数对象/lambda
13
);

通过迭代器指定排序范围（如 vector.begin() 到 vector.end()），无需手动计算元素个数和大小。
模板自动推导元素类型，无需手动类型转换。

3. 支持的数据类型#

qsort：
只能排序 原生数组（如 int arr[10]），且需手动处理类型转换。
对自定义类型（如C++的结构体/类）排序时，需在比较函数中显式转换 void* 为对应类型指针，容易出错。
sort：
支持 所有可随机访问的容器（如 vector、array、deque）和原生数组，通过迭代器统一接口。
对自定义类型（如 struct、class）排序时，可通过重载 < 运算符或自定义比较器（lambda、函数对象）实现，类型安全且方便。

4. 比较函数的差异#

`qsort` 的比较函数：#

必须返回 int 类型：
- 若 a < b，返回负数；
- 若 a == b，返回 0；
- 若 a > b，返回正数。

参数为 const void*，需手动转换为具体类型指针，例如排序 int 数组：

1
int compareInt(const void* a, const void* b) {
2
    // 必须先转换为 int*，再解引用
3
    int val1 = *(const int*)a;
4
    int val2 = *(const int*)b;
5
    return val1 - val2; // 升序
6
}

`sort` 的比较器：#

可以是函数、函数对象或lambda表达式，返回 bool 类型：
若希望 a 排在 b 前面，返回 true，否则返回 false。

无需类型转换，模板自动推导，例如排序 int 数组：

1
// 升序（默认，可省略）
2
sort(arr.begin(), arr.end(), [](int a, int b) { return a < b; });
3
// 降序
4
sort(arr.begin(), arr.end(), [](int a, int b) { return a > b; });

5. 排序算法与性能#

qsort：
通常实现为 快速排序（某些库可能用混合算法），但由于C语言的限制（无模板、需类型转换），性能略低，尤其是对小数据或简单类型（如 int）。
时间复杂度：平均 O(n log n)，最坏 O(n²)（取决于实现）。
sort：
C++标准未规定具体算法，但主流实现（如GCC的 libstdc++）采用 ** introsort（内省排序）**，结合快速排序、堆排序和插入排序，在不同场景下自动切换，性能更优。
时间复杂度：稳定在 O(n log n)（最坏情况也会保证）。
此外，sort 利用模板 inline 优化，避免了 qsort 中函数指针的调用开销，对简单类型排序速度通常比 qsort 快2-3倍。

6. 稳定性#

qsort：不稳定排序（相等元素的相对顺序可能改变）。
sort：不稳定排序（同 qsort），但C++提供 stable_sort 实现稳定排序，而C标准库没有对应的稳定排序函数。

7. 使用示例对比#

排序 `int` 数组：#

1
// qsort 示例（C风格）
2
#include <cstdlib>
3
#include <iostream>
4
using namespace std;
5

6
int compareInt(const void* a, const void* b) {
7
    return *(int*)a - *(int*)b; // 手动转换
8
}
9

10
int main() {
11
    int arr[] = {3, 1, 4, 1, 5};
12
    int n = sizeof(arr) / sizeof(arr[0]);
13
    qsort(arr, n, sizeof(int), compareInt); // 需指定大小和比较函数
14
    for (int num : arr) cout << num << " "; // 1 1 3 4 5
15
    return 0;
16
}

1
// sort 示例（C++风格）
2
#include <algorithm>
3
#include <iostream>
4
#include <vector>
5
using namespace std;
6

7
int main() {
8
    vector<int> arr = {3, 1, 4, 1, 5};
9
    sort(arr.begin(), arr.end()); // 无需手动指定大小和类型
10
    for (int num : arr) cout << num << " "; // 1 1 3 4 5
11
    return 0;
12
}

排序自定义类型：#

1
// qsort 排序结构体（需手动转换）
2
#include <cstdlib>
3
#include <string>
4
using namespace std;
5

6
struct Student { string name; int score; };
7

8
int compareStudent(const void* a, const void* b) {
9
    // 手动转换为 Student*
10
    Student* s1 = (Student*)a;
11
    Student* s2 = (Student*)b;
12
    return s1->score - s2->score;
13
}
14

15
int main() {
16
    Student arr[] = {{"Bob", 75}, {"Alice", 85}};
17
    qsort(arr, 2, sizeof(Student), compareStudent);
18
    return 0;
19
}

1
// sort 排序结构体（类型安全）
2
#include <algorithm>
3
#include <vector>
4
using namespace std;
5

6
struct Student { string name; int score; };
7

8
int main() {
9
    vector<Student> arr = {{"Bob", 75}, {"Alice", 85}};
10
    // 用lambda指定排序规则（按分数升序）
11
    sort(arr.begin(), arr.end(), [](const Student& a, const Student& b) {
12
        return a.score < b.score;
13
    });
14
    return 0;
15
}

总结：如何选择？#

在C++中：优先使用 std::sort，原因是：
类型安全、接口简洁（迭代器）、性能更优、支持自定义类型和lambda，且有 stable_sort 可选。
在纯C中：只能使用 qsort，但需注意类型转换和函数指针的使用。

简单来说，sort 是C++中更现代、高效、安全的排序方案，而 qsort 是C语言的遗留产物，仅在兼容C时使用。

介绍一下std::sort函数的时间复杂度#

std::sort 是 C++ 标准库中最常用的排序函数，其时间复杂度设计为 平均和最坏情况下均为 O(n log n)，这是通过灵活的算法选择实现的。具体细节如下：

1. 底层算法：内省排序（Introsort）#

C++ 标准并未强制规定 std::sort 的具体实现，但主流编译器（如 GCC 的 libstdc++、Clang 的 libc++）均采用 内省排序（Introsort） 作为核心算法，其逻辑如下：

初始阶段：使用快速排序（Quicksort），利用其平均 O(n log n) 的高效性。
深度控制：跟踪递归深度，当深度超过阈值（通常为 2 * log2(n)）时，切换为堆排序（Heapsort），避免快速排序在最坏情况下（如已排序数组）退化为 O(n²)。
小规模优化：当子数组长度小于阈值（通常为 16）时，切换为插入排序（Insertionsort），利用其对小规模数据的高效性（减少递归开销）。

这种混合策略确保了 std::sort 在各种场景下的稳定性和高效性。

2. 时间复杂度的保证#

平均情况：O(n log n)（来自快速排序的特性）。
最坏情况：O(n log n)（通过堆排序兜底，避免快速排序的最坏情况）。
空间复杂度：O(log n)（主要来自快速排序的递归栈，堆排序阶段为 O(1) 原地排序）。

3. 与其他排序函数的对比#

相比 C 语言的 qsort（通常为纯快速排序，最坏 O(n²)），std::sort 最坏情况下更稳定。
相比 std::stable_sort（稳定排序，最坏 O(n log n)，但空间复杂度可能为 O(n)），std::sort 空间效率更高，但不稳定。

总结#

std::sort 通过内省排序（快速排序 + 堆排序 + 插入排序的混合策略），在理论和实践中均保证了 O(n log n) 的时间复杂度，兼顾了平均效率和最坏情况性能，是 C++ 中排序的首选方案。

音乐

音乐

给我这些排序的特点、原理、cpp可实现代码，方便我学习以及亲自手敲代码#

1. 选择排序（Selection Sort）#

特点#

原理#

C++实现#

2. 冒泡排序（Bubble Sort）#

特点#

原理#

C++实现#

3. 插入排序（Insertion Sort）#

特点#

原理#

C++实现#

4. 希尔排序（Shell Sort）#

特点#

原理#

C++实现（步长采用n/2递减）#

5. 快速排序（Quick Sort）#

特点#

原理#

C++实现（随机枢轴优化）#

6. 归并排序（Merge Sort）#

特点#

原理#

C++实现#

7. 堆排序（Heap Sort）#

特点#

原理#

C++实现#

8. 计数排序（Counting Sort）#

特点#

原理#

C++实现（假设数据范围为[minVal, maxVal]）#

9. 基数排序（Radix Sort）#

特点#

原理#

C++实现（按低位排序，基数为10）#

10. 桶排序（Bucket Sort）#

特点#

原理#

C++实现（假设数据范围为[0,1)的浮点数）#

11. 锦标赛排序（Tournament Sort）#

特点#

原理#

C++实现（最小值锦标赛）#

12. Tim排序#

特点#

原理#

C++实现（简化版，实际实现复杂）#

学习建议#

如果我想偷懒调用库函数，如何写，或者调用?#

1. 调用 std::sort（快速排序的优化版本，非稳定排序）#

特点：#

使用方法：#

2. 调用 std::stable_sort（稳定排序）#

特点：#

使用方法：#

3. 对自定义类型排序（需提供比较规则）#

总结：#

sort和qsort区别在哪里？#

1. 所属标准与头文件#

2. 函数原型与参数#

qsort 原型：#

sort 原型（简化版）：#

3. 支持的数据类型#

4. 比较函数的差异#

qsort 的比较函数：#

sort 的比较器：#

5. 排序算法与性能#

6. 稳定性#

7. 使用示例对比#

排序 int 数组：#

排序自定义类型：#

总结：如何选择？#

介绍一下std::sort函数的时间复杂度#

1. 底层算法：内省排序（Introsort）#

2. 时间复杂度的保证#

1. 调用 `std::sort`（快速排序的优化版本，非稳定排序）#

2. 调用 `std::stable_sort`（稳定排序）#

`qsort` 原型：#

`sort` 原型（简化版）：#

`qsort` 的比较函数：#

`sort` 的比较器：#

排序 `int` 数组：#