淺談常見排序算法實現(xiàn)原理及性能優(yōu)化

◆

(河南省鄭州市第十一中學(xué))

1行業(yè)背景

隨著計算機技術(shù)和網(wǎng)絡(luò)技術(shù)的高速發(fā)展，如今越來越多行業(yè)都希望借助計算機的能力進(jìn)行發(fā)展，這也就衍生出了互聯(lián)網(wǎng)行業(yè)和軟件行業(yè)的急速擴張。目前市場上需要大量的計算機人才，并且薪資待遇都很可觀。除了計算機相關(guān)專業(yè)人才，其他專業(yè)的人才同樣大量地投入IT市場。為了適應(yīng)目前膨脹的IT環(huán)境，計算機編程語言也從最初的指令語言，匯編語言發(fā)展到目前各種各樣的高級語言。

高級語言的出現(xiàn)使得人們經(jīng)過短時間的培訓(xùn)就能夠進(jìn)行簡單的軟件開發(fā)，所以現(xiàn)在大家戲稱普通程序員為“碼農(nóng)”。舉個簡單的例子，在Java語言中，簡單的Arrays.sort()方法，就可以對一個數(shù)組進(jìn)行排序。但是這句代碼的背后隱藏著什么，它是如何實現(xiàn)的，它的性能如何，對于使用它的人來說可能未必清楚。

本文將通過Java語言對常見的排序算法的實現(xiàn)原理進(jìn)行剖析，介紹不同的排序算法的適用場景和性能高低。

2 Java語言介紹

Java語言是一種開源的高級編程語言，封裝性很強。Java代碼最終會編譯成class文件，在Java虛擬機上執(zhí)行的，所以Java是不受操作系統(tǒng)的限制的，具有跨平臺特性，是目前業(yè)界非常流行的一門語言。

由于Java是一門高級程序語言，所以使用Java的程序員可以調(diào)用很多Java基礎(chǔ)包中或是其他人編寫的工具類中很簡單的方法完成較為復(fù)雜的功能。比如在上一節(jié)提到的對數(shù)組排序的方法。Java語言令軟件開發(fā)的門檻降低了很多，使更多的人可以快速成為Java開發(fā)者。

3常用排序算法簡介

3.1冒泡排序

冒泡排序是一個相當(dāng)經(jīng)典的排序算法，因為它更接近于人類直觀的排序方式。它的排序思想如同它的名字，通過兩兩交換，將數(shù)字像水中的泡泡一樣，有序地冒出來。它的最佳時間復(fù)雜度是O(n^2)。

3.2快速排序

快速排序雖然名為“快速”，但它未必是最快的排序算法，因為在不同的場景下，排序算法的性能是會受到影響的。但總體上來講，快速排序的性能還是不錯的。它采用了分而治之和遞歸的思想，使數(shù)組不會被多次循環(huán)嵌套遍歷，在多數(shù)場景下，會大大提升排序的效率和性能。它的最佳時間復(fù)雜度為O(nlgn)。

3.3插入排序

插入排序不能說是一個非常好的排序方法，因為它的思想較為古板，但卻非常好理解。他將數(shù)組中的數(shù)字分為有序部分和無序部分，不斷從無序部分將數(shù)據(jù)插入有序部分中，并且插入后依然有序，這就需要每次都找到數(shù)據(jù)要插入的位置。如果數(shù)組本來就是有序的，那么此時的復(fù)雜度為O(n)；如果數(shù)組本來是倒序的，那么插入排序的時間復(fù)雜度就為O(n^2)。插入排序較適應(yīng)于元素少的數(shù)組進(jìn)行排序。

3.4選擇排序

選擇排序應(yīng)該是最為簡單直觀的排序方法了，它每次都遍歷數(shù)組，從中選擇出最大(最小)的元素，放在數(shù)組的第一位，直到所有元素全部排序完成。選擇排序在不同的場景下都會執(zhí)行相同次數(shù)的遍歷，所以性能不是很高。它的時間復(fù)雜度是O(n^2)。

4排序算法原理剖析

以上排序方法中，插入排序和選擇排序的原理都較為直觀，本文不對其進(jìn)行過多的介紹。下面主要對冒泡排序和快速排序算法進(jìn)行深度地剖析。

4.1快速排序原理研究

快速排序由于時間復(fù)雜度為O(nlgn)，排序效率較高，因此經(jīng)常被采用，再加上快速排序的思想——分治法也非常實用，因此很多知名軟件公司，如騰訊、微軟都會在筆試或面試中對“快速排序”進(jìn)行提問。

快速排序的基本思想是：

1.先從數(shù)列中取出一個數(shù)作為基準(zhǔn)數(shù)。

2.將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。

3.再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個數(shù)。

以下是快速排序的算法模擬過程，待排序數(shù)組如下：

首先定義變量：i，j，X，其中i是指向數(shù)組起始位置的游標(biāo)值，j是指向數(shù)組末尾的游標(biāo)值。X為基準(zhǔn)數(shù)。

(1)初始狀態(tài)下：i=0;j=9;X=72。

