«

java数组插入元素并快捷排序的方法是什么

时间:2024-7-8 14:46     作者:韩俊     分类: Java


本篇内容介绍了“java数组插入元素并快捷排序的方法是什么”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

1、从数组的第二个元素进行操作,如果发现其前面的元素比他大,就将其前面的元素往后挪,直到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;
 
}

2、通过二分查找减少了比较次数,即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;
 
}

标签: java

热门推荐