经典算法之折半插入排序

简介: 经典算法之折半插入排序

在这里插入图片描述

前言:
✌ 作者简介:游坦之 ✌
🏆 大学软件工程在读,希望学到真本领,经世致用 🏆
📫 如果文章知识点有错误的地方,请指正!和大家一起学习,一起进步👀
💬 人生格言:丑且益坚,病当益壮💬
🔥 如果感觉博主的文章还不错的话,还请👍关注、点赞、收藏三连支持👍一下博主哦

在这里插入图片描述
@TOC

🍳折半插入排序

🔍什么是折半查找

​ 折半插入排序是对插入排序算法的一种改进。所谓插入排序,就是不断的依次将元素插入前面已排好序的序列中。说白了,就是将一个集合,分为有序区和无序区,前区是有序区,后区是还没有处理的集合数据,前区的范围从0到n,后区的范围从n到0,其中n是集合中元素的数量。

🎍举个栗子

​ 对元素{5,3,2,1,4}进行从小到大的排序。此时index为0,代表有序区元素的数量,同时代表指向当前要排序的元素。

​ 第一次,因为有序区元素为0,所以把元素直接放在有序区的第一个,此时index更新为1。(红色方块代表排序完了)

在这里插入图片描述

​ 第二次,此时指向第二个元素也就是3,因为此时有序区元素不为空,所有在有序区内进行二分查找一次进行比较。(0+1/2 = 0 ),所以与第0个元素5比较,3<5,5元素往后移动一个,3放到5原来的位置,index更新为2。

在这里插入图片描述

​ 第三次,重复上述过程,2放在了3的原位置,index更新为3。

​ 第四次,重复上述过程,1又放在了2的原位置。index更新为4。

在这里插入图片描述

​ 第五次,重复上述过程,index更新为5。排序完毕。
在这里插入图片描述

🎷思考

​ 折半插入排序的时间复杂度,由于该算法需要遍历所有的元素,也就是n。对于每一个元素来说,又需要一次二分查找,时间复杂度也就是logm,综上,折半插入排序的时间复杂度即为O(nlogn)。

​ 折半插入排序的退出条件,当index==n的时候,即对所有的元素排序完毕之后,退出排序。

🎈实战演练

对{5,1,3,2,4}进行折半插入排序的算法实现

#include <iostream>
using namespace std;
const int M = 1010;
int n; 
int temp;
int index = 0;
int a[M]; 
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<n;i++)
    {
        if(index==0)
        {
            index++;
        }else{
            int l = 0;
            int r = index;
            int mid;
            while(l<=r&&mid<=i)
            {
                 mid = (l+r)/2;
                if(a[mid]>a[i])
                {
                    r = mid-1;
                }else if(a[mid]<a[i])
                {
                    l = mid+1;
                }else{
                    break;
                }
            }
            if(a[i]<a[mid])
            {
                
                temp = a[i];
                for(int j=i-1;j>=mid;j--)
                {
                    a[j+1] = a[j];
                }
                a[mid] = temp;
            }else{
                temp = a[i];
                for(int j=i-1;j>=mid+1;j--)
                {
                    a[j+1] = a[j];
                }
                a[mid+1] = temp;
            } 
            index++;
        }
            cout<<"排序"<<index<<"次的情况是:"<<endl; 
        for(int i=0;i<n;i++)
        {
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }
    
    return 0;
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tDLazIUi-1660119708394)(C:\Users\86158\AppData\Roaming\Typora\typora-user-images\image-20220810161953171.png)]

✨$\textcolor{blue}{原创不易}$ <br/>
👍 $\textcolor{green}{点赞,不会损失一匹布}$ <br/>
⭐️ $\textcolor{green}{收藏,不会丢掉一厘金}$ <br/>
✏️ $\textcolor{green}{留下痕迹,却会温暖作者的心!}$ <br/>

在这里插入图片描述

相关文章
|
2月前
|
算法 搜索推荐
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
本文介绍了冒泡排序、选择排序和插入排序三种基础排序算法的原理、实现代码和测试结果。
21 0
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
|
2月前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
25 0
|
2月前
|
搜索推荐 算法
【排序算法(一)】——插入排序,选择排序 —> 深层解析
【排序算法(一)】——插入排序,选择排序 —> 深层解析
|
5月前
|
算法 搜索推荐 C#
|
6月前
|
机器学习/深度学习 算法 搜索推荐
数据结构算法--2 冒泡排序,选择排序,插入排序
**基础排序算法包括冒泡排序、选择排序和插入排序。冒泡排序通过相邻元素比较交换,逐步将最大值“冒”到末尾,平均时间复杂度为O(n^2)。选择排序每次找到剩余部分的最小值与未排序部分的第一个元素交换,同样具有O(n^2)的时间复杂度。插入排序则类似玩牌,将新元素插入到已排序部分的正确位置,也是O(n^2)复杂度。这些算法适用于小规模或部分有序的数据。**
|
6月前
|
算法 搜索推荐
数据结构与算法-插入排序
数据结构与算法-插入排序
32 2
|
6月前
|
算法 搜索推荐 数据可视化
【漫画算法】插入排序:插入宝石的传说
【漫画算法】插入排序:插入宝石的传说
|
6月前
|
人工智能 搜索推荐 JavaScript
心得经验总结:排序算法:插入排序法(直接插入法和希尔排序法)
心得经验总结:排序算法:插入排序法(直接插入法和希尔排序法)
40 0
|
6月前
|
机器学习/深度学习 搜索推荐 算法
【C/排序算法】:直接插入排序和希尔排序
【C/排序算法】:直接插入排序和希尔排序
45 0
|
6月前
|
搜索推荐 算法
排序算法之插入排序
排序算法之插入排序
46 0