基礎排序算法-------插入排序

---

實現過程：

插入排序的過程就像整理橋牌的過程；每次將待排元素中的第一個元素插入到有序區間的合適位置，為了給當前待排元素騰出位置，需要將有序區間內所有大于待排元素的其他元素都向右移動一位；
與選擇排序一樣，待排元素左邊區間的元素是有序的，但是它們的位置并不確定，因為可能會被移動，當待排索引到達數組右端時，整個數組就有序了。

特點：

與選擇排序不同，插入排序所需要的時間取決于輸入時元素的順序；若初始數據越接近有序，則排序速度就越快，所以插入排序經常用于高階排序算法的優化手段之一。

時間復雜度：最好的情況下為O(N),其他情況下為O(N^2)

空間復雜度：O(1)

穩定性：穩定

---

1.基礎插入排序

將無序區間的第一個元素作為待排元素，不斷與前一元素交換位置而到達合適位置。

代碼實現：

public static void insertionShort(int[] arr) {//[0,i]為有序區間//[j,arr.length)為無序區間//j指向當前待排的那個元素for (int i = 0; i < arr.length - 1; i++) {for (int j = i + 1; j > 0; j--) {//待排元素與前一元素比較大小if (arr[j] < arr[j - 1]) {//待排元素與前一元素交換位置swap(arr, j, j - 1);}else {//說明待排元素前一元素小于等于待排元素，已到達合適位置break;}}}}

2.優化后的插入排序

上面的基礎插入排序，不斷將待排元素與前一元素交換位置而到達目標位置，交換過程會不斷訪問數組，會增加排序時間；如果確認位置后，先記錄待排元素值，通過右移其他元素，為目標元素騰出位置，最后直接將待排元素值補位到目標位置，這樣可以節省不少時間。

代碼實現：

public static void insertionShort2(int[] arr) {//[0,i]為有序區間//[j,arr.length)為無序區間//j指向當前待排的那個元素for (int i = 0; i < arr.length - 1; i++) {int j = i + 1;//記錄當前待排元素值int temp = arr[j];for (; j > 0 && temp < arr[j - 1]; j--) {//將大于待排元素的其他元素右移一位arr[j] = arr[j - 1];}//此時j指向位置即為待排元素的合適位置arr[j] = temp;}}

3.再次優化--------折半插入排序

利用二分查找法來確定待插入元素在有序區間里的位置；確認位置后，通過右移其他元素，為目標元素騰出位置，最后直接補位。

代碼實現：

public static void insertionShortHalf(int[] arr) {int len = arr.length;//[0,i]為有序區間//[i+1,len)為無序區間for (int i = 0; i < len - 1; i++) {//left指向有序區間第一個元素int left = 0;//right指向無序區間第一個元素，即待插元素int right = i + 1;//待插元素值int value = arr[right];//出了循環，left所指就是待插位置while (left < right) {int mid = left + ((right - left) >> 1);if (arr[mid] > value) {right = mid;}else{left = mid + 1;}}//[left,i]區間所有元素向右搬移一位for (int j = i + 1; j > left; j--) {arr[j] = arr[j - 1];}//待排元素歸位arr[left] = value;}}

不同情況下以上三種插入排序執行時間對比

a.處理長度為10萬且近乎有序數組時，三種插入排序方式時間效率差別不大，都很優秀。

b.處理長度為10萬且數據隨機不重復數組時，折半插入排序速度最快，基礎插入排序速度最慢。

---

總結

以上是生活随笔為你收集整理的【Java】基础排序算法-插入排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。