數據結構實驗五-查找與排序的實現

1、.實 驗 報 告課程名稱 數據結構 實驗名稱 查找與排序的實現 系別 專業(yè)班級 指導教師11 學號 姓名 實驗日期 實驗成績 一、實驗目的(1) 掌握交換排序算法（冒泡排序）的基本思想；(2) 掌握交換排序算法（冒泡排序）的實現方法；(3) 掌握折半查找算法的基本思想；(4) 掌握折半查找算法的實現方法；二、實驗內容1. 對同一組數據分別進行冒泡排序，輸出排序結果。要求：1) 設計三種輸入數據序列：正序、反序、無序2) 修改程序：a) 將序列采用手工輸入的方式輸入b) 增加記錄比較次數、移動次數的變量并輸出其值，分析三種序列狀態(tài)的算法時間復雜性2. 對給定的有序查找集合，通過折半查找與給定值k

2、相等的元素。3. 在冒泡算法中若設置一個變量lastExchangeIndex來標記每趟排序時經過交換的最后位置，算法如何改進？三、設計與編碼1.本實驗用到的理論知識2.算法設計3.編碼package sort_search;import java.util.Scanner;public class Sort_Search /冒泡排序算法public void BubbleSort(int r) int temp;int count=0,move=0;boolean flag=true;for(int i=1;ir.length&flag;i+)flag=false;count+;for(in

3、t j=0;jrj+1)temp=rj;rj=rj+1;rj+1=temp;move+;flag=true;System.out.println(排序后的數組為：);for(int i=0;ir.length;i+)System.out.print(ri+ );System.out.println();System.out.println(比較次數為：+count);System.out.println(移動次數為：+move);public static int BinarySearch(int r,int key) /折半查找算法int low=0,high=r.length-1;whil

4、e(lowkey)high=mid-1;elselow=mid+1;return -1; /測試public static void main(String args) Sort_Search ss=new Sort_Search();int t=new int13;System.out.println(依次輸入13個整數為：);Scanner sc=new Scanner(System.in);for(int i=0;it.length;i+)ti=sc.nextInt();System.out.println(排序前的數組為： );for(int i=0;i0)System.out.pri

5、ntln(k+ 在數組中的位置是第： + BinarySearch(t,k);elseSystem.out.println(k+ 在數組中查找不到！); 四、運行與調試1. 在調試程序的過程中遇到什么問題，是如何解決的？問題：在計算比較次數和移動次數時，計算數據明顯出錯。原因：在進行移動和比較的過程中，沒有更新標志，導致計數出錯。解決辦法：在比較和移動的過程中，有進行比較和移動的操作時，更新標志。然后按標志計數。2. 設計了哪些測試數據？預計結果是什么？說明： 測試了int類型數據： 241 17 23 45 37 4 31 43 11 89 33 101 177 預計排序后結果為：4 11 17 23 31 33 37 43 45 89 101 177 241 比較次數： 無序：8次 正序：1次 反序：12次 移動次數： 無序：30次 正序：0次 反序：78次 查找數33的位置為：5 查找數101的位置為：10 查找數100的結果為：查找不到3. 程序運行的結果如何 I.無序輸入：II.正序輸入：III.反序輸入： 五、總結與心得六、思考題已知奇偶轉換排序如下：第一趟對所有奇數的i，將ai和ai+1進行比較，第二趟對所有偶數的i,將ai和ai+1進行比較,每次比較時若ai