思想：

插入排序就是每一步都將一個待排數據按其大小插入到已經排序的數據中的適當位置，直到全部插入完畢。

從i=1開始往后遍歷，對于每個數據記錄為temp，從該數據向前探索若比temp大則后移，直至第一個比temp小的數據，將temp插入到這個數據之后。

?

?

1 #include <iostream> 2 3 using namespace std; 4 5 void InsertSort(int* arr,int n) 6 { 7 int i,j,temp; 8 for(i=1;i<n;i++) 9 { 10 temp = arr[i]; 11 j = i - 1; 12 while(j>=0 && temp < arr[j]) 13 { 14 arr[j+1] = arr[j]; 15 j--; 16 } 17 arr[j+1] = temp; 18 } 19 } 20 21 int main() 22 { 23 int * arr; 24 int n; 25 cout<<"Input the arr length:"<<endl; 26 cin>>n; 27 arr = new int[n]; 28 cout<<"Input the arr elements:"<<endl; 29 for(int i=0;i<n;i++) 30 { 31 cin>>arr[i]; 32 } 33 InsertSort(arr,n); 34 cout<<"The outcome:"<<endl; 35 for(int i=0;i<n;i++) 36 cout<<arr[i]<<endl; 37 return 0; 38 } 39 40 /************ 41 穩定 42 最好情況：數組正序排列，每次第i個記錄一進入內層循環就退出，只有外層的n-1次。 43 時間復雜度O(n)。 44 最差情況：數組逆序排列（正好與需要排列的順序相反），每次第i個記錄都要在內層循環中比較i次。 45 時間復雜度為O(n^2)。 46 平均情況：O(n^2)。 47 空間復雜度：一個臨時變量O(1)。 48 插入排序適用于待排序元素較少的情況。如果數組已有序用插入排序也很合適。 49 **************/ View Code

?

轉載于:https://www.cnblogs.com/CnZyy/p/3314629.html

總結

以上是生活随笔為你收集整理的各种排序总结（一）直接插入排序的全部內容，希望文章能夠幫你解決所遇到的問題。

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