簡(jiǎn)單選擇排序算法的改進(jìn)及分析

張憶文　譚　霽

[摘要]排序是計(jì)算機(jī)程序設(shè)計(jì)的重要操作,經(jīng)典的排序包括:冒泡排序、選擇排序、插入排序等等;以簡(jiǎn)單選擇排序算法為基礎(chǔ),對(duì)其進(jìn)行改進(jìn),通過(guò)分析得出與之具有同樣行之有效、甚至更高的排序效率。

[關(guān)鍵詞]簡(jiǎn)單選擇排序 改進(jìn)算法 分析

中圖分類號(hào):TP3文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1671-7597(2009)0920077-01

排序是將數(shù)據(jù)元素的任一序列,重新排列成一個(gè)關(guān)鍵字有序的序列?；诒容^和移動(dòng)的排序算法具有通用性,包括插入排序、選擇排序、交換排序、歸并排序、計(jì)數(shù)排序[1]。各種排序的算法各具有優(yōu)缺點(diǎn),但就其全面性能而言,很難提出一種被公認(rèn)的最好的方法。評(píng)價(jià)算法主要考慮其時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性等。筆者通過(guò)對(duì)簡(jiǎn)單選擇排序算法進(jìn)行改進(jìn),使其交換或移動(dòng)的次數(shù)減少,從而提高效率。

一、簡(jiǎn)單選擇排序[2]

簡(jiǎn)單選擇排序的基本思想:對(duì)待排序的序列進(jìn)行若干趟處理,通過(guò)n-i次關(guān)鍵字的比較,從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄和第i(1≤i≤n)個(gè)記錄進(jìn)行交換,這樣一趟處理就能確定一個(gè)數(shù)的位置,對(duì)n個(gè)數(shù)如果確定n-1個(gè)數(shù)的位置,則這n個(gè)數(shù)就排序成功。

(一)主要代碼片段

