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
        while (j >= 0 && arr[j] > key) {
10
            arr[j + 1] = arr[j];
11
            --j;
12
        }
13
        arr[j + 1] = key;
14
    }
15
}

（其余排序算法代码略，请参考完整文章）

音乐

音乐

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

1. 选择排序（Selection Sort）#

特点#

原理#

C++实现#

2. 冒泡排序（Bubble Sort）#

特点#

原理#

C++实现#

3. 插入排序（Insertion Sort）#

特点#

原理#

C++实现#

支持与分享

音乐

目录