JAVA語言的常見排序算法

本文格式為Word版，下載可任意編輯——JAVA語言的常見排序算法JAVA語言的常見排序算法

導(dǎo)語：每種排序算法都有它自己的優(yōu)點(diǎn)及局限性，適用于不同的要求范圍，在選擇時(shí)應(yīng)根據(jù)需要適選中用，甚至可將多種算法結(jié)合起來使用，效率才會(huì)更高。下面就由我為大家介紹一下JAVA語言的常見排序算法，接待大家閱讀!

1排序算法概述

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

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

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

2.1冒泡排序

2.1.1根本思想

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

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

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

publicstaticvoidbubblesortinta[]

inti，j，temp;

intn=a。length;//獲得數(shù)組長度

fori=1;i=n;i++//外層循環(huán)操縱對比趟數(shù)

forj=0;jifa[j]a[j+1]//假設(shè)相鄰兩數(shù)前者比后者大，那交換

temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

2.2插入排序

2.2.1根本思想

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

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

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

publicstaticvoidsortint[]arr

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

//外層循環(huán)確定輪次：從其次個(gè)到結(jié)果一個(gè)，n-1輪

intj;

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

forj=i-1;j=0;j--

//假設(shè)找到了比當(dāng)前數(shù)小的，退出//三種處境都確定了j+1為當(dāng)前數(shù)理應(yīng)排的位置

ifarr[j]break;

//再交換排序

inttemp=arr[i];

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

forintk=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)到只剩下結(jié)果一個(gè)數(shù)據(jù)元素為止。它的對比次數(shù)是確定的：nn-1/2。因此無論何種序列，正序和反序數(shù)據(jù)耗時(shí)相差不多，相差的只是數(shù)據(jù)移動(dòng)時(shí)間，對數(shù)據(jù)的有序性不敏感。它雖然對比次數(shù)多，但它的數(shù)據(jù)交換量卻很少。如圖4所示。

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

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

publicstaticvoidselectsortint[]arr

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

intmin;

intindex;

forinti=0;i//內(nèi)層循環(huán)確定對比和交換范圍

min=arr[i];

index=i;

forintj=i+1;j//對比和交換

ifminarr[j]

min=arr[j];

index=j;

ifi!=index

inttemp=arr[i];

arr[i]=arr[index];

arr[index]=temp;

2.4歸并排序

2.4.1根本思想

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

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

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

publicstaticvoidmergeint[]arr，intfrom，intmid，intend，int[]temp

//調(diào)配大數(shù)組空間

//int[]arr=newint[a。length+b。length];

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

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

//對比，取值，直到其中一個(gè)數(shù)組終止

whilei=midj=end

ifarr[i]temp[k++]=arr[i++];

else

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

whilei=mid

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

whilej=end

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

forintindex=from;index=end;index++

arr[index]=temp[index];

publicstaticvoidsortint[]arr，intfrom，intto，int[]temp

iffromto

intmid=from+to/2;

//遞歸

sortarr，from，mid，temp;

sortarr，mid+1，to，temp;

//合并

mergearr，from，mid，to，temp;

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

3.1性能比較

我們可以通過一些根本的性能標(biāo)準(zhǔn)對各個(gè)排序方法舉行總結(jié)比較，見表1。

3.2影響排序效果的因素

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

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

②記錄的大小規(guī)模;

③關(guān)鍵字的布局及其初始狀態(tài);

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

⑤語言工具的條件;

⑥存布局;

⑦時(shí)間和輔佐