数据结构（排序（上））：冒泡、选择、插入
数据结构（排序（上））：冒泡、选择、插入排序
[作者的个人gitee▶️](友人A (friend-a188881041351) - Gitee.com)
每日一言：“人生是一场盛大的修行，我们在时光的长河中，不断与自己和解，与世界对话。🌸🌸每一次挫折都是灵魂的磨砺，每一次成长都是生命的馈赠😊”
一.冒泡排序
1.基本概念：
冒泡排序是一种简单的排序算法。它重复地遍历要排序的序列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历序列的工作是重复地进行，直到没有再需要交换，也就是说该序列已经排序完成。
这个算法的名字由来是因为越小（或越大）的元素会经由交换慢慢“浮”到数列的顶端。
2.工作原理
- 外层循环
- 外层循环控制排序的轮数。对于一个包含 n 个元素的数组，需要进行 n - 1 轮比较。例如，对于数组 [5, 3, 8, 6, 2]，有 5 个元素，所以需要进行 4 轮比较。
- 内层循环
- 内层循环负责每一轮中的比较和交换操作。在第 i 轮比较中，内层循环会比较相邻的元素，从数组的第 1 个元素开始，比较第 i 个元素和第 i + 1 个元素。如果第 i 个元素大于第 i + 1 个元素（对于升序排序），就交换它们的位置。
- 随着排序的进行，每一轮比较的次数会逐渐减少。在第 i 轮比较时，只需要比较 n - i 次。因为经过前 i - 1 轮排序后，数组的最后 i - 1 个元素已经是排好序的了，不需要再比较。
3.代码示例
void BubbleSort(vector<int>& arr)
{
//外层循环每循环一次就使一个数去到正确的位置
for (int i = 0; i < arr.size(); i++)
{
for (int j = 0; j < arr.size() - 1 - i; j++)
{
if (arr[j] > arr[j+1])
swap(arr[j], arr[j+1]);
}
}
}
二.选择排序
1.基本概念
选择排序（Selection Sort）是一种简单直观的排序算法。它的基本思想是：在每一轮排序中，从未排序的部分选择一个最小（或最大）的元素，将其放到已排序部分的末尾。通过不断选择最小（或最大）的元素，逐步构建有序序列。
2.工作原理
- 初始状态
- 假设有一个数组，初始时整个数组都是未排序的。例如，对于数组 [64, 25, 12, 22, 11]，所有元素都未排序。
- 选择最小元素
- 在第一轮排序中，从整个数组中找到最小的元素（这里是 11），将其与数组的第一个元素（64）交换位置。此时，数组的第一个位置已经排好序，数组变为 [11, 25, 12, 22, 64]。
- 缩小未排序范围
- 在第二轮排序中，从剩下的未排序部分（从第二个元素开始，即 [25, 12, 22, 64]）中找到最小的元素（这里是 12），将其与未排序部分的第一个元素（25）交换位置。此时，数组变为 [11, 12, 25, 22, 64]。
- 重复操作
- 每一轮都在缩小的未排序部分中选择最小的元素，将其放到已排序部分的末尾。重复这个过程，直到整个数组排序完成。
3.代码示例
void SelectSort(vector<int>& arr)
{
if (arr.size() <= 1)
return;
for (int i = 0; i < arr.size(); i++)
{
int minIndex = i;//假设最小数位置是i
for (int j = i + 1; j < arr.size(); j++)//j是i+1的位置，遍历i+1~n-1位置
{
if (arr[j] < arr[minIndex])//如果j位置的数比i小，则更新minIndex，使它指向最小元素
minIndex = j;
//每次内层循环结束后，minIndex的值已经是i+1~n-1区间内最小值的索引
}
//交换arr[i]与arr[minIndex]即可，此刻就保证了i位置的值是最小值
swap(arr[i],arr[minIndex]);
}
}
三.插入排序
1.基本概念
插入排序（Insertion Sort）是一种简单直观的排序算法。它的基本思想是：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。类似于整理扑克牌的过程，每次从牌堆中抽出一张牌，插入到已经排好序的牌中合适的位置。
2.工作原理
- 初始状态
- 假设有一个数组，初始时第一个元素被视为已排序部分，其余元素为未排序部分。例如，对于数组 [5, 2, 4, 6, 1, 3]，初始时 5 是已排序部分，其余是未排序部分。
- 插入操作
- 从未排序部分取出第一个元素（这里是 2），将其插入到已排序部分的合适位置。已排序部分只有一个元素 5，2 比 5 小，所以 2 插入到 5 的前面，数组变为 [2, 5, 4, 6, 1, 3]。
- 重复操作
- 继续从未排序部分取出下一个元素（这里是 4），将其插入到已排序部分的合适位置。已排序部分是 [2, 5]，4 插入到 2 和 5 之间，数组变为 [2, 4, 5, 6, 1, 3]。
- 重复这个过程，直到未排序部分为空，整个数组排序完成。
3.代码示例
void InsertSort_2(vector<int>& arr)
{
if (arr.size() == 0 || arr.size() == 1)
return;
for (int i = 0; i < arr.size(); i++)
{
int end = i;//指向有序序列最后一个位置
int tmp = arr[end + 1];//保存要插入的元素
while (end >= 0)//一次内层循环使待插入元素依次与已排序元素比较
{
//如果待插入元素小于end指向的元素，就先让tmp保存待排序元素
//之后将end指向的元素向后挪动覆盖
//之后end--，tmp再与end指向元素比较，直到end减为-1或符合else条件，循环结束
if (arr[end] > tmp)
{
arr[end + 1] = arr[end];
end--;
}
else
break;
}
arr[end + 1] = tmp;
}
}