基于JAVA語言的常見排序算法分析與比較

奚科芳

摘 要：該文主要闡述了冒泡排序、插入排序、選擇排序、歸并排序這4種排序算法的基本思想、JAVA實現(xiàn)代碼，通過分析對比得到各種算法的最佳使用場景，從而提高排序的效率。

關(guān)鍵詞：排序算法 基本思想 性能比較

中圖分類號：TP312 文獻標識碼：A 文章編號：1674-098X（2016）09（c）-0097-03

Analysis and Comparison of Common Sorting Algorithms Based on JAVA Language

Xi Kefang

（Jinken College of Technology，Nanjing，Jiangsu，210000，China）

Abstract：This articlemainly expounds the bubble sort， insertion sort， selection sort， merge sort， the basic idea of the four kinds of sorting algorithm Java implementation code，we would get the best use of the scene and improve the efficiency of the sortthrough the analysis and comparison of various algorithms.

Key Words：Sorting algorithm；Basic idea；Performance comparison

1 排序算法概述

所謂計算機中的排序，就是使一串記錄，按照其中的某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。而排序算法則是一種能將一串數(shù)據(jù)依照特定的方式進行排序的一種算法。

根據(jù)排序過程中涉及的存儲器不同，可以將排序方法分為兩大類： 一類是內(nèi)部排序，指的是待排序地記錄存放在計算機隨機存儲器中進行的排序過程。另一類是外部排序，指的是需要對外存儲器進行訪問的排序過程。該課題主要研究幾類常見的內(nèi)部排序，有冒泡排序、插入排序、選擇排序、歸并排序。

2 常見排序算法基本思想和JAVA代碼實現(xiàn)

2.1 冒泡排序

2.1.1 基本思想

冒泡排序是將相鄰的兩個記錄按關(guān)鍵值兩兩比較，如果記錄的次序相反時即進行交換，直到序列中不存在反序的記錄為止。如有n個無序數(shù)，第一趟將第一個和第二個進行比較，將大的放在第二個位置，再將第二個和第三比較，大的放在第三個位置，依次向后比較，比較n-1次，將最大的放在最后（n的位置）；第二趟，再從第一個開始比較，比較n-2次，這次把最大的放到第n-1個位置，然后再來回比較。遵循第i次遍歷就從第一個數(shù)開始比較n-i次，將最后的值放在第n-i+1的位置。如圖1、圖2所示。

2.1.2 JAVA語言實現(xiàn)冒泡排序核心代碼

//冒泡排序：10萬個隨機數(shù)用時約25秒

public static voidbubblesort （int a[]）{

inti，j，temp；

int n=a。length； //獲得數(shù)組長度

for（i=1；i<=n；i++）{ //外層循環(huán)控制比較趟數(shù)

for（ j=0；j

if（a[j]>a[j+1]）{//如果相鄰兩數(shù)前者比后者大，那交換

temp=a[j]；

a[j]=a[j+1]；

a[j+1]=temp；

}

}

}

}

2.2 插入排序

2.2.1 基本思想

插入排序是一種簡單的排序方法，它的基本排序思想是依次將待排序的記錄逐一地按其關(guān)鍵字值的大小插入到一個已排好序的有序序列中，得到一個新的有序序列，直到所有的記錄插完為止，從而實現(xiàn)排序。在有序情況下只需要經(jīng)過n-1次比較，在最壞情況下，將需要n（n-1）/2次比較，如圖3所示。

2.2.2 JAVA語言實現(xiàn)插入排序核心代碼

//插入排序：10萬隨機數(shù)據(jù)用時約7秒

public static void insertsort（int[] arr） {

//插入排序：從小到大，從前往后，先找位置后排序

//外層循環(huán)確定輪次：從第二個到最后一個，n-1輪

int j；

for（inti=1； i

//內(nèi)存循環(huán)先找位置：從后（i-1）前找，最多找到0

for（j=i-1； j>=0； j--） {

//如果找到了比當前數(shù)小的，退出//三種情況都確定了j+1為當前數(shù)應(yīng)該排的位置

if（arr[j]

break；

}

}

//再交換排序

int temp = arr[i]；

//從[j+1，i-1]通通往后退一格

for（int k=i-1；k>=j+1；k--） {

arr[k+1] = arr[k]；

}//j+1這個位置讓我排

arr[j+1] = temp；

}

}

2.3 選擇排序

2.3.1 基本思想

選擇排序是在待排序的一組數(shù)據(jù)元素中，選出最小的一個數(shù)據(jù)元素與第一個位置的數(shù)據(jù)元素交換；然后在剩下的數(shù)據(jù)元素當中再找最小的與第二個位置的數(shù)據(jù)元素交換，循環(huán)到只剩下最后一個數(shù)據(jù)元素為止。它的比較次數(shù)是一定的：n（n-1）/2。因此無論何種序列，正序和反序數(shù)據(jù)耗時相差不多，相差的只是數(shù)據(jù)移動時間，對數(shù)據(jù)的有序性不敏感。它雖然比較次數(shù)多，但它的數(shù)據(jù)交換量卻很少。如圖4所示。

