第10章、资料排序

《第10章、资料排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章、資料排序朝陽科技大學王淑卿1大綱氣泡浮昇排序法(BubbleSort)選擇排序法(SelectionSort)插入排序法(InsertionSort)謝耳排序法(ShellSort)快速排序法(QuickSort)累堆排序法(HeapSort)合併排序法(MergeSort)基數排序法(RadixSort)或稱為筒子排序法(BucketSort)樹排序法(TreeSort)2排序的基本觀念檔案(File)記錄(Row或Record)欄位(Column或Field)鍵值(KeyValue)3氣泡浮昇排序法(BubbleSort)將N筆記錄(編號0至N-1)

2、按鍵值不遞減次序排序的氣泡浮昇排序法1.重複步驟2N-1回合，直到其中有一回合沒有「交換」情形發生為止2.比較陣列中相鄰兩元素之鍵值，若前面元素大於後面元素，則立刻將兩元素值交換4氣泡浮昇排序法(BubbleSort)氣泡浮昇排序法之每一回合結果氣泡浮昇排序法之每一回合結果先定下來的為最大值5氣泡浮昇排序法(BubbleSort)publicclassBubbleSort{//ClassNameandFileName:BubbleSortpublicstaticvoidmain(Stringargs[]){shortsource[]={48,11,9,78,9,2

3、0};//sourceshortexchange=0;for(shortpass=1;passsource[i+1]){exchange=source[i];//swapsource[i]=source[i+1];source[i+1]=exchange;}//ifend}//forend}//forendfor(shorti=0;i

4、]+"");//showresultonscreen}}//mainmethodend}//classend6選擇排序法(SelectionSort)將N筆記錄(編號1至N)按鍵值不遞減次序排序的選擇排序法為：1.重複步驟2N-1回合2.找出第i個至第N個鍵值中的最小者，並將之與第i個鍵值交換。其中i等於回合數。選擇排序法的每一回合結果先定下來的為最小值7選擇排序法(SelectionSort)publicclassArrays{publicstaticvoidselectionSort(int[]arr){intsmallIndex,tmp;intpass,n=

5、arr.length;//passhastherange0ton-2for(pass=0;pass<=n-2;pass++){smallIndex=pass;for(inti=pass;i<=n-1;i++){if(arr[i]<=arr[pass])smallIndex=i;}}if(smallIndex!=pass){tmp=arr[pass];arr[pass]=arr[smallIndex];arr[smallIndex]=tmp;}}}publicstaticvoidmain(Stringargs[]){//declareanintegerarrayin

6、t[]arr={87,38,77,38,25,21,1};Arrays.selectionSort(arr);System.out.print("Sorted:");for(inti=0;i<="">System.out.print(arr[i]+"");}}8插入排序法(InsertionSort)將N筆記錄(編號1至N)依鍵值不遞減之次序排序的插入排序法為：1.從第2個鍵值至第N個鍵值，分別執行步驟22.將該鍵值插入到其前面所有鍵值當中第一個大於本身的鍵值之前，若沒有大於本身者，則保持原狀並繼續下一回合插入排序法每一回合排序前，已排序/未排序鍵值分佈9插入排序

7、法(InsertionSort)插入排序法的每一回合結果10插入排序法(InsertionSort)輸入：整數陣列data，長度為n輸出：排序陣列data，若itarget)&&(j>0))5{a[j]=a[j-1];6j--;7}8a[j]=target;9}挑定一個target，向前比較11謝耳排序法(ShellSort)將N筆記錄(編號0至N-1)按鍵值不遞減之順序排列之謝耳排序法為：1.

8、選擇一適當