數(shù)組排序算法淺析

張紫琳

?

數(shù)組排序算法淺析

張紫琳

摘要：數(shù)組排序是程序設(shè)計(jì)的一項(xiàng)重要內(nèi)容，通過(guò)運(yùn)用數(shù)組排序的算法，我們能夠?qū)⒑芏鄦?wèn)題便捷化。在計(jì)算機(jī)編程中排序是經(jīng)常遇到的一個(gè)問(wèn)題，所有的數(shù)據(jù)只有經(jīng)過(guò)一定的排序才會(huì)更有意義。在眾多算法中，本文對(duì)順序排序、冒泡排序和選擇排序這三種基本的排序算法進(jìn)行詳細(xì)介紹。

關(guān)鍵詞：數(shù)組；排序算法；淺析

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

一、順序排序

順序排序的主要思想是每一輪比較結(jié)束后都可以確定某一元素；在一輪的比較過(guò)程中，將要確定的位置上的元素與其后所有的元素進(jìn)行比較；對(duì)于一個(gè)長(zhǎng)為N的數(shù)組，需進(jìn)行N－1輪比較。其第一輪的比較過(guò)程如下：

該輪中，a[0]與a[1]～a[n-1]的所有元素進(jìn)行比較，比較過(guò)程中，如果發(fā)現(xiàn)哪個(gè)元素比a[0]小，則與a[0]進(jìn)行交換。一輪比較之后，確定a[0]為數(shù)組中最小的元素。相同方法，依次確定a[1]、a[2]、a[3]…a[n-2]。

順序排序主要特點(diǎn)描述

由上表，可以寫(xiě)出其實(shí)現(xià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；} }

可以發(fā)現(xiàn)當(dāng)數(shù)組原有的順序是降序，要實(shí)現(xiàn)其升序排序時(shí)，每一輪中的交換的次數(shù)將會(huì)非常多，嚴(yán)重影響排序效率。所以對(duì)該方法進(jìn)行改進(jìn)：先找出數(shù)組中最小值，再與相應(yīng)位置上的元素進(jìn)行交換，這就是選擇排序。

選擇排序的主要過(guò)程描述

二、選擇排序

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

第一輪的比較過(guò)程如下：

選擇排序的實(shí)現(xiàn)代碼

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

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

三、冒泡排序

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

冒泡排序的實(shí)現(xiàn)代碼

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

四、算法淺析

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

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

五、結(jié)語(yǔ)

以上所述只是三種常見(jiàn)排序，在眾多的排序算法中各有優(yōu)缺點(diǎn)，每一種算法只有在某一種情況下才表現(xiàn)的最好，我們應(yīng)當(dāng)合理的根據(jù)實(shí)際情況選擇算法。

參考文獻(xiàn)：

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

[2]郭敏杰.基于云計(jì)算的海量網(wǎng)絡(luò)流量數(shù)據(jù)分析處理及關(guān)鍵算法研究[D].北京郵電大學(xué)，2014.

[3]譚浩強(qiáng).C程序設(shè)計(jì).清華大學(xué)出版社，2010.

（作者單位：江蘇省宿城中等專(zhuān)業(yè)學(xué)校）