一、直接插入排序

空間復雜度：O(1)

時間復雜度：O(n^2)

穩定性：穩定

適用性：順序表和鏈表

//直接插入排序 void InsertSort1(int A[],int n){int i,j,temp;for(i=1;i<n;i++){if(A[i]<A[i-1]){temp=A[i];for(j=i-1;j>=0&&A[j]>temp;j--){A[j+1]=A[j]; //元素右移}A[j+1]=temp;}} }

二、折半插入排序

空間復雜度：O(1)

時間復雜度：O(n^2)

穩定性：穩定

適用性：順序表

//折半插入排序 void InsertSort2(int A[],int n){int i,j,low,high,mid;for(i=2;i<=n;i++){A[0]=A[i];low=1;high=i-1;while(low<=high){mid=(low+high)/2;if(A[mid]>A[0])high=mid-1;elselow=mid+1;}for(j=i-1;j>=low;j--)A[j+1]=A[j];A[j+1]=A[0];} }

三、希爾排序（縮小增量排序）

空間復雜度：O(1)

時間復雜度：O(n^1.3)，最壞O(n^2)

穩定性：不穩定

適用性：順序表

//希爾排序 void ShellSort(int A[],int n){for(d=n/2;d>=1;d=d/2){for(i=d+1;i<=n;i++){if(A[i]<A[i-d]){A[0]=A[i];for(j=i-d;j>0&&A[0]<A[j];j-=d)A[j+d]=A[j];A[j+d]=A[0];}}} }

?

總結

以上是生活随笔為你收集整理的三种插入排序算法：直接插入排序、折半插入排序、希尔插入排序的全部內容，希望文章能夠幫你解決所遇到的問題。

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