奚科芳

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

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

中圖分類(lèi)號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 排序算法概述

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

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

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

2.1 冒泡排序

2.1.1 基本思想

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

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

//冒泡排序：10萬(wàn)個(gè)隨機(jī)數(shù)用時(shí)約25秒

public static voidbubblesort （int a[]）{

inti，j，temp；

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

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 基本思想

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

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

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

public static void insertsort（int[] arr） {

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

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

int j；

for（inti=1； i

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

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

//如果找到了比當(dāng)前數(shù)小的，退出//三種情況都確定了j+1為當(dāng)前數(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這個(gè)位置讓我排

arr[j+1] = temp；

}

}

2.3 選擇排序

2.3.1 基本思想

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

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

//選擇排序：10萬(wàn)隨機(jī)數(shù)據(jù)用時(shí)約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)部分有序。部分有序的含義是待排序列由若干個(gè)有序的子序列組成。歸并排序的基本思想是：將這些有序的子序列進(jìn)行合并，從而得到有序的序列。合并是一種常見(jiàn)運(yùn)算，其方法是：比較各子序列的第一個(gè)記錄的鍵值，最小的一個(gè)就是排序后序列的第一個(gè)記錄的鍵值。取出這個(gè)記錄，繼續(xù)比較各子序列現(xiàn)在的第一個(gè)記錄的鍵值，便可找出排序后的第二記錄。如此繼續(xù)下去，最終可以得到排序結(jié)果。因此，歸并排序的基礎(chǔ)是合并，如圖5所示。

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

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

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

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

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

//定義三個(gè)下標(biāo)分別指向a，b，arr

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

//比較，取值，直到其中一個(gè)數(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 性能對(duì)比

我們可以通過(guò)一些基本的性能標(biāo)準(zhǔn)對(duì)各個(gè)排序方法進(jìn)行總結(jié)對(duì)比，見(jiàn)表1。

3.2 影響排序效果的因素

上述介紹的4種排序方法，因?yàn)椴煌呐判蚍椒ㄟm應(yīng)不同的應(yīng)用環(huán)境和要求，所以選擇合適的排序方法應(yīng)綜合考慮下列因素：

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

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

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

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

⑤語(yǔ)言工具的條件；

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

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

3.3 排序方法的選擇

①若n較?。ㄈ鏽≤50），可采用插入排序或選擇排序。當(dāng)記錄規(guī)模較小時(shí)，插入排序較好；否則因?yàn)檫x擇排序移動(dòng)的記錄數(shù)少于插人排序，應(yīng)選選擇排序?yàn)橐恕?/p>

②若文件初始狀態(tài)基本有序（指正序），則應(yīng)選用插人排序、冒泡排序?yàn)橐耍?/p>

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

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

參考文獻(xiàn)

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

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

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