Java怎样实现插入排序,优化操作是什么
导读:这篇文章给大家介绍了“Java怎样实现插入排序,优化操作是什么”的相关知识,讲解详细,步骤过程清晰,对大家进一步学习和理解“Java怎样实现插入排序,优化操作是什么”有一定的帮助,希望大家阅读完这篇文章能有所收获。下面就请大家跟着小编的思路...
这篇文章给大家介绍了“Java怎样实现插入排序,优化操作是什么”的相关知识,讲解详细,步骤过程清晰,对大家进一步学习和理解“Java怎样实现插入排序,优化操作是什么”有一定的帮助,希望大家阅读完这篇文章能有所收获。下面就请大家跟着小编的思路一起来学习一下吧。
普通插入:从数组的第二个元素进行操作,当发现其前面的元素比他大时,执行交换操作。
static int[] insertSort(int[] array){ int len = array.length; for (int begin = 1; begin len; begin++){ int cur = begin; while (cur > 0 & & array[cur] array[cur-1]){ int tmp = array[cur]; array[cur] = array[cur-1]; array[cur-1] = tmp; cur--; } } return array; }
第一步优化:从数组的第二个元素进行操作,如果发现其前面的元素比他大,就将其前面的元素往后挪,直到cur指向的元素大于或者等于他前一个元素,此时cur指向的位置就是待插入元素应该插入的位置。
static int[] insertSort2(int[] array){ int len = array.length; for (int begin = 1; begin len; begin++){ int cur = begin; int tmp = array[cur]; while (cur > 0 & & array[cur] array[cur-1]){ array[cur] = array[cur-1]; cur--; } array[cur] = tmp; } return array; }
第二步优化
第三种算法和第二种其实本质上是一样的,都是找待插入位置,挪动元素,只不过第三种算法通过二分查找减少了比较次数,即cmp函数的调用,还减少了swap函数的调用。更快的找到了当前元素应该插入的位置,然后再进行挪动,提高了效率。
static int[] insertSort3(int[] array){ int len = array.length; for (int begin = 1; begin len; begin++){ int v = array[begin]; int insertIndex = search(array,begin); // 将 [insertIndex, begin) 范围内的元素往右边挪动一个单位 for (int i = begin; i > 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 end){ int mid = (begin+end) > > 1; if (array[index] array[mid]){ end = mid; } else{ begin = mid+1; } } return begin; }
需要注意的是:使用了二分搜索后,只是减少了比较次数,但插入排序的平均时间复杂度依然是O(n^2)
将其中的挪动操作分离出来的效果:
package com.mj.sort.cmp; import com.mj.sort.Sort; public class InsertionSort3T extends ComparableT> > extends SortT> { // protected void sort() { // for (int begin = 1; begin array.length; begin++) { // T v = array[begin]; // int insertIndex = search(begin); // // 将 [insertIndex, begin) 范围内的元素往右边挪动一个单位 for (int i = begin - 1; i > = 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 array.length; begin++) { insert(begin, search(begin)); //元素索引给你,你告诉这个位置的元素往哪插 } } /** * 将source位置的元素插入到dest位置 * @param source * @param dest */ private void insert(int source, int dest) { T v = array[source]; for (int i = source; i > 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 end) { int mid = (begin + end) > > 1; if (cmp(array[index], array[mid]) 0) { end = mid; } else { begin = mid + 1; } } return begin; } }
感谢各位的阅读,以上就是“Java怎样实现插入排序,优化操作是什么”的内容了,通过以上内容的阐述,相信大家对Java怎样实现插入排序,优化操作是什么已经有了进一步的了解,如果想要了解更多相关的内容,欢迎关注网络,网络将为大家推送更多相关知识点的文章。
声明:本文内容由网友自发贡献,本站不承担相应法律责任。对本内容有异议或投诉,请联系2913721942#qq.com核实处理,我们将尽快回复您,谢谢合作!
若转载请注明出处: Java怎样实现插入排序,优化操作是什么
本文地址: https://pptw.com/jishu/654951.html