栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

十大排序算法之六 - 插入排序

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

十大排序算法之六 - 插入排序

十大排序算法之六 - 插入排序 1.插入排序的介绍
  • 插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入
  • 简单的理解,就是分两个队伍,将乱序的元素一个一个拿出来,放在有序的队伍中去,如果正好符合游戏的顺序,直接放好;如果不符合顺序,则插入到符合顺序的位置上去
2.Java实现插入排序并测试 2.1 Java实现插入排序
package com.lagou.insertionSort;


public class InsertionSortMethod {
    // 升序排序
    public int[] insertSort(int[] array){
        int len = array.length;
        int preIndex, current; // 前一个元素索引,当前元素
        for (int i = 1; i < len; i++){
            preIndex = i - 1; // 已经排好序的序列最后一个元素
            current = array[i];
            while (preIndex >= 0 && array[preIndex] > current){
                array[preIndex + 1] = array[preIndex]; // 江大的元素向后移动一格,腾出要存放元素的位置
                preIndex--; // 大于最后一个,需要继续向前寻找位置插入
            }
            // 不满足条件,就是需要插入的位置
            array[preIndex + 1] = current;
        }
        return array;
    }
}
2.2 进行测试
package com.lagou.insertionSort.test;

import com.lagou.insertionSort.InsertionSortMethod;

import java.util.Arrays;


public class InsertionSortMethodTest {
    public static void main(String[] args) {
        InsertionSortMethod insertionSortMethod = new InsertionSortMethod();
        int[] array = {3, 6, 5, 2, 4, 9, 8, 1, 7};
        System.out.println("【插入排序】原数组:" + Arrays.toString(array));
        int[] sort = insertionSortMethod.insertSort(array);
        System.out.println("【插入排序】新的数组:" + Arrays.toString(sort));
    }
}

3.总结

插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/936931.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号