冒泡排序
算法思路
每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。
一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
第一次冒泡操作.png
经过一次冒泡操作之后，6 这个元素已经存储在正确的位置上。要想完成所有数据的排序，我们只要进行 6 次这样的冒泡操作就行了。
image.png
void bubleSort(vector<int>& vec)
{
for (int i = 0; i < vec.size(); i++)
{
// 提前退出冒泡循环的标志位
bool flag = false;
for (int j = 0; j < vec.size() - i - 1; ++j)
{
if (vec[j] > vec[j+1])
{
swap(vec[j], vec[j+1]);
flag = true;
}
}
if (!flag) break; // 扫描一趟没有发生交换时，说明当前索引右边元素已经有序。
}
}
特点
冒泡排序是原地排序算法吗？
冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。冒泡排序是稳定的排序算法吗？
冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。-
冒泡排序算法的时间复杂度是多少？
若序列是有序的，则只需要一趟扫描就可以结束，此时，比较次数为n-1，移动次数也为0，此时情况最好。
-
若序列是逆序的，则需要比较n(n-1)/2，交换n(n-1)/2。此时情况最差。
image.png
平均时间 最差 最佳 辅助空间 稳定性 O(n^2) O(n^2) O(n) O(1) 稳定
选择排序
算法思路
选择排序会将整个数组分为已排序区间和未排序区间，每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
image.png
void selectSort(vector<int> &vec)
{
for (int i = 0; i < vec.size(); i++)
{
int minIndex = i;
for (int j = i+1; j < vec.size(); j++)
{
if (vec[j] < vec[minIndex])
{
minIndex = j;
swap(vec[i], vec[minIndex]);
}
}
}
}
特点
选择排序是原地排序算法吗？
选择排序空间复杂度为 O(1)，是一种原地排序算法。选择排序是稳定的排序算法吗？
选择排序是一种不稳定的排序算法，选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。
比如 5，8，5，2，9 这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了，所以就不稳定了。-
选择排序算法的时间复杂度是多少？
选择排序有2个鲜明特点：- 运行时间和输入无关，对于长度为N的数组，选择排序需要N(N-1)/2次比较和N次交换
- 数据移动最少，选择排序用了N次交换，交换次数和数组大小是线性关系。其他任何算法不具备这个特征，大部分都是线性对数或者平方。
平均时间 最差 最佳 辅助空间 稳定性 O(n^2) O(n^2) O(n^2) O(1) 不稳定
