C语言的几个算法排序.doc

算法排序 /xiajuarticle/details/6898246 下面简要总结了常用的一些排序算法。如有错误，还请大家指正、见谅~~谢谢~~ 【1】插入排序： 是一个对少量元素进行排序的有效算法。实现比较简单。时间复杂度：O(n^2)，空间复杂度：O(1)。是稳定的排序方法。 代码： view plaincopy to clipboardprint? //insertion?sort ?? #include?iostream ?? using?namespace?std;?? ?? //insertion?sort ?? void?InsertionSort(int?*a,int?n)?? {?? ????int?temp;?? ????for(int?i?=?1;i??n;++i)?? ????{?? ????????temp?=?*(a?+?i);?? ????????int?j?=?i?-?1;?? ????????while(j?=?0??*(a?+?j)??temp)?? ????????{?? ????????????*(a?+?j?+?1)?=?*(a?+?j);?? ????????????--j;?? ????????}?? ????????*(a?+?j?+?1)?=?temp;?? ????}?? }?? ?? int?main()?? {?? ????int?n,temp;?? ????coutplease?input?the?number?of?the?values?that?need?to?sort:endl;?? ????cinn;?? ????int?*a?=?(int*)malloc(n?*?sizeof(int));?? ????coutplease?input?each?value:endl;?? ????for(int?i?=?0;i??n;++i)?? ????{?? ????????cintemp;?? ????????*(a?+?i)?=?temp;?? ????}?? ????/*? ????//insertion?sort? ????for(int?i?=?1;i??n;++i)? ????{? ????????temp?=?*(a?+?i);? ????????int?j?=?i?-?1;? ????????while(j?=?0??*(a?+?j)??temp)? ????????{? ????????????*(a?+?j?+?1)?=?*(a?+?j);? ????????????--j;? ????????}? ????????*(a?+?j?+?1)?=?temp;? ????}*/?? ????InsertionSort(a,n);?? ?? ????coutthe?values?after?sort:endl;?? ????for(int?i?=?0;i??n;++i)?? ????????cout*(a?+?i)?;?? view plaincopy to clipboardprint? free(a);?? view plaincopy to clipboardprint? }?? 数据测试： 上述代码可以改进的一个地方是：在查找插入位置的时候可以采用二分查找，但是这样依然不可以把时间复杂度降低为O(nlogn)，因为移动元素的复杂度没有降低。所以时间复杂度仍然是O(n^2)。 做此改进需要添加函数InsertLoc用于二分查找需要插入的位置，以及修改函数InsertionSort的实现。具体如下： view plaincopy to clipboardprint? //改进：用二分查找来找到插入的位置 ?? //在数组a[low]a[high]查找val插入的位置 ?? int?InsertLoc(int?*a,int?low,int?high,int?val)?? {?? ????if(low?==?high)?? ????{?? ????????if(val??*(a?+?low))return?(low?+?1);?? ????????else?? ????????????return?low;?? ????}?? ????int?mid?=?(low?+?high)?/?2;?? ????if(val??*(a?+?mid)??val??*(a?+?mid?+?1))?? ????????return?InsertLoc(a,mid?+?1,high,val);?? ????else?if(val??*(a?+?mid)??val??*(a?+?mid?+?1))?? ????????return?InsertLoc(a,l