插入排序

简介:

基本思想

把n个元素的数列分成有序(前)和无序(后)的两部分

{{a1},{a2,a3,a4,…,an}}
{{a1⑴,a2⑴},{a3⑴,a4⑴ …,an⑴}}
…
{{a1(n-1),a2(n-1) ,…},{an(n-1)}}

每次处理就是将无序的数列中第一个元素与有序数列的元素从后到前比较,找到插入位置,将该元素插入到有序数列的适当的最终的位置上(稳定排序)。

参考代码一

复制代码
#include <iostream>
#include <cstdlib>
using namespace std;

void insertSort(int array[], int size)
{
    for(int i = 1; i < size; ++i)
    {
        for(int j = i; j > 0 && array[j-1] > array[j]; --j)
        {
            int tmp = array[j];
            array[j] = array[j-1];
            array[j-1] = tmp;
        }
    }
}

int main()
{
    int a[] = {1, 3, 5, 7, 8};
    size_t size = sizeof(a) / sizeof(int);
    insertSort(a, size);
    for(int i = 0; i < size; ++i)
        cout << a[i] << " ";
    cout << endl;
}
复制代码

连续交换的时候相当于整体后移,把做比较元素放到最终位置上,修改如下。

参考代码二

复制代码
#include <iostream>
#include <cstdlib>
using namespace std;

void insertSort(int array[], int size)
{
    for(int i = 1; i < size; ++i)
    {
        int tmp = array[i];
        int j;
        for(j = i; j > 0 && array[j-1] > array[j]; --j)
            array[j] = array[j-1];
        array[j] = tmp;
    }
}

int main(int argc, char **argv)
{
    int a[] = {1, 3, 5, 7, 8};
    size_t size = sizeof(a) / sizeof(int);
    insertSort(a, size);
    for(int i = 0; i < size; ++i)
        cout << a[i] << " ";
    cout << endl;
}
复制代码

运行结果

1 3 5 7 8

 

分析

空间:仅需要一个辅助空间,为O(1)

时间:对数列进行升序排列,最好情况——已经是升序了,比较次数为(n-1)次;最坏情况——已经是降序了,比较次数为(n-1)*n/2,赋值操作为(n-1)*n/2 + (n-1)。

平均来说插入排序算法复杂度为O(n2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用,在STL的sort算法和stdlib的qsort算法中,都将插入排序作为快速排序的补充,用于少量元素的排序(通常为8个或以下)。

 




本文转自jihite博客园博客,原文链接:http://www.cnblogs.com/kaituorensheng/p/3553344.html,如需转载请自行联系原作者

相关文章
|
安全 Linux 网络安全
/var/log/secure日志详解
Linux系统的 `/var/log/secure` 文件记录安全相关消息,包括身份验证和授权尝试。它涵盖用户登录(成功或失败)、`sudo` 使用、账户锁定解锁及其他安全事件和PAM错误。例如,SSH登录成功会显示&quot;Accepted password&quot;,失败则显示&quot;Failed password&quot;。查看此文件可使用 `tail -f /var/log/secure`,但通常只有root用户有权访问。
3448 4
|
Docker 容器
docker如何在容器外执行容器内命令
有时候我们想执行某个容器的某条命令,但又不想进入容器内。那该怎么办? 所以就有一种办法,我们直接在容器外执行容器内的命令,来进行一些容器内的操作。
2764 0
docker如何在容器外执行容器内命令
|
JSON 关系型数据库 MySQL
MySQL中GROUP_CONCAT与JSON_OBJECT、GROUP BY的巧妙结合:打造高效JSON数组汇总
MySQL中GROUP_CONCAT与JSON_OBJECT、GROUP BY的巧妙结合:打造高效JSON数组汇总
446 1
|
NoSQL Go API
简洁、轻量级的 Go API 框架
简洁、轻量级的 Go API 框架
190 0
|
Go 开发者
Golang深入浅出之-Go语言项目构建工具:Makefile与go build
【4月更文挑战第27天】本文探讨了Go语言项目的构建方法,包括`go build`基本命令行工具和更灵活的`Makefile`自动化脚本。`go build`适合简单项目,能直接编译Go源码,但依赖管理可能混乱。通过设置`GOOS`和`GOARCH`可进行跨平台编译。`Makefile`适用于复杂构建流程,能定义多步骤任务,但编写较复杂。在选择构建方式时,应根据项目需求权衡,从`go build`起步,逐渐过渡到Makefile以实现更高效自动化。
349 2
|
JavaScript
一篇文章讲明白js鼠标侧键监听(也有左键,中键和右键)
一篇文章讲明白js鼠标侧键监听(也有左键,中键和右键)
490 0
|
缓存 Rust 前端开发
【一起学Rust | 框架篇 | Tauri2.0框架】Tauri2.0环境搭建与项目创建
【一起学Rust | 框架篇 | Tauri2.0框架】Tauri2.0环境搭建与项目创建
1716 0
|
JSON 中间件 API
|
SQL 存储 运维
阿里云分布式关系型数据库服务 DRDS
DRDS 是阿里巴巴集团自主研发的分布式数据库中间件产品,专注于解决单机关系型数据库扩展性问题,具备轻量(无状态)、灵活、稳定、高效等特性,稳定运行11年,经历历届双十一核心交易业务和各类行业业务的考验
13555 0