2019-02-16 03:56:05 mySoul2018

概述

這是一種就地比較排序算法。這裡，維護一個始終排序的子列表。例如，維護數組的下半部分以進行排序。要在此已排序的子列表中“插入”的元素必須找到其適當的位置，然後必須將其插入其中。因此名稱，插入排序。

按順序搜索數組，移動未分類的項並將其插入已排序的子列表（在同一數組中）。該算法不適用於大數據集，因為其平均和最差情況複雜度為0（n 2），其中n是項目數。

插入排序如何工作？

我們以一個未排序的數組為例。

插入排序比較前兩個元素。

它發現14和33都已按升序排列。目前，14位於已排序的子列表中。

插入排序向前移動並將33與27進行比較。

並發現33不在正確的位置。

它將33與27交換。它還檢查已排序子列表的所有元素。在這裡，我們看到排序的子列表只有一個元素14，而27大於14.因此，排序的子列表在交換後仍然排序。

到目前為止，我們在已排序的子列表中有14和27。接下來，它將33與10進行比較。

這些值不是按排序順序排列的。

所以我們互換它們。

但是，交換使27和10未分類。

因此，我們也交換它們。

我們再次以未排序的順序找到14和10。

我們再次交換它們。到第三次迭代結束時，我們有一個包含4個項目的已排序子列表。

此過程將繼續，直到排序的子列表中包含所有未排序的值。現在我們將看到插入排序的一些編程方面。

算法

現在我們對這種排序技術的工作原理有了更大的瞭解，因此我們可以推導出簡單的步驟來實現插入排序。

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the 
 value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

偽代碼

procedure insertionSort( A : array of items )
 int holePosition
 int valueToInsert
 for i = 1 to length(A) inclusive do:
 /* select value to be inserted */
 valueToInsert = A[i]
 holePosition = i
 /*locate hole position for the element to be inserted */
 while holePosition > 0 and A[holePosition-1] > valueToInsert do:
 A[holePosition] = A[holePosition-1]
 holePosition = holePosition -1
 end while
 /* insert the number at hole position */
 A[holePosition] = valueToInsert
 end for
end procedure

C代碼

#include <stdio.h>
#include <stdbool.h>
#define MAX 7
int intArray[MAX] = {4,6,3,2,1,9,7};
void printline(int count) {
 int i;
 for(i = 0;i < count-1;i++) {
 printf("=");
 }
 printf("=\n");
}
void display() {
 int i;
 printf("["); 

 // navigate through all items 
 for(i = 0;i < MAX;i++) {
 printf("%d ",intArray[i]);
 }
 printf("]\n");
}
void insertionSort() {
 int valueToInsert;
 int holePosition;
 int i;
 // loop through all numbers 
 for(i = 1; i < MAX; i++) { 
 // select a value to be inserted. 
 valueToInsert = intArray[i];
 // select the hole position where number is to be inserted 
 holePosition = i;
 // check if previous no. is larger than value to be inserted 
 while (holePosition > 0 && intArray[holePosition-1] > valueToInsert) {
 intArray[holePosition] = intArray[holePosition-1];
 holePosition--;
 printf(" item moved : %d\n" , intArray[holePosition]);
 }
 if(holePosition != i) {
 printf(" item inserted : %d, at position : %d\n" , valueToInsert,holePosition);
 // insert the number at hole position 
 intArray[holePosition] = valueToInsert;
 }
 printf("Iteration %d#:",i);
 display();
 } 
}
void main() {
 printf("Input Array: ");
 display();
 printline(50);
 insertionSort();
 printf("Output Array: ");
 display();
 printline(50);
}
/<stdbool.h>/<stdio.h>

輸出

Input Array: [4 6 3 2 1 9 7 ]
==================================================
Iteration 1#:[4 6 3 2 1 9 7 ]
 item moved : 6 

 item moved : 4
 item inserted : 3, at position : 0
Iteration 2#:[3 4 6 2 1 9 7 ]
 item moved : 6
 item moved : 4
 item moved : 3
 item inserted : 2, at position : 0
Iteration 3#:[2 3 4 6 1 9 7 ]
 item moved : 6
 item moved : 4
 item moved : 3
 item moved : 2
 item inserted : 1, at position : 0
Iteration 4#:[1 2 3 4 6 9 7 ]
Iteration 5#:[1 2 3 4 6 9 7 ]
 item moved : 9
 item inserted : 7, at position : 5
Iteration 6#:[1 2 3 4 6 7 9 ]
Output Array: [1 2 3 4 6 7 9 ]
==================================================

總結

一個for和一個while循環，for用於遍歷已經排序好的數組，while用於遍歷未排序的數組。進行交換。

代碼如下


// 插入排序
public class insertSort {
 public static void sort(int[] numbers){
 // 其中insert為要插入的數據
 int i, j , insert;
 // 從數組的第二個元素開始循環數組中的元素插入
 for(i = 1; i < numbers.length; i++){
 // 用於保存被替換的值
 insert = a[i];
 // 用於保存已經排序好的列表 

 j = i - 1;
 // 尋找剩餘列表的數組，用於進行插入
 while(j >= 0 && insert < a[j]){
 // 把待插入的位置挪開
 a[j + 1] = a[j];
 j--;
 }
 // 進行插入
 a[j + 1] = insert;
 }
 }
}