✨✨ 欢迎大家来到贝蒂大讲堂✨✨
🎈🎈养成好习惯，先赞后看哦~🎈🎈
所属专栏：数据结构与算法
贝蒂的主页：Betty’s blog
1. 冒泡排序
1.1. 算法思想
**冒泡排序(Bubble Sort)**是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
1.2. 算法步骤
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这样就将最大的元素移动至最后，相当于这个元素已经排序完成。
- 针对所有的元素重复以上的步骤，除了已完成排序元素。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
特别注意：如果一轮之后，元素并没有发生任何交换则说明此时排序已经完成，可以提前结束循环。
1.3. 动图演示
1.4. 代码实现
void swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void BubbleSort(int* arr, int len)//冒泡排序
{
int flag = 0;//标记是否交换
for (int i = 0; i < len - 1; i++)//交换元素个数
{
for (int j = 0; j < len - 1 - i; j++)//交换次数
{
if (arr[j] > arr[j + 1])
{
swap(&arr[j], &arr[j + 1]);
flag = 1;
}
}
if (flag == 0)//未发生交换，则排序已完成
{
break;
}
}
}
1.5. 复杂度分析
- 时间复杂度：以最坏的情况来算，O(N)=n-1+n-2+n-3+…+2+1=n(n-1)/2=>时间复杂度为O(N2)。
- 空间复杂度：没有开辟额外的空间大小，所以空间复杂度为O(1)。
2. 选择排序
2.1. 算法思想
**选择排序(Selection Sort)**也是一种比较直观的排序，它通过每次遍历数组选出最小或最大元素，然后与起始或者末尾位置交换，不断缩小区间，依次循环达到排序的目的。
2.2. 算法步骤
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
2.3. 动图演示
2.4. 代码实现
2.4.1. 优化前
void SelectSort(int* arr, int len)//选择排序
{
for (int i = 0; i < len - 1; i++)//起始位置
{
int mini = i;
for (int j = i + 1; j < len; j++)//寻找最小元素
{
if (arr[j] < arr[mini])
{
mini = j;
}
}
swap(&arr[mini], &arr[i]);
}
}
2.4.2. 优化后
对于选择排序我们可以进行一些优化，我们可以同时选择最大与最小的元素，同时往起始与结尾位置交换。
特别注意：同时交换可能会改变原先最大或者最小元素的位置，这时我们就需要特殊判断一下。
void SelectSort(int* arr, int len)//选择排序
{
int begin = 0;
int end = len - 1;
while (begin < end)
{
int mini = begin;
int maxi = begin;
for (int i = begin + 1; i <= end; i++)
{
if (arr[mini] > arr[i])
{
mini = i;
}
if (arr[maxi] < arr[i])
{
maxi = i;
}
}
swap(&arr[mini], &arr[begin]);
//如果begin与maxi重合，则需要更新maxi
if (begin == maxi)
{
maxi = mini;
}
swap(&arr[maxi], &arr[end]);
begin++;
end--;
}
}
2.5. 复杂度分析
- 时间复杂度：无论是优化前后，每次都需要遍历寻找最小或者最大元素，所以时间复杂度为O(N2)。
- 空间复杂度：没有开辟额外的空间大小，所以空间复杂度为O(1)。
3. 插入排序
3.1. 算法思想
**插入排序(Insert Sort)**是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。它的思想类似于我们打扑克牌时的整理。
3.2. 算法步骤
- 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
- 从尾到头依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
- 依次重复1,2步骤，直至插入完成。
3.3. 动图演示
3.4. 代码实现
void InsertSort(int* arr, int len)//插入排序
{
for (int i = 0; i < len - 1; i++)
{
int end = i;//从末尾开始插入
int tmp = arr[i + 1];//保存插入元素
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + 1] = arr[end];
end--;
}
else
{
break;//找到合适位置
}
}
arr[end + 1] = tmp;//插入
}
}
3.5. 复杂度分析
- 时间复杂度：每次插入都可能移动元素，以最坏的情况来说时间复杂度为O(N2)。
- 空间复杂度：没有开辟额外的空间大小，所以空间复杂度为O(1)。
4. 希尔排序
4.1. 算法思想
**希尔排序(Shell Sort)**是插入排序的一种优化，它先通过gap将整个待排元素序列分割成若干个子序列，然后分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
希尔排序的本质就是通过gap的预排序让数据接近有序，然后再使用插入排序大大提升插入的效率。
4.2. 算法步骤
- 选取一个gap对数据进行分组，每间隔gap个元素分为一组，一共gap组。
- 以gap为基准单位，对其进行插入排序。
- 依次缩小gap的范围，直至gap为1，相当于进行一次正常的插入排序。
4.3. 动图演示
4.4. 代码实现
void ShellSort(int* arr, int len)//希尔排序
{
int gap = len;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < len - gap; i++)
{
int end = i;//从末尾开始插入
int tmp = arr[i + gap];//保存插入元素
while (end >= 0)
{
if (arr[end] > tmp)
{
arr[end + gap] = arr[end];
end-=gap;
}
else
{
break;//找到合适位置
}
}
arr[end + gap] = tmp;//插入
}
}
}
4.5. 复杂度分析
- 时间复杂度：希尔排序的时间复杂度一般较为难计算，通过大量测验一般认为其时间复杂为O(N1.3 )。
- 空间复杂度：没有开辟额外的空间大小，所以空间复杂度为O(1)。