版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/tianxiawushanu/article/details/142660275
1. 排序的概念及其应用
在正式讲解插入排序和希尔排序之前,我要带着大家理解我们为什么需要排序?以及排序在我们生活中有什么应用?学完这些之后,大家也许对排序算法就不会那么迷茫了。
1.1 排序的概念
排序:所谓排序,就是使一串记录,按照我们特定且可行的想法,递增或递减的排列起来的操作。
排序是一项操作!
1.2 排序的应用
看到这里,大家可以打开京东商城,当你想买一台新的手机时,却不知如何入手。你可能会选择按好评数来进行排序,从而选出好评率最高的手机。在这个过程,就用到了排序的思想。
再如,我们的大学按照教学资源以及教学能力,也能进行排序:
当然,生活中还有很多例子都是用到了排序的思想。这就是所谓处处有排序!
好了,在了解完排序的重要性之后,我们就要正式迈入学习插入排序和希儿排序的殿堂中了。
2. 插入排序
插入排序,通常我们也称它为直接插入排序。
2.1 基本思想
在一个有序的数组中,按照一定的规则插入待排序的数字。
详细一点说的话,就是:
算法思路:
先从单趟排序讲起,我们可以选择待插入的数字与从排序好的数组末端的数进行比较。若发现该值比待插入的数字要大,则将盖子往后挪动一位,接着继续往前面进行比较。若发现该值比待插入的数字要小,说明该值的后面一个位置就是待插入数字应该插入的位置,我们就可以结束循环了。
单趟排序讲完了之后,就可以将一个完整的插入排序了。
如果你真的认证解读了单趟插入排序的思路,你会发现插入排序不过如此!
其实一个完成的插入排序就是在循环地跑单趟排序,循环地初始条件为从待插入数组的第二个元素小标开始。每当单趟排序跑完之后,我们都得设置循环条件的值(一开始比较数组末端的位置)。因为你已经排好了部分数组,每当来一个新数字就得在拍好数组中插入,重复上述过程。
下面我给大家展示插入排序算法的动图,希望大家能够结合上述的话语,仔细观看:
2.2 插入排序的代码实现
void InsertSort(int* a, int n){
for (int i = 1; i < n; i++)
{
int end = i - 1; //待排序数组的末端
//也可以写成int tmp = a[end + 1];
int tmp = a[i]; //tmp存放的是待插入的数值
while (end >= 0)
{
if (tmp < a[end]) //待插入数字与数组末端的值进行比较
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
2.3 插入排序算法总结
根据上面的代码,我们可以总结出一些关于插入排序算法的特征:
元素集合越接近有序,直接插入排序算法的时间效率就越高
- 时间复杂度:O(N^2)
- 空间复杂度:O(1)
,它是一种稳定的排序算法
稳定性:稳定
3. 希尔排序
希尔排序又称缩小增量排序。
3.1 基本思想
先选定一个整数(gap),把待排序的数据分成个别组。分组的标准就是所有距离为gap的数据分在同一组,并对每一组内的记录进行排序。然后,缩小gap的值,重复上述分组和排序的工作。当gap = 1时,就相当于直接插入排序了。
上面这个思想很重要,是理解希尔排序的核心!
给大家举个例子:
3.2 希尔排序的代码实现
void ShellSort(int* a, int n){
int gap = n;
while (gap > 1)
{
//gap /= 2;
gap = gap / 3 + 1;
for (int j = 0; j < gap; j++)
{
//就是在对每组(隔gap位置的数字)的数据进行插入排序
for (int i = j; i < n; i += gap)
{
int end = i - 1;
int tmp = a[i];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
}
3.3 希尔排序的特征总结