学习视频分享:java视频教程
普通插入:从数组的第二个元素进行操作,当发现其前面的元素比他大时,执行交换操作。
static int[] insertSort(int[] array){ int len = array.length; for (int begin = 1; begin 0 && array[cur] <p><strong>第一步优化:从数组的第二个元素进行操作,如果发现其前面的元素比他大,就将其前面的元素往后挪,直到cur指向的元素大于或者等于他前一个元素,此时cur指向的位置就是待插入元素应该插入的位置。</strong><br></p><pre class="brush:php;toolbar:false"> static int[] insertSort2(int[] array){ int len = array.length; for (int begin = 1; begin 0 && array[cur] <p><strong>第二步优化</strong><br></p><p><strong>第三种算法和第二种其实本质上是一样的,都是找待插入位置,挪动元素,只不过第三种算法通过二分查找减少了比较次数,即cmp函数的调用,还减少了swap函数的调用。更快的找到了当前元素应该插入的位置,然后再进行挪动,提高了效率。</strong></p><pre class="brush:php;toolbar:false">static int[] insertSort3(int[] array){ int len = array.length; for (int begin = 1; begin insertIndex; i--){ array[i] = array[i-1]; } array[insertIndex] = v; } return array; } static int search(int[] array, int index){ int begin = 0; int end = index; while(begin > 1; if (array[index] <p><strong>需要注意的是:使用了二分搜索后,只是减少了比较次数,但插入排序的平均时间复杂度依然是O(n^2)</strong><br></p><p><strong>将其中的挪动操作分离出来的效果:</strong></p><pre class="brush:php;toolbar:false"> package com.mj.sort.cmp;import com.mj.sort.Sort;public class InsertionSort3<t>> extends Sort<t> { // protected void sort() {// for (int begin = 1; begin = insertIndex; i--) { }// for (int i = begin; i > insertIndex; i--) {// array[i] = array[i - 1];// }// array[insertIndex] = v;// }// } @Override protected void sort() { for (int begin = 1; begin dest; i--) { array[i] = array[i - 1]; } array[dest] = v; } /** * 利用二分搜索找到 index 位置元素的待插入位置 * 已经排好序数组的区间范围是 [0, index) * @param index * @return */ private int search(int index) { int begin = 0; int end = index; while (begin > 1; if (cmp(array[index], array[mid]) <p>相关推荐:<a href="https://www.php.cn/java/guide/" target="_blank">java入门教程</a></p></t></t>
以上就是java实现插入排序后怎么进一步优化的详细内容,更多请关注php中文网其它相关文章!
Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号