淺談常見排序算法實現原理及性能優化

◆

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

1行業背景

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

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

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

2 Java語言介紹

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

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

3常用排序算法簡介

3.1冒泡排序

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

3.2快速排序

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

3.3插入排序

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

3.4選擇排序

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

4排序算法原理剖析

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

4.1快速排序原理研究

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

快速排序的基本思想是：

1.先從數列中取出一個數作為基準數。

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

3.再對左右區間重復第二步，直到各區間只有一個數。

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

首先定義變量：i，j，X，其中i是指向數組起始位置的游標值，j是指向數組末尾的游標值。X為基準數。

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

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

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

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

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

(6)繼續從i開始找比基準值大的數，當i加1等于j時，此次排序結束。數組為：

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

4.2冒泡排序原理研究

冒泡排序非常容易理解，設數組長度為n。

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

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

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

5冒泡排序算法性能優化

5.1第一次優化

在第四節中，本文已經用Java代碼實現了冒泡排序的排序功能。但是可以看出原數組a中的后半部分已經是排序狀態，其實不必要循環20次，可能在某次排序后數組已經是有序狀態了。所以就要考慮進行性能優化。

我們可以試想，如果某次排序中沒有交換元素位置的事件發生，那么就可以認為是該數組已經排序成功了，就不需要在進行排序。我們對冒泡排序進行了如下優化：

可以看出效果很明顯，在循環了5次后，就已經是有序數組了，程序便停止排序工作。

5.2第二次優化

在5.1節中對冒牌排序做了部分優化，使得排序的循環次數從20次減少到了5次。可以說減少了3/4的工作量，性能提升非常大。但是同時我們發現了另一個問題，雖然5.1節中的程序使循環次數減少了，但是每次的內部循環次數依然沒有變化，每次循環還是要對比到最后一個數為止。

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

可以看出，與上次優化一樣，程序只循環了5次就結束了排序工作，但是相比于第一次循環，后幾次循環的內部循環數驟減，又一次提升了排序的性能。

6總結

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

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

參考文獻：

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

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

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

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