Java網(wǎng)絡(luò)程序設(shè)計(jì) 課件 單元3-06 排序算法

控制結(jié)構(gòu)、方法與數(shù)組應(yīng)用單元三if語(yǔ)句switch語(yǔ)句循環(huán)語(yǔ)句目錄CONTENTS123方法一維數(shù)組目錄CONTENTS45排序算法二維數(shù)組673.6排序算法所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減地排列起來(lái)的操作。排序的算法有很多，各種算法對(duì)空間的要求及時(shí)間效率也各有差別。其中插入排序和冒泡排序又被稱作簡(jiǎn)單排序，它們對(duì)空間的要求不髙，但時(shí)間效率不穩(wěn)定。而其他一些排序相對(duì)于簡(jiǎn)單排序來(lái)說(shuō)對(duì)空間的要求稍高一點(diǎn)，但時(shí)間效率卻能穩(wěn)定在很高的水平。從實(shí)際編程的角度看，很少需要自己編寫(xiě)算法實(shí)現(xiàn)排序，Java的一些工具類中提供了一些靜態(tài)方法可以實(shí)現(xiàn)排序的功能。3.6.1冒泡排序由于在排序過(guò)程中總是小數(shù)往前放，大數(shù)往后放，類似于小的氣泡往上升，所以稱作冒泡排序。通過(guò)上面的分析可以看出，假設(shè)需要排序的序列的個(gè)數(shù)是n，則需要經(jīng)過(guò)n-l輪，最終完成排序。在第一輪中，比較的次數(shù)是n-1次，之后每輪減少1次。冒泡排序就是依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。第一輪：先比較第1個(gè)和第2個(gè)數(shù)，將小數(shù)放前，大數(shù)放后；然后比較第2個(gè)數(shù)和第3個(gè)數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個(gè)數(shù)，將小數(shù)放前，大數(shù)放后；至此第一輪結(jié)束，將最大的數(shù)放到了最后。第二輪：仍從第一對(duì)數(shù)開(kāi)始比較，將小數(shù)放前，大數(shù)放后，一直比較到倒數(shù)第二個(gè)數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的數(shù)），第二輪結(jié)束，在倒數(shù)第二的位置上得到一個(gè)新的最大數(shù)（其實(shí)在整個(gè)數(shù)列中是第二大的數(shù)）。3.6.1冒泡排序用Java語(yǔ)言實(shí)現(xiàn)冒泡排序，可以用雙重for循環(huán)實(shí)現(xiàn)，其核心代碼如下。staticvoidbubbleSort(int[]a){//引用傳遞inttemp;//數(shù)組的長(zhǎng)度可以通過(guò)“數(shù)組名.length”獲得for(inti=0;i<a.length-1;i++){//需要比較n-1輪for(intj=0;j<a.length-i-1;j++){//根據(jù)a.length-i-1，每輪需要比較的次數(shù)逐輪減少1次if(a[j]>a[j+l]){ //相鄰數(shù)進(jìn)行比較，符合條件進(jìn)行替換temp=a[j];a[j]=a[j+1];a[j+l]=temp;}}}}3.6.2插入排序插入排序包括直接插入排序、二分插入排序、鏈表插入排序和希爾排序。接下來(lái)介紹最簡(jiǎn)單的直接插入排序。直接插入排序存在兩個(gè)表，一個(gè)是有序表，另一個(gè)是無(wú)序表。每次從無(wú)序表中取出第一個(gè)元素，把它插入到有序表的合適位置，使有序表仍然有序。第一輪：比較無(wú)序表中前兩個(gè)數(shù)，然后按順序插入到有序表中，剩下的數(shù)仍在無(wú)序表中。第二輪：把無(wú)序表中剩下的第一個(gè)數(shù)與有序表的兩個(gè)數(shù)進(jìn)行比較，然后把這個(gè)數(shù)插入到合適位置。按此規(guī)律操作，直至無(wú)序表中的數(shù)全部插入到有序表，完成排序。3.6.2插入排序用Java語(yǔ)言實(shí)現(xiàn)直接插入排序的核心代碼如下。staticvoidinsertSort(int[]a){//引用傳遞for(inti=1;i<a.length;i++){intj=-1;while(j<=i&&a[i]>a[++j]);//找到a[i]應(yīng)該擺放的位置if(j<i){//將j之后的數(shù)據(jù)移動(dòng)一位，然后把a(bǔ)[i]移動(dòng)到j(luò)處inttemp=a[i];for(intk=i-1;k>=j;k--){a[k+1]=a[k];}a[j]=temp;}