快捷導(dǎo)航

JAVA十大排序算法之插入排序詳解

更新時間：2021年08月23日 09:45:25 作者：阿粵Ayue

這篇文章主要介紹了java中的插入排序，本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下

插入排序

當我們在玩撲克牌的時候，總是在牌堆里面抽取最頂部的一張然后按順序在手中排列。

插入排序是指在待排序的元素中，假設(shè)前面n-1(其中n>=2)個數(shù)已經(jīng)是排好順序的，現(xiàn)將第n個數(shù)插到前面已經(jīng)排好的序列中，然后找到合適自己的位置，使得插入第n個數(shù)的這個序列也是排好順序的。

1.對于未排序數(shù)據(jù)（一般取數(shù)組的二個元素，把第一個元素當做有序數(shù)組），在已排序序列中從左往右掃描，找到相應(yīng)位置并插入。

2.為了給要插入的元素騰出空間，需要將插入位置之后的已排序元素在都向后移動一位。

代碼實現(xiàn)

對下面數(shù)組實現(xiàn)排序：{15, 51, 86, 70, 6, 42, 26, 61, 45, 81, 17, 1}

動圖演示

插入排序

代碼實現(xiàn)

public class InsertionSort {
    public static final int[] ARRAY = {15, 51, 86, 70, 6, 42, 26, 61, 45, 81, 17, 1};
    public static int[] sort(int[] array) {
        if (array.length == 0) {
            return array;
        }
        //待排序數(shù)據(jù)，改數(shù)據(jù)之前的已被排序
        int current;
        for (int i = 0; i < array.length - 1; i++) {
            //已被排序數(shù)據(jù)的索引
            int index = i;
            current = array[index + 1];
            //將當前元素后移一位
            while (index >= 0 && current < array[index]) {
                array[index + 1] = array[index];
                index--;
            }
            //插入
            array[index + 1] = current;
        }
        return array;
    }

    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + "  ");
        }
        System.out.println("");
    }
    public static void main(String[] args) {
        print(ARRAY);
        System.out.println("============================================");
        print(sort(ARRAY));
    }
}