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

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