Java經(jīng)典排序算法之插入排序代碼實例

更新時間：2023年10月20日 11:09:04 作者：惡魔青葉

這篇文章主要介紹了Java經(jīng)典排序算法之插入排序代碼實例,插入排序是一種最簡單直觀的排序算法,它的工作原理是通過構(gòu)建有序序列,對于未排序數(shù)據(jù),在已排序序列中從后向前掃描,找到相應位置并插入,需要的朋友可以參考下

1.簡介

插入排序是一種最簡單直觀的排序算法，它的工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應位置并插入。

插入排序的時間復雜度是O(n^2) ，空間復雜度是O（1）。將第一個看成一個有序數(shù)列，將后面的數(shù)跟前面的數(shù)比較，大的就往后移

第一趟排序后：得到一個有序數(shù)列，其大小為2

第二趟排序后：得到一個有序數(shù)列，其大小為3

第三趟排序后：得到一個有序數(shù)列，其大小為4 …

每一趟插入排序，都可以將一個無序值插入一個有序數(shù)列，直至全部值有序

實現(xiàn)思路：

第一步、將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列。
第二步、從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的后面。所以插入排序是穩(wěn)定的排序）

2.圖解流程

在這里插入圖片描述

3.代碼實現(xiàn)

package com.znzz.insertSort;
import java.util.Arrays;
public class InsertSort {
    public static void main(String[] args) {
        inserrtSort(new int[]{6,2,0,2,4,7,9,10});
    }
    public static void inserrtSort(int[] arr) {
        int value;  //待插入元素
        int index;  //待插入元素的前一個元素的索引
        for (int i = 1; i < arr.length; i++) {
            //這里i=1，默認第一個元素是有序的，
            //循環(huán)條件是小于數(shù)組長度
            value = arr[i];
            index = i - 1;   //前一個元素
            while (index >= 0 && value < arr[index]){
                //需要保證index合法
                //每當前面的元素比待插入元素大，就向后移動
                arr[index + 1] = arr[index];
                index--;
        }
        //到這里表示退出循環(huán)，說明找到了待插入的位置，
        arr[index + 1] = value;
    }
        System.out.println(Arrays.toString(arr));
}
}

到此這篇關(guān)于Java經(jīng)典排序算法之插入排序代碼實例的文章就介紹到這了,更多相關(guān)Java插入排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: