一、插入排序的實(shí)現(xiàn)

1.什么是插入排序呢

插入排序的工作方式像許多人排序一手撲克牌。開始時(shí)，我們的左手為空并且桌子上的牌面向下。然后，我們每次從桌子上拿走一張牌并將它插入左手中正確的位置。為了找到一張牌的正確位置，我們從右到左將它與已在手中的每張牌進(jìn)行比較。拿在左手上的牌總是排序好的，原來這些牌是桌子上牌堆中頂部的牌

2.具體步驟

第一輪：從第二位置的 6 開始比較，比前面 7 小，交換位置。

第二輪：第三位置的 9 比前一位置的 7 大，無需交換位置。

第三輪：第四位置的 3 比前一位置的 9 小交換位置，依次往前比較。

第四輪：第五位置的 1 比前一位置的 9 小，交換位置，再依次往前比較。

…

就這樣依次比較到最后一個(gè)元素。

3.使用循環(huán)不變式證明算法的正確性

循環(huán)不變式的概念：
簡單了說就是每次循環(huán)都有某種性質(zhì)，且該性質(zhì)一直保持不變，直到循環(huán)結(jié)束。

循環(huán)不變式的三個(gè)性質(zhì)：

1.初始化：循環(huán)的第一次迭代之前，它為真。
2.保持：如果循環(huán)的某次迭代之前它為真，那么下次迭代之前它仍為真。
3.終止：在循環(huán)終止時(shí)，不變式為我們提供一個(gè)有用的性質(zhì)，該性質(zhì)有助于證明算法時(shí)正確的。

對于插入排序，如何證明這三個(gè)性質(zhì)

初始化：插入排序初始只有1個(gè)元素arr[0]，所以該子數(shù)組是有序的
保持：每次插入元素到子數(shù)組中，該子數(shù)組一直保持有序性
終止：循環(huán)的終止條件是遍歷到了最后一個(gè)將要插入的元素，此時(shí)插入過后，子數(shù)組已經(jīng)擁有了原數(shù)組的所有數(shù)據(jù)，且保持有序

因此算法正確。

4.插入排序代碼實(shí)現(xiàn)

import java.util.Arrays;/*** @author:抱著魚睡覺的喵喵* @date:2021/2/23* @description: 插入排序*/ public class InsertSort {public static void main(String[] args) {int arr[] = {9,1,4,2,8};InsertSort(arr);System.out.println(Arrays.toString(arr));}public static void InsertSort(int[] arr) {for (int i = 1; i < arr.length; i++) {int insertVal = arr[i];int insertIndex =i - 1;while (insertIndex >= 0 && insertVal < arr[insertIndex]) {arr[insertIndex + 1] = arr[insertIndex];insertIndex--;}arr[insertIndex + 1] = insertVal;}} }

5.插入排序算法的分析

1.時(shí)間復(fù)雜度：最壞的情況就是原數(shù)組的數(shù)據(jù)是降序排列，最好的情況當(dāng)然就是已經(jīng)有序(升序）
最壞的情況：O(n^2)
最好的情況：O(n)
所以平均時(shí)間復(fù)雜度位O(n^2)

2.空間復(fù)雜度：O(1)

3.插入排序是穩(wěn)定的；適用場景：數(shù)據(jù)規(guī)模較小

---

二、插入排序的優(yōu)化

于插入排序，如果比較操作的代價(jià)比交換操作大的話，可以采用二分查找法來減少比較操作的次數(shù)。

1.二分查找算法概述(折半查找法）：

二分查找的基本思想是將n個(gè)元素分成大致相等的兩部分，取a[n/2]與x做比較，如果x=a[n/2],則找到x,算法中止；如果x<a[n/2],則只要在數(shù)組a的左半部分繼續(xù)搜索x,如果x>a[n/2],則只要在數(shù)組a的右半部搜索x.

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

import java.util.Arrays;/*** @author:抱著魚睡覺的喵喵* @date:2021/3/4* @description: 使用二分法優(yōu)化直接插入*/ public class DichotomizeInsertSort {public static void main(String[] args) {int arr[] = {2, 5, 8, -11, 6,-19, 7, 8};InsertSort(arr);System.out.println(Arrays.toString(arr));}public static void InsertSort(int arr[]) {int insertValue,mid = 0;int i,j,insertIndex;for (int k = 1; k < arr.length; k++) {i = 0;insertIndex = k;j = k - 1;insertValue = arr[k];while (i <= j) {mid = (i + j) / 2;if (arr[mid] < insertValue) {i = mid + 1;} else {j = mid - 1;}}for (int s = insertIndex - 1; s >= i; s--) {arr[s + 1] = arr[s];}arr[i] = insertValue;}}}

3.復(fù)雜度分析
時(shí)間復(fù)雜度：O(n^2)

二分插入排序只是減少了比較的次數(shù)，而數(shù)據(jù)的移動次數(shù)還是不變的；
本質(zhì)上來說：直接插入排序和二分插入排序性能上差不了多少

總結(jié)

以上是生活随笔為你收集整理的十大经典排序算法之插入排序及其二分优化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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