數組排序算法淺析

張紫琳

?

數組排序算法淺析

張紫琳

摘要：數組排序是程序設計的一項重要內容，通過運用數組排序的算法，我們能夠將很多問題便捷化。在計算機編程中排序是經常遇到的一個問題，所有的數據只有經過一定的排序才會更有意義。在眾多算法中，本文對順序排序、冒泡排序和選擇排序這三種基本的排序算法進行詳細介紹。

關鍵詞：數組；排序算法；淺析

數組排序就是將數組中的元素按照某種特定的順序進行排列，如升序或降序。數組排序方法很多，有冒泡排序、順序排序、選擇排序等。本文對一個長度為N的整型數組a，以升序排列為例，對順序排序、選擇排序和冒泡排序的算法進行解析，并在最后加以比較。

一、順序排序

順序排序的主要思想是每一輪比較結束后都可以確定某一元素；在一輪的比較過程中，將要確定的位置上的元素與其后所有的元素進行比較；對于一個長為N的數組，需進行N－1輪比較。其第一輪的比較過程如下：

該輪中，a[0]與a[1]～a[n-1]的所有元素進行比較，比較過程中，如果發現哪個元素比a[0]小，則與a[0]進行交換。一輪比較之后，確定a[0]為數組中最小的元素。相同方法，依次確定a[1]、a[2]、a[3]…a[n-2]。

順序排序主要特點描述

由上表，可以寫出其實現代碼

for(i=0；i

{ for(j=i+1；j

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

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

可以發現當數組原有的順序是降序，要實現其升序排序時，每一輪中的交換的次數將會非常多，嚴重影響排序效率。所以對該方法進行改進：先找出數組中最小值，再與相應位置上的元素進行交換，這就是選擇排序。

選擇排序的主要過程描述

二、選擇排序

選擇排序的主要思想是每次從待排序的數據元素中選出最小的一個元素，放在待排序數列的起始位置，直到全部待排序列的數據元素全部排列完畢。

第一輪的比較過程如下：

選擇排序的實現代碼

for(i=0；i

{k=i；

for(j=i+1；ja[j]) k=j；

if(k!=i){t=a[k]；a[k]=a[i]；a[i]=t；} }

選擇排序相較于順序排序有更高的執行效率，而且思想同樣利于理解。

三、冒泡排序

冒泡排序的主要思想是“相鄰元素”之間的比較，如果前面的元素大于后面元素就把他們互換。一輪比較之后可以確定最后一個元素為最大，第二輪比較之后可以確定最后一個元素為第二大的元素……依次類推，第N－1輪比較，可以確定倒數第二個元素，這個時候數組的排序完成。冒泡排序的過程如下：

冒泡排序的實現代碼

for(i=N-2；i>=0；i--)

{for(j=0；j<=i；j++)

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

{t=a[j]；a[j]=a[j+1]；a[j+1]=t；}}

四、算法淺析

順序排序算法，思想簡單易于理解且適于任何的數組，無論什么情況下都可以使用；但是順序排序效率較低，可以采用選擇排序法進行改進；即使如此選擇排序的效率依然受到比較次數的影響，所以對于比較元素比較少的數組，可以采用冒泡排序法。

如果數組中99%的數值已經排序好，即只有很少的元素需要進行排序，可以選擇冒泡排序法；如果你所要排序的數據數目相對較少并滿足100個以下，你就可以采用選擇排序法；如果上述幾種情況都不滿足，那么就選普遍適用的排序算法即順序排序法即可。

五、結語

以上所述只是三種常見排序，在眾多的排序算法中各有優缺點，每一種算法只有在某一種情況下才表現的最好，我們應當合理的根據實際情況選擇算法。

參考文獻：

[1]張巍.基于PageRank算法的搜索引擎優化策略研究[D].四川大學，2005.

[2]郭敏杰.基于云計算的海量網絡流量數據分析處理及關鍵算法研究[D].北京郵電大學，2014.

[3]譚浩強.C程序設計.清華大學出版社，2010.

（作者單位：江蘇省宿城中等專業學校）