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中如何實作插入排序演算法？的詳細內容。更多資訊請關注PHP中文網其他相關文章！