c語(yǔ)言的幾個(gè)算法排序

《c語(yǔ)言的幾個(gè)算法排序》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、算法排序http://blog.csdn.net/xiajun07061225/article/details/6898246下面簡(jiǎn)要總結(jié)了常用的一些排序算法。如有錯(cuò)誤，還請(qǐng)大家指正、見諒~~謝謝~~【1】插入排序：是一個(gè)對(duì)少量元素進(jìn)行排序的有效算法。實(shí)現(xiàn)比較簡(jiǎn)單。時(shí)間復(fù)雜度：O(n^2)，空間復(fù)雜度：O(1)。是穩(wěn)定的排序方法。代碼：viewplaincopytoclipboardprint?1.//insertion?sort??2.#include???3.using?n

2、amespace?std;??4.??5.//insertion?sort??6.void?InsertionSort(int?*a,int?n)??7.{??8.????int?temp;??9.????for(int?i?=?1;i?=?0?&&?*(a?+?j)?>?temp)??14.????????

3、{??15.????????????*(a?+?j?+?1)?=?*(a?+?j);??16.????????????--j;??17.????????}??18.????????*(a?+?j?+?1)?=?temp;??19.????}??20.}??21.??22.int?main()??1.{??2.????int?n,temp;??3.????cout<<"please?input?the?number?of?the?values?that?need?to?sort:"<

4、4.????cin>>n;??5.????int?*a?=?(int*)malloc(n?*?sizeof(int));??6.????cout<<"please?input?each?value:"<>temp;??10.????????*(a?+?i)?=?temp;??11.????}??12.????/*?13.????//insertion?sort?14.???

5、?for(int?i?=?1;i?=?0?&&?*(a?+?j)?>?temp)?19.????????{?20.????????????*(a?+?j?+?1)?=?*(a?+?j);?21.????????????--j;?22.????????}?23.????????*(a?+?j?+?1)?=?temp;?

6、24.????}*/??25.????InsertionSort(a,n);??26.??27.????cout<<"the?values?after?sort:"<

7、方是：在查找插入位置的時(shí)候可以采用二分查找，但是這樣依然不可以把時(shí)間復(fù)雜度降低為O(nlogn)，因?yàn)橐苿?dòng)元素的復(fù)雜度沒(méi)有降低。所以時(shí)間復(fù)雜度仍然是O(n^2)。做此改進(jìn)需要添加函數(shù)InsertLoc用于二分查找需要插入的位置，以及修改函數(shù)InsertionSort的實(shí)現(xiàn)。具體如下：viewplaincopytoclipboardprint?1.//改進(jìn)：用二分查找來(lái)找到插入的位置??2.//在數(shù)組a[low]---a[high]查找val插入的位置??3.int?InsertLoc(int?*a

8、,int?low,int?high,int?val)??4.{??5.????if(low?==?high)??1.????{??2.????????if(val?>?*(a?+?low))return?(low?+?1);??3.????????else??4.????????????return?low;??5.????}??6.????int?mid?=?(low?+?high)?/?2;??7.????if(val?>?*(a?+?mid)?&&?val?>?*(a?+?m