Java數(shù)組排序——插入排序（Insertion Sort）思路及實(shí)現(xiàn)

1、概念及其介紹：

? 插入排序（InsertionSort）,一般也被稱為直接插入排序。對(duì)于少量元素的排序，他是一個(gè)有效的算法。

2、思路：

? 它的基本思路是將一個(gè)記錄插入到已經(jīng)排序好的有序表中，從而得到一個(gè)新的、記錄增加1的有序表。在實(shí)現(xiàn)過程中使用雙層循環(huán)，外層循環(huán)對(duì)除了第一個(gè)元素之外的所有元素，內(nèi)層循環(huán)對(duì)當(dāng)前元素前面有序表進(jìn)行待插入位置查找，進(jìn)行移動(dòng)。

3、適用說明：

? 插入排序的平均時(shí)間復(fù)雜度是O(n^2)，空間復(fù)雜度為常數(shù)階O(1)，具體時(shí)間復(fù)雜度和數(shù)組的有序性也是有關(guān)聯(lián)的。
插入排序中，當(dāng)待排序數(shù)組是有序時(shí)，是最優(yōu)的情況，只需當(dāng)前跟前一個(gè)數(shù)比較一下就可以了，這是一共需要比較n-1次，時(shí)間復(fù)雜度為O(n)。最壞的情況是待排序數(shù)組是逆序的，此時(shí)需要比次數(shù)最多，最壞的情況是O(n^2)。

4、過程圖示：

? 假設(shè)前面n-1(其中n>=2)個(gè)數(shù)是已經(jīng)排好順序的，現(xiàn)將第n個(gè)數(shù)插到前面已經(jīng)排好的序列中，然后找到合適自己的位置，使得插入的第n個(gè)數(shù)的新序列也是排好順序的。排序的過程如圖所示：

以數(shù)組int[] numbers = ｛5,3,2,6,4｝; 為例：

**第一輪：**將第2個(gè)元素3作為臨時(shí)元素，也就是待插入元素，將臨時(shí)元素3與前一個(gè)元素5做比較，如果臨時(shí)元素3小于前一個(gè)元素5，則前一個(gè)元素5向后移動(dòng)一位，臨時(shí)元素3插入此前5的位置。

**第二輪：**將第3個(gè)元素2作為臨時(shí)元素，先將2與5做比較，2小于5，將5向后移動(dòng)一位，再將2與3做比較，2小于3，將3向后移動(dòng)一位，最后將2插入到3之前的位置。

**第三輪：**將第四個(gè)元素6作為臨時(shí)元素，將6與5做比較，6大于5，將6插入到當(dāng)前自己所在的位置。

**第四輪：**將第五個(gè)元素4作為臨時(shí)元素，將4與6做比較，4小于6，將6向后移動(dòng)一位，在將4與5做比較，4小于5，將5向后移動(dòng)一位，再將4與3做比較，4大于3，將4插入3后面的位置。完成排序。

5、代碼實(shí)現(xiàn)：

/*** @Author: LiuHao* @Date: 2021/10/19 20:23* 插入排序2*/ public class InsertSort2 {public static void main(String[] args) {int[] numbers = {5,3,2,6,4};System.out.println("排序前的結(jié)果為：" + Arrays.toString(numbers));for (int i = 1; i < numbers.length; i++) { //控制循環(huán)輪數(shù)int temp = numbers[i]; //定義待交換元素int j; //定義待插入的位置for (j = i; j > 0 && temp < numbers[j - 1]; j --) {numbers[j] = numbers[j - 1];}numbers[j] = temp;System.out.println("第" + i + "輪的排序結(jié)果為：" + Arrays.toString(numbers));}System.out.println("排序后的結(jié)果為：" + Arrays.toString(numbers));} }

6、運(yùn)行結(jié)果：

排序前的結(jié)果為：[5, 3, 2, 6, 4]
第1輪的排序結(jié)果為：[3, 5, 2, 6, 4]
第2輪的排序結(jié)果為：[2, 3, 5, 6, 4]
第3輪的排序結(jié)果為：[2, 3, 5, 6, 4]
第4輪的排序結(jié)果為：[2, 3, 4, 5, 6]
排序后的結(jié)果為：[2, 3, 4, 5, 6]

總結(jié)

以上是生活随笔為你收集整理的Java插入排序（思路及实现）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。