技术文章 > java >  java数组 > 正文

java数组如何插入元素并快捷排序?

小妮浅浅

对于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;
 
}

需要注意的是:使用了二分搜索后,只是减少了比较次数,但插入排序的平均时间复杂度依然是O(n^2)。

以上就是java数组插入元素并快捷排序的方法,大家在对基本的数组操作有所了解后,可以就本篇的综合性使用展开练习。更多Java学习指路:java数组

免费视频教程
本教程部分素材来源于网络,版权问题联系站长!
相关文章
  java数组的概念理解
  java数组初始化方式
  java数组遍历的方法
  java数组内存的探究
  java数组转换成list的注意点
  java数组进行翻转的方法有哪些
  java数组中删除元素的操作
  java数组中有哪些面试题
  java数组中length的使用
  java数组中如何查找元素的位置?
相关视频章节
  什么是tkinter窗口
  例子3 登录窗口
  例子2 登录窗口
  例子1 登录窗口
  pack grid place 放置位置
作者信息

小妮浅浅

认证0级讲师

最近文章
python在协程中增加任务 455
python pyg2plot的原理 353
python中pyg2plot如何使用? 160
推荐视频
视频教程分类