for(i=0;i

{for(j=i+1;j

if(a[i]>a[j])

{t=a[i];a[i]=a[j];a[j]=t;}}

(二)算法分析

時(shí)間復(fù)雜度:簡(jiǎn)單選擇排序過(guò)程中,當(dāng)待排序序列為正序時(shí),移動(dòng)的次數(shù)最少為0次;當(dāng)為逆序時(shí)最大為3n(n-1)/2;然而無(wú)論記錄是否有序所需比較的次數(shù)都為n(n-1)/2;所以時(shí)間復(fù)雜度為O(n2)。

二、改進(jìn)算法一

簡(jiǎn)單選擇排序在每趟中都選一個(gè)最小的關(guān)鍵字確定其正確的位置,上述算法只要相鄰元素逆序就要交換(移動(dòng));可以附設(shè)一個(gè)變量記錄其最小值,然后在與最小值交換,這樣可以大大的減少移動(dòng)的次數(shù)。

(一)主要代碼片段

for(i=0;i

{k=i;

for(j=i+1;j

if(a[i]>a[j])

k=j;

if(k!=i)

{t=a[i];a[i]=a[j];a[j]=t;}}

(二)算法分析

時(shí)間復(fù)雜度:當(dāng)待排序序列為正序時(shí),移動(dòng)的次數(shù)最少為0次;當(dāng)為逆序時(shí)最大為3(n-1),這比3n(n-1)/2大大的減少;比較的次數(shù)為n(n-1)/2;所以時(shí)間復(fù)雜度為O(n2)。

三、改進(jìn)算法二

簡(jiǎn)單的選擇排序在一趟排序的過(guò)程只能確定一個(gè)元素的正確位置,現(xiàn)改進(jìn)為在一趟的排序過(guò)程中確定兩個(gè)元素的位置,即一個(gè)最大值和一個(gè)最小值。對(duì)一個(gè)待排序序列應(yīng)比較第一個(gè)元素和最后一個(gè)元素的值,若逆序就交換,這樣可以保證第一個(gè)元素比最后一個(gè)元素小;將2到n-1個(gè)元素依次同第一個(gè)元素比較;若逆序則交換;否則和最后一個(gè)元素比較若逆序則交換;這樣在一趟排序過(guò)程中就確定兩個(gè)元素的位置;對(duì)剩余的n-2個(gè)元素,重復(fù)上述過(guò)程直至全部有序[3]。

(一)主要代碼片段

for(i=1;i<=n/2;i++)

{if(a[i-1]>a[n-i])

{t=a[i-1];a[i-1]=a[n-i];a[n-i]=t;}

for(j=i;j

if(a[i-1]>a[j])

{ t=a[i-1];a[i-1]=a[j];a[j]=t;}

else if(a[j]>a[n-i])

{t=a[j];a[j]=a[n-i];a[n-i]=t;}}

(二)算法分析

時(shí)間復(fù)雜度:當(dāng)待排序序列為正序時(shí),移動(dòng)的次數(shù)最少為0次;最壞時(shí)所需的移動(dòng)次數(shù)為n-1,大大的低于簡(jiǎn)單選擇排序的3n(n-1)/2;從比較次數(shù)來(lái)看,循環(huán)的次數(shù)減少一半,所以比較的次數(shù)為n(n-1)/4相對(duì)與簡(jiǎn)單選擇排序也有所降低。 所以時(shí)間復(fù)雜度為O(n2)。

四、改進(jìn)算法三

利用分治法的思想將第一個(gè)數(shù)和最后一個(gè)數(shù)比較若逆序,則交換;第二個(gè)數(shù)和倒數(shù)第二個(gè)數(shù)比較若逆序,則交換;直至第i個(gè)數(shù)和第i個(gè)數(shù)比較;將待排序序列分成兩部分,將小者放在前半部分,大的放在后半部分,然后再在前半部分選出最小值;后半部分選出最大值;對(duì)剩余的n-2個(gè)數(shù)做同樣的處理,直至全部有序。

(一)主要代碼片段

for(i=0,j=n-1;i<=j;i++,j--)

{while(i

if(a[i]>a[j])

{t=a[i];a[i-]=a[j];a[j]=t;i++;j--}

k=i-1;static m=0;static l=n-1;

for(t=m;t

if(a[t]>a[t+1])

{ r=a[t];a[t]=a[t+1];a[t+1]=r;}

for(t=k;t

if(a[t]>a[t+1])

{r=a[t];a[t]=a[t+1];a[t+1]=r;}

m++;l--;}

(二)算法分析

第一趟在n個(gè)元素的序列比較n/2(n為偶數(shù))次或?yàn)?n+1)/2次(n為奇數(shù));為討論方便取n為偶數(shù);在前半部分選出最小值要比較n/2-1次;后半部分選出最大值需要比較n/2-1次;所以在一趟排序確定兩個(gè)元素的正確位置要3n/2-2次。在剩余的n-2個(gè)元素中確定兩個(gè)元素的正確位置需要3(n-2)/2-2次;以此類推可知最后一趟剩余的兩個(gè)元素的比較次數(shù)為1次;所以總的比較次數(shù)為3n(n-2)/8;這比簡(jiǎn)單選擇排序也有所降低。當(dāng)待排序序列為正序時(shí),移動(dòng)的次數(shù)最少為0次;最壞時(shí)所需的移動(dòng)次數(shù)為9n(n-2)/8比簡(jiǎn)單選擇排序也有所降低。

五、各種排序的比較

六、結(jié)束語(yǔ)

各種改進(jìn)方法的思想和簡(jiǎn)單的選擇排序基本一致;都是在簡(jiǎn)單選擇排序的基礎(chǔ)上加以改進(jìn);使之成為一種更簡(jiǎn)單,效率更高的算法。

參考文獻(xiàn):

[1]嚴(yán)蔚敏等,數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)[M].北京:清華大學(xué)出版社,2005.7.

[2]潭浩強(qiáng),C程序設(shè)計(jì)[M].北京:清華清華大學(xué)出版社,1999.4.

[3]何洪英,雙向選擇排序算法的實(shí)現(xiàn)及性能研究,成功(教育),2007.9.

作者簡(jiǎn)介:

張憶文,男,本科生,長(zhǎng)江師范學(xué)院數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè);譚霽,男,本科生,長(zhǎng)江師范學(xué)院數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)。