排序算法——折半插入排序

川长思鸟来 2022-06-12 00:19 210阅读 0赞

## 前言 ##

之前已经介绍过了插入排序的原理了。但是对于插入位置的选择就可以通过二分查找法的方式进行求取，加快算法运行。

## 1. 编码 ##

template<typename T> struct Disp
    {
        void operator()(T value)
        {
            cout << value << "\t";
        }
    };
    
    //折半插入排序
    void InsertSort2(std::vector<int>& vec)
    {
        int len(vec.size());
        if(len == 0) return;
        cout << "display origin array:" << endl;
        for_each(vec.begin(), vec.end(), Disp<int>());  //打印原始的数据
    
        for(int i=1; i<len; ++i)
        {
            int left(0), midle(-1), right(i-1),temp(vec[i]);
            while(left < right) //使用二分查找的思想，在已知序列里面找到需要操作的位置
            {
                midle = (right-left)/2; //得到中间位置
                if(vec[midle] > temp) right = midle - 1;  //当前的中位数大于参考值了，那么向左右移动（变小）
                else left = midle + 1;  //当前的中位数小于参考值了，那么向右移动（变大）
            }
    
            for(int j=i-1; j>=left; --j)    //将数据low~j的数据向右移动
                vec[j+1] = vec[j];
    
            vec[left] = temp;
        }
    
        cout << "\narray sorted:" << endl;
        for_each(vec.begin(), vec.end(), Disp<int>());
    }

![SouthEast][]

[SouthEast]: /images/20220612/d884a2643cf8438e8a801014e7453376.png

发表评论取消回复

表情：

评论列表（有 0 条评论，210人围观）

还没有评论，来说两句吧...

相关阅读

相关折半插入排序

折半插入排序算法及测试 package sort; //折半插入排序 public class BinaryInsertSortTest \{ public st

小鱼儿/ 2024年02月17日 15:31/ 0 赞/ 3 阅读

相关折半插入排序

折半插入排序： include <stdio.h> define MaxSize 20 typedef int KeyType; //定义关键字类

左手的ㄟ右手/ 2023年03月13日 03:00/ 0 赞/ 19 阅读

相关【白话排序算法】折半插入排序法

之前的文章介绍了[简单插入排序法][Link 1]。我们知道插入排序的核心操作是在子序列中找到要插入的位置并插入。其实子序列本身是有序的，所以在有序的子序列中，我们完全可以使用

た入场券/ 2022年12月23日 03:26/ 0 赞/ 231 阅读

相关折半插入排序法---排序算法(二)

1.排序原理折半插入排序法是对直接插入排序法的改进，直接插入排序法([http://blog.csdn.net/whzhaochao/article/d

╰+哭是因爲堅強的太久メ/ 2022年09月17日 13:18/ 0 赞/ 170 阅读

相关折半插入排序

2016年7月28日08:21:18 折半插入排序:折半插入排序算法是对直接插入排序算法的改进,它的主要改进在于在已经有序的子集中确定待排序元素的位置

亦凉/ 2022年07月16日 13:41/ 0 赞/ 200 阅读

相关折半插入排序

2016年7月28日08:21:18 折半插入排序:折半插入排序算法是对直接插入排序算法的改进,它的主要改进在于在已经有序的子集中确定待排序元素的位置

秒速五厘米/ 2022年07月13日 23:47/ 0 赞/ 206 阅读

相关排序算法——折半插入排序

前言之前已经介绍过了插入排序的原理了。但是对于插入位置的选择就可以通过二分查找法的方式进行求取，加快算法运行。 1. 编码 template<typen

川长思鸟来/ 2022年06月12日 00:19/ 0 赞/ 211 阅读

相关排序算法——插入排序（直接插入排序、折半插入排序、希尔排序）

插入排序有直接插入排序、折半插入排序、希尔排序等直接插入排序直接插入排序的核心是不断将后面的数字，不断插入前面已经排好序的数列中；在进行插入排序时需要不断将需要

素颜马尾好姑娘i/ 2022年06月11日 08:07/ 0 赞/ 254 阅读

相关折半插入排序

插入的基本思想 ①每次插入，都从前面的有序子表中查找出待插入元素应该被插入的位置；　　②给插入位置腾出空间，将待插入元素复制到表中的插入位置。　　注意到该算法中，

待我称王封你为后i/ 2022年05月09日 08:28/ 0 赞/ 268 阅读

相关插入排序——折半插入排序

折半插入排序是基于直接插入排序的优化。 [直接插入排序][Link 1] 将第i个元素插入时，通过折半查找的方式，来查找第i个元素合适的位置。推导过程当0~

悠悠/ 2021年12月13日 14:45/ 0 赞/ 321 阅读