建设网站对公司起什么作用是什么,织梦仿asp网站,vi设计公司专业品牌,flash网站系统最近在和小伙伴们一起研究排序#xff0c;排序分好多总#xff0c;后期会做整体总结#xff0c;本篇则主要对插入排序进行一个整理。 插入排序#xff08;insert sorting#xff09;的算法思想十分简单#xff0c;就是对待排序的记录逐个进行处理#xff0c;每个新纪录… 最近在和小伙伴们一起研究排序排序分好多总后期会做整体总结本篇则主要对插入排序进行一个整理。 插入排序insert sorting的算法思想十分简单就是对待排序的记录逐个进行处理每个新纪录与同组那些已排好序的记录进行比较然后插入到适当的位置。用三个字总结就是—-“多对一”的关系。 插入排序分好几种比如二分插入排序交换插入排序直接插入排序本篇我们重点总结最熟悉的“直接插入排序”。 比如有一个数组【45 34 78 12 34’ 32 29 64】,我们针对此进行一下讲解。 排序过程 数组{45 34 78 12 34’ 32 29 64}第一遍 45和34比较3445,所以排序完成为34 45 78 12 34’ 32 29 64第二遍 78和34 45比较 7845 7834,所以位置不变排序完为 34 45 78 12 34’ 32 29 64第三遍 12和34 45 78比较 1278 左移11245 左移21234 左移3排序完为 12 34 45 78 34’ 32 29 64第四遍 34’ 左移2 排序完 12 34 34’ 45 78 32 29 64第五遍 32 左移4 排序完 12 32 34 34’ 45 78 29 64第六遍 29 左移6 排序完 12 29 32 34 34’ 45 78 64第七遍 64 左移1 排序完 12 29 32 34 34’ 45 64 78用代码实现的话其实更简单引入一个临时变量具体看代码 public static void main(String[] args) {Test2 test2 new Test2();//定义一个数组int[] array {45, 34, 78, 12, 34, 32 ,29 ,64};test2.insertSort(array);System.out.println(Arrays.toString(array));}void insertSort(int[] array) {//定义的临时变量int tempRecord;//i从1开始的原因是jj-1for (int i 1; i array.length; i) {tempRecord array[i];int j i - 1;//j不能为负数根据索引判定值大小通过临时变量进行交换while (j 0 tempRecord array[j]) {array[j 1] array[j];j j - 1;}array[j 1] tempRecord;}} 2018年07月30日14:30:55补充
array[j 1] tempRecord应该放入while循环内因为若tempRecore不小于array[j]则此次i循环则直接结束。 通过代码我们来看一下时间复杂度和空间复杂度。 因为我们只引入了一个辅助存放插入记录的临时变量因此空间代价为一个记录大小 及O1 当数据正序时如上我们口述的排序比较过程执行效率最好每次插入都不用移动前面的元素有N个元素参与比较时间复杂度为O(N)。 当数据反序时则执行效率最差每次插入都要前面的元素后移 i1时移动2-1 i2时移动3-1 当in时移动n-1; 求和公式n(n-1)/2O(n2) 所以最坏的时间复杂度为O(N2) 转载于:https://www.cnblogs.com/huohuoL/p/10545426.html
