排序算法-插入排序(直接插入排序、Shell排序)
2022/3/3 7:16:31
本文主要是介绍排序算法-插入排序(直接插入排序、Shell排序),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
排序算法-插入排序
- 一、直接插入排序
- 二、Shell排序(希尔排序)
一、直接插入排序
视频讲解
基本思想: 将第一个元素看成一个有序子序列,再依次从第二个元素起逐个插入这个有序的子序列中。
一般情况下,在第i步上,将elem[i]插入到由elem[0]~elem[i-1]构成的有序子序列中。
平均时间复杂度:O(n^2)
代码实现(C++):
template <class ElemType> void StraightInsertSort(ElemType elem[], int n) //操作结果:对数组elem做直接插入排序 { for (int i = 1; i < n; i++) { //第i趟直接插入排序 //暂存elem[i] ElemType e = elem[i]; //临时变量 int j = 0; for (j = i - 1; j >= 0 && e < elem[j]; j--) { //将比e大的元素都向后移 //后移 elem[j + i] = elem[j]; } //j+1为插入位置 elem[j + 1] = e; } }
二、Shell排序(希尔排序)
视频讲解
基本思想: 先将整个待排序的元素序列分割成若干子序列,分别对各子序列进行直接插入排序,等整个序列中的元素“基本有序”时,再对全体元素进行一次直接插入排序。
代码实现(C++):
template <class ElemType> void ShellInsert(ElemType elem[], int n, int incr) //操作结果:对数组elem做一趟增量为incr的Shell排序, //对插入排序的修改是子序列中前后向量记录的增量为incr而不是1 { for (int i = incr; i < n; i++) { //第i-incr+1趟插入排序 //暂存elem[i] ElemType e = elem[i]; //临时变量 int j = 0; for (j = i - incr; j >= 0 && e < elem[j]; j -= incr) { //将子序列中比e大的元素都后移 //后移 elem[j + incr] = elem[j]; } //j+incr为插入位置 elem[j + incr] = e; } } template <class ElemType> void ShellSort(ElemType elem[], int n, int inc[], int t) //操作结果:按增量序列inc[0...t-1]对数组elem做Shell排序 { for (int k = 0; k < t; k++) { //第k+1趟Shell排序 ShellInsert(elem, n, inc[k]); } }
这篇关于排序算法-插入排序(直接插入排序、Shell排序)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南