JAVA語(yǔ)言的常見排序算法
導(dǎo)語(yǔ)：每種排序算法都有它自己的優(yōu)點(diǎn)及局限性，適用于不同的要求范圍，在選擇時(shí)應(yīng)根據(jù)需要適當(dāng)選用，甚至可將多種算法結(jié)合起來(lái)使用，效率才會(huì)更高。下面就由小編為大家介紹一下JAVA語(yǔ)言的常見排序算法，歡迎大家閱讀!
1 排序算法概述
計(jì)算機(jī)中的排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來(lái)的操作。而排序算法則是一種能將一串?dāng)?shù)據(jù)依照特定的方式進(jìn)行排序的一種算法。
根據(jù)排序過(guò)程中涉及的存儲(chǔ)器不同，可以將排序方法分為兩大類： 一類是內(nèi)部排序，指的是待排序地記錄存放在計(jì)算機(jī)隨機(jī)存儲(chǔ)器中進(jìn)行的排序過(guò)程。另一類是外部排序，指的是需要對(duì)外存儲(chǔ)器進(jìn)行訪問的排序過(guò)程。該課題主要研究幾類常見的內(nèi)部排序，有冒泡排序、插入排序、選擇排序、歸并排序。
2 常見排序算法基本思想和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è)開始比較，比較n-2次，這次把最大的放到第n-1個(gè)位置，然后再來(lái)回比較。遵循第i次遍歷就從第一個(gè)數(shù)開始比較n-i次，將最后的值放在第n-i+1的位置。如圖1、圖2所示。
2.1.2 JAVA語(yǔ)言實(shí)現(xiàn)冒泡排序核心代碼
/pic/p>
public static voidbubblesort (int a[]){
inti，j，temp;
int n=a。length; /pic/p>
for(i=1;i<=n;i++){ /pic/p>
for( j=0;j if(a[j]>a[j+1]){/pic/p>
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)插入排序核心代碼
/pic/p>
public static void sort(int[] arr) {
/pic/p>
/pic/p>
int j;
for(inti=1; i /pic/p>
for(j=i-1; j>=0; j--) {
/pic/pic/p>
if(arr[j] break;
}
}
/pic/p>
int temp = arr[i];
/pic/p>
for(int k=i-1;k>=j+1;k--) {
arr[k+1] = arr[k];
}/pic/p>
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)選擇排序核心代碼
/pic/p>
public static void selectsort(int[] arr) {
/pic/p>
int min;
int index;
for(inti=0; i /pic/p>
min = arr[i];
index = i;
for(int j=i+1;j /pic/p>
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)行合并，從而得到有序的序列。合并是一種常見運(yùn)算，其方法是：比較各子序列的第一個(gè)記錄的鍵值，最小的一個(gè)就是排序后序列的第一個(gè)記錄的鍵值。取出這個(gè)記錄，繼續(xù)比較各子序列現(xiàn)在的第一個(gè)記錄的鍵值，便可找出排序后的第二記錄。如此繼續(xù)下去，最終可以得到排序結(jié)果。因此，歸并排序的基礎(chǔ)是合并，如圖5所示。
2.4.2 JAVA 語(yǔ)言實(shí)現(xiàn)歸并排序核心代碼
/pic/p>
public static void merge(int[] arr，int from，int mid，int end，int[] temp) {
/pic/p>
/pic/p>
/pic/p>
inti=from，j=mid+1，k=from;
/pic/p>
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;
/pic/p>
sort(arr，from，mid，temp);
sort(arr，mid+1，to，temp);
/pic/p>
merge(arr，from，mid，to，temp);
}
}
3 排序方法的性能比較及選擇
3.1 性能對(duì)比
我們可以通過(guò)一些基本的性能標(biāo)準(zhǔn)對(duì)各個(gè)排序方法進(jìn)行總結(jié)對(duì)比，見表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ǔ)言工具的條件;
�、薮娼Y(jié)構(gòu);
⑦時(shí)間和輔助空間復(fù)雜度等。
3.3 排序方法的選擇
�、偃鬾較小(如n≤50)，可采用插入排序或選擇排序。當(dāng)記錄規(guī)模較小時(shí)，插入排序較好;否則因?yàn)檫x擇排序移動(dòng)的記錄數(shù)少于插人排序，應(yīng)選選擇排序?yàn)橐恕?/p>
�、谌粑募跏紶顟B(tài)基本有序(指正序)，則應(yīng)選用插人排序、冒泡排序?yàn)橐?
②若n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlgn)的排序方法：歸并排序。
【JAVA語(yǔ)言的常見排序算法】相關(guān)文章：
java常見的排序算法的代碼10-23
Java排序算法03-05
常用Java排序算法詳解10-07
c語(yǔ)言的排序算法01-15
java的常見排序方法03-17
java堆排序的算法思想的分析10-07
6種常見的排序算法的C語(yǔ)言實(shí)現(xiàn)10-25
C語(yǔ)言奇偶排序算法02-15
c語(yǔ)言排序的幾種算法12-04