Java中插入排序算法怎么實現

這篇“Java中插入排序算法怎么實現”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內容，內容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“Java中插入排序算法怎么實現”文章吧。

一、基本思想

插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。

二、算法分析

1、算法描述

一般來說，插入排序都采用in-place在數組上實現。具體算法描述如下：

• 從第一個元素開始，該元素可以認為已經被排序；

• 取出下一個元素，在已經排序的元素序列中從后向前掃描；

• 如果該元素（已排序）大于新元素，將該元素移到下一位置；

• 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置；

• 將新元素插入到該位置后；

• 重復步驟2~5。

2、過程分析

（1）、將第一個元素 (1) 標記為已經排序過。

（2）、提取第一個沒有排序過的元素 (28)。

（3）、找出插入提取元素的地方；和已經排序過的元素 1 比較。

（4）、1 > 28 不成立（False）, 在現有位置上插入一個元素。

（5）、找出插入提取元素的地方；和已經排序過的元素 28 比較。

（6）、28 > 3 成立（True）, 則將現在已經排序過的元素({val1}) 向右移動1格。

（7）、找出插入提取元素的地方；和已經排序過的元素 1 比較。

（8）、1 > 3 不成立（False）, 在現有位置上插入一個元素。

（9）、以此類推

三、算法實現

package com.algorithm.tenSortingAlgorithm;

import java.util.Arrays;

public class InsertionSort {
    private static void insertionSort(int[] arr) {
        int preIndex, current;
        for (int i = 1; i < arr.length; i++) {
            preIndex = i - 1;
            current = arr[i];
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex + 1] = current;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,28,3,21,11,7,6,18};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

以上就是關于“Java中插入排序算法怎么實現”這篇文章的內容，相信大家都有了一定的了解，希望小編分享的內容對大家有幫助，若想了解更多相關的知識內容，請關注億速云行業資訊頻道。