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

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

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

插入排序

當(dāng)我們?cè)谕鎿淇伺频臅r(shí)候，總是在牌堆里面抽取最頂部的一張然后按順序在手中排列。

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

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

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

代碼實(shí)現(xiàn)

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

動(dòng)圖演示

插入排序

代碼實(shí)現(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];
            //將當(dāng)前元素后移一位
            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));
    }
}