直接插入排序

直接貼核心代碼

for(i=1;i<n;i++)//n為數組長度{t=a[i];//取出待比較元素for(j=i-1;j>=0&&a[j]>t;j--)//在此元素比前數大的情況下進入循環{a[j+1]=a[j];//前面的元素后移}a[j+1]=t;//確定位置，將取出的元素插入}

以上就是整個直接插入排序的核心部分，其中t是用來暫存取出的元素。此法時間復雜度O(n^2)。

二分插入排序

其實二分插入排序在已經會了直接插入排序的基礎上十分簡單，只需要在你取出元素后對其進行二分法判斷，直到找到插入位置，下面放核心代碼

for(i=1;i<n;i++)//n為數組長度{t=a[i];//取出待比較元素int left=0;//定義左邊界int right=i-1;//定義右邊界，所以有序區間為[0,i-1]while(left<=right)//在有序區間進行折半查找，找到插入位置{int mid=(right+left)/2;//先取有序區間中間值if(t<a[mid])//如果取出元素小于中間值，右邊界縮小，總之就是二分法的原理，讀者應該能理解{right =mid-1;}else{left = mid+1;}}//通過這里的循環，已經找到了插入位置for(j=i-1;j>=left;j--)//這一步就是移動元素，騰出插入位置{a[j+1]=a[j];}a[left]=t;//將元素插入}

以上就是二分插入排序的核心代碼，其實就是在直接插入的基礎上，用了二分法去判斷元素的插入位置。此法時間復雜度最好時O(nlog2n)，最壞時O(n^2)，所以比起直接插入排序是有一定優勢的。

希爾排序

當數據量很大，并且有序程度很低時，上面兩種方法的時間復雜度很高，這時就可以采用希爾排序，其時間復雜度為O(n^(1.3—2))。
其實希爾排序不難理解，就是先對數據進行的分組排序，讓數據變的整體有序，在此基礎上，最終進行直接插入排序，下面直接放核心代碼部分

for(gap=n/2;gap>0;gap/=2)//n為數組長度，等長（gap）取子序列排序，最終取長度為1，則進行正常的插入排序{for(i=gap;i<n;i+=gap)//對子序列進行插入排序{t=a[i]; //看到沒，其實整個代碼和直接插入排序差別不大，只是將for(j=i-gap;j>=0&&a[j]>t;j-=gap) //直接插入排序里的1換成了這里的長度（gap），其他地方{ //都一模一樣，只有能掌握直接插入排序就能掌握希爾排序a[j+gap]=a[j];}a[j+gap]=t; }}

相信讀者應該能夠理解到這三種排序的區別與聯系了，快去自己實現試試吧！

總結

以上是生活随笔為你收集整理的插入排序（含希尔排序）的C/C++实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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