目录一.直接插入排序1.1直接插入排序引入1.2直接插入排序的核心思想与算法分析1.3实例说明1.4直接插入排序代码实现1.5直接插入排序性能分析二.希尔排序2.1希尔排序引入2.2
排序是我们生活中经常会面对的问题,以打扑克牌为例,你摸的手牌肯定是杂乱的,你一定会将小牌移动到大牌的左面,大牌移动到小牌的右面,这样顺序就算理好了。这里我们的理牌方法就是直接插入排序。
核心思想: 就是将一个记录插入到已经排好序的有序表中,从而得到一个新的记录数增1的有序表。
算法分析:
以12,2,9,8,18,7这几个数字为例,排序过程:
代码如下:
void InsertSort(int* arr, int len)
{
//assert arr!=NULL
for (int i = 1; i < len; i++)//一共跑了多少趟 //01234 12345
{
int tmp = arr[i];//待插入的值
//j 指向 这一趟开始的时候的已排序好的队列中最后一个值的下标
int j;
for (j = i - 1; j >= 0; j--)//这里控制待插入的值和 已排序队列的挨着比较(从右向左比较)
{
if (arr[j] <= tmp)
{
break;//这时应该停下来
}
else
{
arr[j + 1] = arr[j];
}
}
arr[j + 1] = tmp;
}
}
时间复杂度:
(1)顺序排序时,只需比较(n-1)次,插入排序时间复杂度为O(n);
(2)逆序排序时,需比较n(n-1)/2次,插入排序时间复杂度为O(n^2);
(3)当原始序列杂乱无序时,平均时间复杂度为O(n^2)。
空间复杂度:
插入排序过程中,需要一个临时变量temp存储待排序元素,因此空间复杂度为O(1)。
算法稳定性:
插入排序是一种稳定的排序算法。
希尔排序其实就是对直接插入排序的优化,在第一部分我们说过==(1)直接插入排序数据越有序,插入的效率就越高;(2)记录数比较少时,直接插入的优势也很明显。==希尔排序就是根据这两个特点进行的优化。
核心思想: 通过一个不断缩小的增量序列,对无序序列反复的进行拆分并且对拆分后的序列使用插入排序的。
算法分析:
以12,2,9,8,5,88,99,10,7,17,77,66,89,10,21为例,排序过程如下:
代码如下:
void shell(int arr[], int len, int gap)//一趟希尔排序
{
for (int i = gap; i < len; i++)//i++ 不是i=i+gap;
{
int tmp = arr[i];//待插入的值
//j 指向 这一趟开始的时候的已排序好的队列中最后一个值的下标
int j;
for (j = i - gap; j >= 0; j = j - gap)//这里控制待插入的值和 已排序队列的挨着比较(从右向左比较)
{
if (arr[j] <= tmp)
{
break;//这时应该停下来
}
else
{
arr[j + gap] = arr[j];
}
}
arr[j + gap] = tmp;
}
}
void ShellSort(int arr[], int len)
{
int gap[] = { 5, 3, 1 };//
int gap_len = sizeof(gap) / sizeof(gap[0]);
for (int i = 0; i < gap_len; i++)
{
Shell(arr, len, gap[i]);
}
}
时间复杂度:
希尔排序的时间复杂度依赖于增量序列的函数,当n在某个特定的范围后最优的情况下,希尔排序的时间复杂度为O(n ^ 1.3),在最差的情况下,希尔排序的时间复杂度为:O(n ^ 2)。
空间复杂度:
希尔排序的空间复杂度:O(1)。
算法稳定性:
希尔排序并不是一种稳定的排序算法。
到此这篇关于C语言深入探究直接插入排序与希尔排序使用案例讲解的文章就介绍到这了,更多相关C语言排序内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!
--结束END--
本文标题: C语言深入探究直接插入排序与希尔排序使用案例讲解
本文链接: https://www.lsjlt.com/news/149413.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0