幾種常用的排序算法

《幾種常用的排序算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、幾種常用的排序算法(轉(zhuǎn)載收藏)2009-03-0623:161選擇排序先在整個(gè)序列中選出關(guān)鍵字值最小的元素,如果它不是第一個(gè)元素,則將它和第一個(gè)元素交換;然后在除一個(gè)除第一個(gè)位置上的元素以外的其余元素中再選出關(guān)鍵值次最小的元素,如果它不在第二個(gè)位置,則和第二個(gè)位置上的元素進(jìn)行交換;依次類推,直至所有元素排序完成.該算法是不穩(wěn)定的.[1]算法:選擇排序Algorithmselect_sort(s[])//s[]為sortseq型排序表,n為整型常量//i,j,k為整型//t為元素類型{For(i=1;i<=n-1;++i){k=I;for(j=i+1;j<=n;++j)if(s[j]

2、.key

3、插完.該算法是穩(wěn)定的算法;直接插入排序Algorithminsert_sort(s[])//s[]為sortseq型排序表,n為整型常量//i,j為整型{for(i=2;i<=n;++i){s[0]=s[i];for(j=i–1;s[j].key>s[0].key;--j)s[j+1]=s[j];s[j+1]=s[0];}}2)對(duì)半插入排序直接插入排序中,將查找第i個(gè)元素插入位置的方法改用對(duì)半法進(jìn)行關(guān)鍵字間的比較,便得到對(duì)半插入排序.為了用對(duì)半法查找插入位置,待排序的n個(gè)元素序列的存儲(chǔ)結(jié)構(gòu)須采用順序存儲(chǔ)方式.該算法是穩(wěn)定的.算法:對(duì)半插入排序algoreithmbin_sort(s

4、[]){for(i=2;i<=n;++i){s[0]=s[i];L=1;h=i–L;while(L<=h){m=(L+h)/2;if(s[m].key>s[0].key)h=m–1;elseL=m+1;}for(j=i–1;j>=1;--j)s[j+1]=s[j];s[L]=[0];}}注:本文用大寫L以區(qū)別小寫l與數(shù)字1的區(qū)別3冒泡排序先將第一個(gè)元素的關(guān)鍵字和第二個(gè)元素的關(guān)鍵字進(jìn)行比較,若不滿足順序要求,則將兩個(gè)元素進(jìn)行交換;然后比較第二個(gè)和第三個(gè)元素的關(guān)鍵字并作同樣處理;依次類推,直至第n-1個(gè)元素的位置和第n個(gè)元素進(jìn)行比較并處理完.這時(shí)關(guān)鍵字值最大的元素被交換到最后一個(gè)元素的

5、位置上,這是一趟排序過(guò)程.重復(fù)執(zhí)行這種運(yùn)算過(guò)程,不過(guò)第2趟只需對(duì)前n-1個(gè)元素進(jìn)行排序,第3趟只需對(duì)前n-2個(gè)元素進(jìn)行排序,如此下去,直至在一趟排序中沒(méi)有元素進(jìn)行過(guò)交換或最多進(jìn)行了n-1趟排序?yàn)橹?算法:冒泡排序algorithmbubble_sort([])//s[]為sortseq型排序表,n為整型常量//i,j,done為整型//temp為元素類型{i=1;done=0;while(i<=n–1&&!done){done=1;for(j=1;j<=n–i;++j)if(s[j].key>s[j+1].key){done=0;temp=s[j];s[j]=s[j+1];s[j+

6、1]=tem[;}++i;}}4快速排序從排序過(guò)程來(lái)看,快速排序與冒泡排序一樣,也是通過(guò)元素交換方式來(lái)進(jìn)行排序的.快速排序方法的基本思想是:在待排序的元素序列中任取一個(gè)元素(例如取第一個(gè)元素),通過(guò)一趟排序,以該元素的關(guān)鍵字為標(biāo)準(zhǔn),將待排元素序列分成兩部分,所有關(guān)鍵不大于該元素關(guān)鍵字的元素排在它的位置之前(即左邊),所有關(guān)鍵字不小于該元素關(guān)鍵字的元素排在它的位置之后(即右邊),把該元素排在這兩部分的中間,這就是該元素最終排序的位置.然后分別對(duì)這兩部分重復(fù)上述排序,直至所有的元素都排到序列的相應(yīng)位置上為止.該算法是不穩(wěn)定的算法:快速排序.algorithmquick_sort(s[]

7、,L,r)//s[]為sortseq型排序表//L,j,r為整型//k為keytype型//temp為元素型{if(L=k&&ij){s[i++]=s[j];while(s[i].key<=k&&i