簡單選擇排序算法的改進及分析

張憶文　譚　霽

[摘要]排序是計算機程序設計的重要操作,經典的排序包括:冒泡排序、選擇排序、插入排序等等;以簡單選擇排序算法為基礎,對其進行改進,通過分析得出與之具有同樣行之有效、甚至更高的排序效率。

[關鍵詞]簡單選擇排序 改進算法 分析

中圖分類號:TP3文獻標識碼:A文章編號:1671-7597(2009)0920077-01

排序是將數據元素的任一序列,重新排列成一個關鍵字有序的序列。基于比較和移動的排序算法具有通用性,包括插入排序、選擇排序、交換排序、歸并排序、計數排序[1]。各種排序的算法各具有優缺點,但就其全面性能而言,很難提出一種被公認的最好的方法。評價算法主要考慮其時間復雜度、空間復雜度、穩定性等。筆者通過對簡單選擇排序算法進行改進,使其交換或移動的次數減少,從而提高效率。

一、簡單選擇排序[2]

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

(一)主要代碼片段

for(i=0;i

{for(j=i+1;j

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

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

(二)算法分析

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

二、改進算法一

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

(一)主要代碼片段

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;}}

(二)算法分析

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

三、改進算法二

簡單的選擇排序在一趟排序的過程只能確定一個元素的正確位置,現改進為在一趟的排序過程中確定兩個元素的位置,即一個最大值和一個最小值。對一個待排序序列應比較第一個元素和最后一個元素的值,若逆序就交換,這樣可以保證第一個元素比最后一個元素小;將2到n-1個元素依次同第一個元素比較;若逆序則交換;否則和最后一個元素比較若逆序則交換;這樣在一趟排序過程中就確定兩個元素的位置;對剩余的n-2個元素,重復上述過程直至全部有序[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;}}

(二)算法分析

時間復雜度:當待排序序列為正序時,移動的次數最少為0次;最壞時所需的移動次數為n-1,大大的低于簡單選擇排序的3n(n-1)/2;從比較次數來看,循環的次數減少一半,所以比較的次數為n(n-1)/4相對與簡單選擇排序也有所降低。 所以時間復雜度為O(n2)。

四、改進算法三

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

(一)主要代碼片段

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個元素的序列比較n/2(n為偶數)次或為(n+1)/2次(n為奇數);為討論方便取n為偶數;在前半部分選出最小值要比較n/2-1次;后半部分選出最大值需要比較n/2-1次;所以在一趟排序確定兩個元素的正確位置要3n/2-2次。在剩余的n-2個元素中確定兩個元素的正確位置需要3(n-2)/2-2次;以此類推可知最后一趟剩余的兩個元素的比較次數為1次;所以總的比較次數為3n(n-2)/8;這比簡單選擇排序也有所降低。當待排序序列為正序時,移動的次數最少為0次;最壞時所需的移動次數為9n(n-2)/8比簡單選擇排序也有所降低。

五、各種排序的比較

六、結束語

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

參考文獻:

[1]嚴蔚敏等,數據結構(C語言版)[M].北京:清華大學出版社,2005.7.

[2]潭浩強,C程序設計[M].北京:清華清華大學出版社,1999.4.

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

作者簡介:

張憶文,男,本科生,長江師范學院數學與應用數學專業;譚霽,男,本科生,長江師范學院數學與應用數學專業。