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

張子瀚

【摘要】隨著計(jì)算機(jī)技術(shù)的快速發(fā)展，企業(yè)和用戶對軟件的要求不再是僅僅停留在滿足基本需求。在此基礎(chǔ)之上，企業(yè)和用戶希望軟件能夠具有更好地健壯性和更高的性能。目前，計(jì)算機(jī)程序語言不斷更新?lián)Q代，程序員在編寫代碼時(shí)，透明度越來越高，可能表面上，但是卻不了解底層的實(shí)現(xiàn)。通過使用Java編程語言，研究基礎(chǔ)的幾個(gè)排序算法的實(shí)現(xiàn)原理，并且討論如何提高排序算法的性能。

【關(guān)鍵詞】排序算法 高性能 Java

1行業(yè)背景

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

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

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

2 Java語言介紹

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

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

3常用排序算法簡介

3.1冒泡排序

冒泡排序是一個(gè)相當(dāng)經(jīng)典的排序算法，因?yàn)樗咏谌祟愔庇^的排序方式。它的排序思想如同它的名字，通過兩兩交換，將數(shù)字像水中的泡泡一樣，有序地冒出來。它的最佳時(shí)間復(fù)雜度是O（n^2）。

3.2快速排序

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

3.3插入排序

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

3.4選擇排序

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

4排序算法原理剖析

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

4.1快速排序原理研究

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

快速排序的基本思想是：

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

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

3.再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(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的時(shí)候，值47小于基準(zhǔn)值72。此時(shí)將0位置的數(shù)置為47，i加1。此時(shí)數(shù)組的8位置被空了下來，就要從左邊開始找比基準(zhǔn)數(shù)大的數(shù)字去填充8位置。此時(shí)找到位置3的值86大于基準(zhǔn)值72。這時(shí)就將8位置的值置為86，j減1。

（3）此時(shí)的i=3，j=7，X=72。

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

（5）此時(shí)i=4，j=5，X=72。

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

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

4.2冒泡排序原理研究

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

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

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

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

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

5.1第一次優(yōu)化

在第四節(jié)中，本文已經(jīng)用Java代碼實(shí)現(xiàn)了冒泡排序的排序功能。但是可以看出原數(shù)組a中的后半部分已經(jīng)是排序狀態(tài)，其實(shí)不必要循環(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次。可以說減少了3/4的工作量，性能提升非常大。但是同時(shí)我們發(fā)現(xiàn)了另一個(gè)問題，雖然5.1節(jié)中的程序使循環(huán)次數(shù)減少了，但是每次的內(nèi)部循環(huán)次數(shù)依然沒有變化，每次循環(huán)還是要對比到最后一個(gè)數(shù)為止。

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

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

6總結(jié)

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

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

參考文獻(xiàn)：

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

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

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

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