文档章节

直接插入排序以及其改进版-二分法排序

realsa
 realsa
发布于 2016/10/10 18:01
字数 630
阅读 53
收藏 0

插入排序是一种简单直观的排序算法。 序列可以分为有序区和无序区,开始时有序区只有第一个元素,然后每次把无序区中第一个元素插入到有序区中。

当无序区为空时,排序结束。

那如何把元素插入到有序区中呢?

直接插入排序的做法是从后到前逐一比较。总时间复杂度为O(N^2)。

既然是插入到有序区,那我们可以考虑用二分法快速找到应该插入的位置,但是在顺序存储结构中,仍然无法避免插入过程移动元素的开销,所以这种方法总时间复杂度仍然是O(N^2)。

就当复习一下二分吧

参考[1]二分法排序的原理

算法思想简单描述: 在插入第i个元素时,对前面的0~i-1元素进行折半,先跟他们 中间的那个元素比,如果小,则对前半再进行折半,否则对后半 进行折半,直到left>right,然后再把第i个元素前1位与目标位置之间 的所有元素后移,再把第i个元素放在目标位置上。

具体代码如下:

#include<iostream>
#include <stdio.h>
#include<vector>
using  namespace std;
//函数模版,打印vector中的内容
template <typename T>
void printVector(const vector<T>&v)
{
    if(v.empty())   cout<<endl<<"your vector is empty"<<endl;
    cout<<endl;
    for(int i=0;i<v.size();i++)
    {
        cout<<v[i]<<" ";
    }
    cout<<endl;
}
//1. 直接插入排序
vector<int> insertSort(vector<int> v)
{
    if(v.empty()) return v;
    int t=0;
    int n=v.size()-1;
    for(int i=1;i<=n;i++)
    {
        if(v[i]<v[i-1])
        {
            int t=v[i];
            int j=i-1;
            for(;j>=0 && v[j]>t;j--)    v[j+1]=v[j];
            //j位置不满足条件时,循环跳出。所以t应该插入到j+1处。
            v[j+1]=t;
        }
    }
    return v;
}
//2. 二分法
vector<int> binarySort(vector<int> v)
{
    if(v.empty()) return v;
    int n=v.size()-1;

    for(int i=1;i<=n;i++)
    {
        if(v[i]<v[i-1])
        {
            int t=v[i];
            int left=0;
            int right=i-1;
            int mid=0;
            while(left>=0 && left<=right)
            {
                mid=(left+right)/2;
                //如果有2个以上的相同值,不能保证稳定排序
                if (v[mid]==t){ mid+=1; break;}
                else if(v[mid]<t) {left=mid+1;}
                else {right=mid-1;}
            }
            //mid处就是要插入的位置
            int j=i-1;
            for(;j>=mid;j--) v[j+1]=v[j];
            v[mid]=t; //v[j+1]=t;
        }
    }
    return v;
}

//测试
int main()
{
    int a[]={2,1,6,4,5};
    //int a[]={2,4,6,8,5};
    printVector(binarySort(vector<int>(a,a+5)));
}

References

© 著作权归作者所有

realsa

realsa

粉丝 33
博文 84
码字总数 107087
作品 0
广州
程序员
私信 提问
【数据结构与算法JavaScript实现与应用】查找算法 —— 顺序查找 PK 二分法+排序

前言 在列表中查找数据有两种方式:顺序查找和二分查找。对于一个已排序的列表,二分法无疑效率更高,因为每次可排除一半的元素,但若是对于一个无序的列表,如果先对其排序,再用二分法查找...

haoshuai1950
07/20
0
0
Java 9种排序算法详解和示例汇总

冒泡排序、选择排序、直接插入排序、二分法排序、希尔排序、快速排序、堆排序、归并排序、基数排序,共9中排序算法详解和代码示例。 示例中全部采用从小到大排序,编码方式为本人理解的思路,...

磊_lei
2018/06/02
0
0
常用基础排序算法

首先初始化了一个MAX大小的数组,用乱序函数将数组打乱,用于测试各个排序函数,先附上要测试的几个基础排序函数,后面附上乱序函数和主调度函数。代码就那么几行,只是注释的思乱占了比较多...

穿靴子的猫LJL
2015/10/13
22
0
算法之排序(Java版)-持续更新补充

开始复习排序,主要是按照《轻松学算法》这本书的目录来学习,同时搜索网上的博客文章来辅助,参考的来源均在文章底部标明。同样,本文持续更新,代码书上只给了基础排序代码(我称之为原始排...

kissjz
2018/08/03
0
0
**超详细的**10种排序算法原理及 JS 实现

简介 本文介绍了常见的 10 种排序算法的原理、基本实现和常见的优化实现,并有(个人认为)足够详细的代码注释。 实在是居家工作,面试笔试必备良药。 这里只给出基于其原理的一般实现,很多...

迪斯马斯克
04/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

centos7 linuxdeployqt qt5.13.1 打包程序

原文链接:https://www.cnblogs.com/linuxAndMcu/p/11016322.html 一、简介 linuxdeployqt 是Linux下的qt打包工具,可以将应用程序使用的资源(如库,图形和插件)复制到二进制运行文件所在的...

shzwork
27分钟前
4
0
IDEA 配置Springboot项目热部署

实现的方式概述 注意以下的热部署方式在IDEA是默认没有打开自动编译的,手动编译需要快捷键(Ctrl+Shift+F9),自动编译的修改配置如下:(注意刷新不要太快,会有1-2秒延迟) File-Settings-C...

小强的进阶之路
38分钟前
9
0
免费数据分析工具:secsoso

前段时间思考了理想数据分析平台,之后我们根据这个思路开发了spl语言并提供了一个数据分析平台,这个平台主要用在搜索ES,数据库索引中的数据。但后来发现对文件的事后处理也是个非常重要的...

赛克蓝德
40分钟前
5
0
暗黑2不能正常启动?带你轻松使用WIN10运行游戏

暗黑破坏神2这款游戏由于年代比较久远,所以设置启动这方面与现在的大部分游戏有很大差距,由于当初完美运行暗黑2是当年使用最多的XP系统,在使用现在大多数玩家使用的WIN7到WIN10系统常会出...

太空堡垒185
44分钟前
6
0
maven项目对象模型(二)

1.4.4.传递性依赖 一个传递性依赖就是一个依赖的依赖。如果project-a依赖于project-b,而后者接着依赖于project-c,那么project-c就是被认为是project-a的传递性依赖。如果project-c依赖于p...

万建宁
44分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部