(2)從數(shù)組末尾開始找比基準(zhǔn)數(shù)小的數(shù)，找到游標(biāo)位置在8的時候，值47小于基準(zhǔn)值72。此時將0位置的數(shù)置為47，i加1。此時數(shù)組的8位置被空了下來，就要從左邊開始找比基準(zhǔn)數(shù)大的數(shù)字去填充8位置。此時找到位置3的值86大于基準(zhǔn)值72。這時就將8位置的值置為86，j減1。

(3)此時的i=3，j=7，X=72。

(4)位置3被空下來，就要從j的位置開始找比基準(zhǔn)值小的數(shù)，找到位置5的值40比基準(zhǔn)值小，此時將位置3的值置為40，i加1。

(5)此時i=4，j=5，X=72。

(6)繼續(xù)從i開始找比基準(zhǔn)值大的數(shù)，當(dāng)i加1等于j時，此次排序結(jié)束。數(shù)組為：

可以看出位置5前的數(shù)都比72小，后面的數(shù)都比72大。因此再對位置0到4和位置6到9這二個子區(qū)間重復(fù)上述步驟就可以將數(shù)組排序了。

4.2冒泡排序原理研究

冒泡排序非常容易理解，設(shè)數(shù)組長度為n。

(1)從第一個數(shù)開始比較相鄰的前后二個數(shù)據(jù)，如果前面數(shù)據(jù)大于后面的數(shù)據(jù)，就將二個數(shù)據(jù)交換。

(2)這樣對數(shù)組的第0個數(shù)據(jù)到n-1個數(shù)據(jù)進(jìn)行一次遍歷后，最大的一個數(shù)據(jù)就“沉”到數(shù)組第n-1個位置。

(3)n=n-1，如果n不為0就重復(fù)前面二步，否則排序完成。這樣就可以將一個無序的數(shù)組排序。

5冒泡排序算法性能優(yōu)化

5.1第一次優(yōu)化

在第四節(jié)中，本文已經(jīng)用Java代碼實現(xiàn)了冒泡排序的排序功能。但是可以看出原數(shù)組a中的后半部分已經(jīng)是排序狀態(tài)，其實不必要循環(huán)20次，可能在某次排序后數(shù)組已經(jīng)是有序狀態(tài)了。所以就要考慮進(jìn)行性能優(yōu)化。

我們可以試想，如果某次排序中沒有交換元素位置的事件發(fā)生，那么就可以認(rèn)為是該數(shù)組已經(jīng)排序成功了，就不需要在進(jìn)行排序。我們對冒泡排序進(jìn)行了如下優(yōu)化：

可以看出效果很明顯，在循環(huán)了5次后，就已經(jīng)是有序數(shù)組了，程序便停止排序工作。

5.2第二次優(yōu)化

在5.1節(jié)中對冒牌排序做了部分優(yōu)化，使得排序的循環(huán)次數(shù)從20次減少到了5次?？梢哉f減少了3/4的工作量，性能提升非常大。但是同時我們發(fā)現(xiàn)了另一個問題，雖然5.1節(jié)中的程序使循環(huán)次數(shù)減少了，但是每次的內(nèi)部循環(huán)次數(shù)依然沒有變化，每次循環(huán)還是要對比到最后一個數(shù)為止。

我們試想，如果數(shù)組的后半部分已經(jīng)是有序的數(shù)組了，那么我們只要記錄上一次循環(huán)的最后一次交換的位置，在本次循環(huán)時，只要將元素“冒”到該位置，就可以避免每次循環(huán)中都要對比到最后一個數(shù)。我們對冒泡排序進(jìn)行了第二次優(yōu)化：

可以看出，與上次優(yōu)化一樣，程序只循環(huán)了5次就結(jié)束了排序工作，但是相比于第一次循環(huán)，后幾次循環(huán)的內(nèi)部循環(huán)數(shù)驟減，又一次提升了排序的性能。

6總結(jié)

本文通過介紹了幾種常見的排序算法的思想和時間復(fù)雜度，反映出在計算機世界中，任何一個細(xì)小的地方都是可以用心去研究其內(nèi)涵的。通過介紹了冒泡排序的性能優(yōu)化方案，能夠看出，即使是同一種思想的算法，只要掌握了算法的核心原理，就可以設(shè)法提高其性能。

對于一些簡單的程序來講，選擇哪一種算法來排序數(shù)據(jù)可能對程序的執(zhí)行時間和結(jié)果都不會有太大的影響，甚至有時可以忽略不計。但是對于計算量巨大的程序來講，不合適或者性能較低的算法可能就會嚴(yán)重影響程序的整體性能了。所以在我們學(xué)習(xí)計算機技術(shù)的過程中，要知其然，更要知其所以然，這樣才能更好地了解計算機知識。

參考文獻(xiàn)：

[1]唐紅杰.Java語言程序設(shè)計之Java基本語法的教學(xué)研究[J].軟件，2014，(06) ：23-24.

[2]劉建科，馮媛媛.快速排序算法的教學(xué)要點與方法探討[J].電腦知識與技術(shù)，2016，(6X) ：117-118.

[3]程妮.C語言中冒泡排序算法的教學(xué)設(shè)計與分析[J].現(xiàn)代計算機，2016，(10) ：59-63.

[4]黃福員，聶瑞華.冒泡排序算法的改進(jìn)[J].計算機技術(shù)與發(fā)展，2003，(11) ：26-27.