插入排序

简介: 插入排序

Insertion Sort

对于近乎有序的数组,插入排序的时间复杂度优于O(nlogn)

对于完全有序数组,插入排序时间复杂度会降到O(n)

将待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列,将扫描到的每个元素插入前面有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面)

和打扑克牌类似,手中的都是排好序的,抽到一张牌后,会插入到已排好序的牌中合适位置

从第二个元素开始,往前比较

算法步骤

template<typenameT>

voidinsertionSort(Tarr[],intn){

 //从第二个元素开始插入排序,直到末尾

   for(inti=1;i<n;i++){

       //从后往前比较,如果大于前面元素,说明是在合适位置,跳出当前循环

       for(intj=i;j>0;j--){

           if(arr[j]<arr[j-1])

               swap(arr[j],arr[j-1]);

           else

               break;

       }

   }

}

上述代码虽然可以提前终止内层循环,但是时间性能测试是没有选择排序快的

intmain(){

   intn=10000;

   //生成乱序数组

   int*arr=SortTestHelper::generateRandomArray(n,0,n);

   int*arr2=SortTestHelper::copyIntArray(arr,n);//复制arr得到arr2

   //测试耗时

   SortTestHelper::testSort("selectionSort",selectionSort,arr2,n);

   SortTestHelper::testSort("insertionSort",insertionSort,arr,n);

   //释放空间

   delete[] arr;

   delete[] arr2;

   return0;

}

/*

selectionSort : 0.16 s

insertionSort : 1.484 s

*/

优化

因为swap函数进行了三次赋值,赋值是比比较操作更加耗时的,可以减少赋值从而进行改进

先将要插入的元素存储起来,再将要插入的元素依次与前面的元素进行比较,小于前面元素的话,就将前面元素赋值到当前位置,直到要插入的元素大于等于前面元素。可以看到通过一次赋值替换了交换操作(三次赋值)

template<typenameT>

voidinsertionSortPlus(Tarr[],intn){

   //第一个元素显然有序,因此我们从第二个元素开始排序,若间隔为gap,则从下标为gap开始

   for(inti=1;i<n;i++){

       //记录要进行排序的元素

       Te=arr[i];

       //j是要插入的位置

       intj;

       for(j=i;j-1>=0;j=j-1){

           if(e<arr[j-1])

               arr[j]=arr[j-1];

<<<<<<<HEAD

           elsebreak;//明显当e>=arr[j-1]时跳出循环,说明arr[j]正是元素要插入的位置,而之前arr[j]已经后移一位

=======

           elsebreak;//明显当e>arr[j-1]时跳出循环,说明arr[j]正是元素要插入的位置,而之前arr[j]已经后移一位

>>>>>>>27c092bbe831973f875c92f374e0f8ec3ae3e3b4

       }

       arr[j]=e;

   }

}

selectionSort : 0.158 s

insertionSort : 0.113 s

当数据是近乎有序的,插入排序的时间复杂度甚至优于O(nlogn)

   // 生成一个近乎有序的数组,n是数组元素个数,swapTimes是指交换次数,因为数组要保持近乎有序

   int*generateNearlyOrderedArray(intn,intswapTimes){

       int*arr=newint[n];

       for(inti=0;i<n;i++)

           arr[i]=i;

       srand(time(0));

       for(inti=0;i<swapTimes;i++){

           intposx=rand()%n;

           intposy=rand()%n;

           swap(arr[posx],arr[posy]);

       }

       returnarr;

   }

intmain(){

   intn=10000;

   //生成近乎有序数组

   int*arr=SortTestHelper::generateNearlyOrderedArray(n,100);

   int*arr2=SortTestHelper::copyIntArray(arr,n);

   //测试耗时

   SortTestHelper::testSort("selectionSort",selectionSort,arr2,n);

   SortTestHelper::testSort("insertionSort",insertionSort,arr,n);

   //释放空间

   delete[] arr;

   delete[] arr2;

   return0;

}

selectionSort : 0.155 s

insertionSort : 0.003 s

目录
相关文章
|
存储 算法 调度
深入理解操作系统的内存管理
本文旨在探讨操作系统中至关重要的一个组成部分——内存管理。我们将从内存管理的基本原理出发,逐步深入到高级话题,如分页、分段以及虚拟内存技术。文章将详细解析内存分配策略、内存保护机制以及内存映射等关键技术,并讨论现代操作系统如何处理诸如内存碎片和并发控制等问题。通过本文,读者将获得对操作系统内存管理深层次工作原理的理解,为进一步研究或解决实际问题打下坚实的基础。
|
10月前
|
Linux
在 Linux 系统中,“cd”命令用于切换当前工作目录
在 Linux 系统中,“cd”命令用于切换当前工作目录。本文详细介绍了“cd”命令的基本用法和常见技巧,包括使用“.”、“..”、“~”、绝对路径和相对路径,以及快速切换到上一次工作目录等。此外,还探讨了高级技巧,如使用通配符、结合其他命令、在脚本中使用,以及实际应用案例,帮助读者提高工作效率。
689 3
|
9月前
|
消息中间件 网络协议 RocketMQ
RocketMQ Controller 模式 始终更新成本机ip
ontrollerAddr=192.168.24.241:8878 但是日志输出Update controller leader address to 127.0.0.1:8878。导致访问失败
163 3
|
消息中间件 弹性计算 运维
阿里云云消息队列RabbitMQ实践解决方案评测报告
阿里云云消息队列RabbitMQ实践解决方案评测报告
203 9
|
消息中间件 Java Kafka
将CSV的数据发送到kafka(java版)
java版,读取CSV数据发送到kafka
197 1
将CSV的数据发送到kafka(java版)
|
网络协议 算法 网络架构
PPP协议
PPP协议
869 1
PPP协议
|
运维 安全 Java
SpringBoot实战(十四):Spring Boot Admin 集成安全模块
SpringBoot实战(十四):Spring Boot Admin 集成安全模块
446 0
|
Java 应用服务中间件 Android开发
Tomcat 设置使用指定的jdk
我们都知道,tomcat启动前需要配置JDK环境变量,如果没有配置JDK的环境变量,那么tomcat启动的时候就会报错,也就是无法启动。但是在我们的工作或者学习过程中,有的时候会出现tomcat需要使用不同的JDK版本。
1027 0
|
编译器 Linux 测试技术
SDL开发笔记(一):SDL介绍、编译使用以及工程模板
SDL开发笔记(一):SDL介绍、编译使用以及工程模板
SDL开发笔记(一):SDL介绍、编译使用以及工程模板