排序算法作为最经典的算法
排序算法本质上是将数字按照顺序排列
下面将介绍比较经典的排序算法，以从小到大排序为例子
并且使用C++实现
IDE：visual Studio
数组长度为设为n

冒泡排序 (Bubble Sort)

定义

冒泡排序的核心思想是比较相邻两位数字大小，根据结果进行交换，遍历一次数组即为一轮，每遍历一轮既可以确定一个数字所在位置，遍历n轮后即排序结束，由于数字移动的方式像是冒泡一样挪过去，被称为冒泡排序。

详解

在冒泡排序中，第一次许比较n-1次，第二轮需要比较n-2次，比较n轮，根据等差序列通项和公式
$$S_n = \frac{n(a_1 + a_n)}{2} $$
可以近似将比较次数记为$\frac{n^2}{2}$因此冒泡排序的时间复杂度是$O(n^2)$

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<cstdlib>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++)  
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
int main() {
	int arr[] = { 4,3,5,7,9,2,1,8,6 };
	bubbleSort(arr, sizeof(arr) / sizeof(arr[0]));
	cout << "排序后结果为";
	for (size_t i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
	system("pause");
	return 0;
}

选择排序（Selection Sort）

定义

选择排序的核心是每一次循环找到最大值or最小值,将其移动到对应位置，每次循环要经历n-k，k为当前循环的次数，总共要循环n次。

详解

选择排序的执行逻辑可拆解为 “找最小值索引 + 交换位置” 两步，核心过程和复杂度分析如下：
总共比较次数为$S_n=\frac{n(n-1)}{2}$ 因此冒泡排序的时间复杂度是$O(n^2)$

与冒泡排序比较

选择排序的比较次数和冒泡排序一致，但交换次数远少于冒泡排序（冒泡每轮可能多次交换，选择排序每轮仅最多 1 次交换），因此实际执行效率通常略高于冒泡排序。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<cstdlib>
#include<vector>
using namespace std;
void selectSort(vector<int>& vec) {
	for (int i = 0; i < vec.size()-1; i++)
	{
		int minIndex = i;
		for (int j = i+1; j < vec.size(); j++) {
			if (vec[minIndex] > vec[j]) {
				minIndex = j;
			}
		}
		int temp = vec[i];
		vec[i] = vec[minIndex];
		vec[minIndex] = temp;
	}
};
int main()
{
	vector<int> vec = { 1,2,3,5,7,9,4,6,8 };
	selectSort(vec);
	cout << "排序过后为";
	for (size_t i = 0; i < vec.size(); i++)
	{
		cout << vec[i];
	}cout << endl;
	system("pause");
}

插入排序（Insertion Sort）

定义

插入排序的核心是在数列中建立一个局部有序数列，通过不断向有序数列添加新的数字，最后当有序数列大小等于数列大小时即排序结束

详解

先将数列中的第一项看做是一个有序数列，接着查找第二项，将其与第一项合并并且保持数列规律，再查找第三项，同理将其并入先前的有序数列，当所有项都进去时即为排序结束，理论上坏情况下第一次移动1项，第二次移动2项….第n次移动n项。时间复杂度为$O(n)=n^2$

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<cstdlib>
#include<vector>
using namespace std;
void insertSort(vector<int>& vec) {
	for (size_t i = 1; i < vec.size(); i++)
	{
		int j = i - 1;
		int key = vec[i];
		while (key < vec[j]&& j>=0) {
			vec[j + 1] = vec[j];
			j--;
		}
		vec[j +1] = key;
	}


};
int main()
{
	vector<int> vec = { 1,2,3,5,7,9,4,6,8 };
	insertSort(vec);
	cout << "排序过后为";
	for (size_t i = 0; i < vec.size(); i++)
	{
		cout << vec[i];
	}cout << endl;
	system("pause");
}

堆排序 (Heapsort)

定义

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。分为大根堆和小根堆。

详解

核心的实现思路就是在堆中存储所有的数据，然后依次将对中的根取出来，并且维护堆的数据结构，就能确保取出的数据是有序的。
由于堆添加依次元素和堆的维护时间复杂度为$logN$,每个操作都要执行n次，所以堆排序的时间复杂度为$nlogn$

代码实现(等待手写复刻)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

// 调整堆：将以i为根的子树调整为最大堆
// vec: 待排序数组, n: 堆的大小, i: 当前要调整的根节点索引
void heapify(vector<int>& vec, int n, int i) {
    int largest = i;          // 初始化最大值为根节点
    int left = 2 * i + 1;     // 左子节点索引 (i的左孩子)
    int right = 2 * i + 2;    // 右子节点索引 (i的右孩子)

    // 如果左子节点大于根节点，更新最大值索引
    if (left < n && vec[left] > vec[largest]) {
        largest = left;
    }

    // 如果右子节点大于当前最大值，更新最大值索引
    if (right < n && vec[right] > vec[largest]) {
        largest = right;
    }

    // 如果最大值不是根节点，需要交换并递归调整受影响的子树
    if (largest != i) {
        swap(vec[i], vec[largest]);
        // 递归调整交换后的子树，确保其仍为最大堆
        heapify(vec, n, largest);
    }
}

// 堆排序主函数
void heapSort(vector<int>& vec) {
    int n = vec.size();

    // 1. 构建最大堆（从最后一个非叶子节点开始向前调整）
    // 最后一个非叶子节点的索引：n/2 - 1
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(vec, n, i);
    }

    // 2. 逐个提取堆顶元素（最大值），放到数组末尾
    for (int i = n - 1; i > 0; i--) {
        // 将当前堆顶（最大值）与堆的最后一个元素交换
        swap(vec[0], vec[i]);
        // 对剩余的前i个元素重新调整为最大堆（堆大小变为i）
        heapify(vec, i, 0);
    }
}


int main() {
    vector<int> vec = { 1,2,3,5,7,9,4,6,8 };
    cout << "排序前的数组：";
    for (int num : vec) {
        cout << num << " ";
    }
    cout << endl;

    heapSort(vec);

    cout << "排序后的数组：";
    for (int num : vec) {
        cout << num << " ";
    }
    cout << endl;

    system("pause");
    return 0;
}