2.3.2 JAVA語言實現(xiàn)選擇排序核心代碼

//選擇排序：10萬隨機數(shù)據(jù)用時約8秒

public static void selectsort（int[] arr） {

//外層循環(huán)確定輪次（n-1）

int min；

int index；

for（inti=0； i

//內(nèi)層循環(huán)確定比較和交換范圍

min = arr[i]；

index = i；

for（int j=i+1；j

//比較和交換

if（min >arr[j]） {

min = arr[j]；

index = j；

}

}

if（i ！= index） {

int temp = arr[i]；

arr[i] = arr[index]；

arr[index] = temp；

}

}

}

2.4 歸并排序

2.4.1 基本思想

歸并排序要求待排序列已經(jīng)部分有序。部分有序的含義是待排序列由若干個有序的子序列組成。歸并排序的基本思想是：將這些有序的子序列進行合并，從而得到有序的序列。合并是一種常見運算，其方法是：比較各子序列的第一個記錄的鍵值，最小的一個就是排序后序列的第一個記錄的鍵值。取出這個記錄，繼續(xù)比較各子序列現(xiàn)在的第一個記錄的鍵值，便可找出排序后的第二記錄。如此繼續(xù)下去，最終可以得到排序結(jié)果。因此，歸并排序的基礎(chǔ)是合并，如圖5所示。

2.4.2 JAVA 語言實現(xiàn)歸并排序核心代碼

//歸并排序：10萬隨機數(shù)據(jù)用時約15毫秒

public static void merge（int[] arr，int from，int mid，int end，int[] temp） {

//分配大數(shù)組空間

//int[] arr = new int[a。length+b。length]；

//定義三個下標分別指向a，b，arr

inti=from，j=mid+1，k=from；

//比較，取值，直到其中一個數(shù)組結(jié)束

while（i<=mid && j<=end） {

if（arr[i]

temp[k++] = arr[i++]；

}else {

temp[k++] = arr[j++]；

}

}

while（i<=mid） {

temp[k++] = arr[i++]；

}

while（j<=end） {

temp[k++] = arr[j++]；

}

for（int index=from；index<=end；index++） {

arr[index] = temp[index]；

}

}

public static void sort（int[] arr，int from，int to，int[] temp） {

if（from < to） {

int mid = （from+to）/2；

//遞歸

sort（arr，from，mid，temp）；

sort（arr，mid+1，to，temp）；

//合并

merge（arr，from，mid，to，temp）；

}

}

3 排序方法的性能比較及選擇

3.1 性能對比

我們可以通過一些基本的性能標準對各個排序方法進行總結(jié)對比，見表1。

3.2 影響排序效果的因素

上述介紹的4種排序方法，因為不同的排序方法適應(yīng)不同的應(yīng)用環(huán)境和要求，所以選擇合適的排序方法應(yīng)綜合考慮下列因素：

①待排序的記錄數(shù)目n；

②記錄的大?。ㄒ?guī)模）；

③關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)；

④對穩(wěn)定性的要求；

⑤語言工具的條件；

⑥存儲結(jié)構(gòu)；

⑦時間和輔助空間復(fù)雜度等。

3.3 排序方法的選擇

①若n較?。ㄈ鏽≤50），可采用插入排序或選擇排序。當記錄規(guī)模較小時，插入排序較好；否則因為選擇排序移動的記錄數(shù)少于插人排序，應(yīng)選選擇排序為宜。

②若文件初始狀態(tài)基本有序（指正序），則應(yīng)選用插人排序、冒泡排序為宜；

②若n較大，則應(yīng)采用時間復(fù)雜度為O（nlgn）的排序方法：歸并排序。

綜上所述，在上述排序算法中，不能絕對地說哪個算法是最好的。每種排序算法都有它自己的優(yōu)點及局限性，適用于不同的要求范圍，在選擇時應(yīng)根據(jù)需要適當選用，甚至可將多種算法結(jié)合起來使用，效率才會更高。

參考文獻

[1] 謝婷.基于C語言的常用排序算法比較[J].湖南城學(xué)院學(xué)報：自然科技版，2016，25（4）：95-96.

[2] 趙雅青，徐燕.數(shù)值排序算法比較分析[J].電腦編程技術(shù)與維護，2015（23）：5-7.

[3] 李梅云.一些常見數(shù)據(jù)排序算法的比較[J].漳州職業(yè)技術(shù)學(xué)院學(xué)報，2009（7）：60-62.