欢迎来到 Claffic 的博客 💞💞💞
“东风随春归,发我枝上花。”
前言:
排序是日常生活中极其常见的一种算法,它的功能很简单,就是将数字按照升序/降序排列,最终形成一组有序的数字,不过形成有序数字的过程有多种实现方式,它们各有好坏,接下来,由我带你手撕排序算法。
目录
🥰写在前面
💐Part1.插入排序
1.1直接插入排序
1.1.1思想
1.1.2实现
1.2希尔排序
1.2.1思想
1.2.2实现
🌺Part2:选择排序
2.1选择排序
2.1.1思想
2.1.2实现
2.2堆排序
2.2.1思想
2.2.2实现
写在前面
排序离我们的生活很近,这是一种很重要的算法,比如:
网上购物按价格升序排序
世界500强排名
排序是常见的,也是重要的,寻找最优的排序能做到优化,所以理解掌握排序是必要的。
下面是要讲解的常见排序:
我们默认实现排升序,一个一个来:
Part1.插入排序
1.1直接插入排序
1.1.1思想
相信多数人是打牌的,你知道吗,在摸牌的时候,你就悄悄进行了插入排序操作:
这种排序就是新拿到的数字与已有的数字进行比较,确定合适的位置后进行插入操作。
结合动图深度理解:
可以看到:
• 当只有一个数字时,没有可比性,可理解为有序;
• 取下一个数字b,与前一个数字a比较,如果b小于a,则需要调整二者的位置,如果a小于b,符合升序,则不需要调整;
• 前一部分排好的数字逐渐增多,取此区间后最近的数字进行挨个比对,不是合适位置,比较过的数字就后移一位,是合适位置,就进行插入操作。
1.1.2实现
// 插入排序
void InsertSort(int* a, int n)
{
for (int i = 1; i < n; i++)
{
int tmp= a[i];
int endi = i - 1;
while (endi >= 0)
{
if (tmp < a[endi])
{
a[endi + 1] = a[endi];
endi--;
}
else
break;
a[endi + 1] = tmp;
}
}
}
特征分析:
当原数字越接近有序时,效率越高;
时间复杂度:最好:O(N) 最坏:O(N^2);
空间复杂度:O(1);
稳定性(是否动了相同数字的相对位置):稳定
这个排序看起来效率并不高,希尔在快速排序的基础上进行了优化:
1.2希尔排序
1.2.1思想
本质还是插入排序,只不过希尔做了一个巧妙的处理:引入了 gap ,每隔一个gap分为一组;
先让一部分数字相对有序,再调整下一部分,直至最后有序;
1.2.2实现
// 希尔排序
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
//gap /= 2;
gap = gap/3 + 1;
for (int i = 0; i < n - gap; i++)
{
int endi = i;
int tmp = a[i + gap];
while (endi >= 0)
{
if (tmp < a[endi])
{
a[endi + gap] = a[endi];
endi -= gap;
}
else
break;
a[endi + gap] = tmp;
}
}
}
}
注意:gap是多少并没有明确规定,一般是 gap/3+1
特征分析:
希尔排序是对直接插入排序的优化,给gap相当于进行预排序,当gap==1时数组就相当有序了,比起直接插入,会快一些;
时间复杂度:最好:O(N^1.25)~O(N^1.3) (参考《计算机程序设计技巧》--Knuth) 最坏:O(N^2);
空间复杂度:O(1);
稳定性:不稳定
Part2:选择排序
2.1选择排序
2.1.1思想
这种排序方法是我们出厂自带的排序方法,试想:给你一堆乱序的数字,你会怎么排?
通常情况下,我们会从头到尾扫一遍,选出最小的放到最前面,再扫一眼,选出第二大的放到第二位。
这就是选择排序的基本思想。
动图:
是不是挺符合认知规律的?
2.1.2实现
// 选择排序
void SelectSort(int* a, int n)
{
int left = 0, right = n - 1;
while (left < right)
{
// 初始化
int mini = left;
int maxi = left;
// 找到较大/较小值的下标
for (int i = left+1; i <= right; i++)
{
if (a[i] < a[mini]) // 前后顺序会影响结果
{
mini = i;
}
if (a[i] > a[maxi])
{
maxi = i;
}
}
Swap(&a[mini], &a[left]);
// 调试过程中会有left与maxi重叠的情况,这时需要针对这种情况调整
if (left == maxi)
maxi = mini;
Swap(&a[maxi], &a[right]);
left++;
right--;
}
}
特征分析:
直接选择排序思路易理解,但效率不高,不实用;
时间复杂度:最好:O(N^2) 最坏:O(N^2);
空间复杂度:O(1);
稳定性:不稳定
2.2堆排序
2.2.1思想
堆排序在往期 什么是堆,如何实现?(附堆排序,TOP-K问题) 中有详解,
先是建大堆,再是模拟删除操作,这里就不多说啦。
2.2.2实现
//堆排序
void HeapSort(int* a, int n)
{
//向下调整(效率更高)
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}
特征分析:
利用堆的特性,选数快很多,效率较高
时间复杂度:最坏:O(N*logN) 最好:O(N*logN) ;
空间复杂度:O(1);
稳定性:不稳定
总结:
这期是常见排序的前半部分,讲了两类排序:插入排序和选择排序,思想不难,多注意实现中的细节。我打算将后半部分放在下期:交换排序和归并排序。
码文不易 文章来源:https://www.toymoban.com/news/detail-418324.html
如果你觉得这篇文章还不错并且对你有帮助,不妨支持一波哦 💗💗💗文章来源地址https://www.toymoban.com/news/detail-418324.html
到了这里,关于【排序算法 上】带你手撕常见排序 (插入,希尔,选择,堆排序) (动图详解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!