數(shù)據(jù)結構Java版第3章排序

1、數(shù)據(jù)結構（數(shù)據(jù)結構（Java版）版）葉核亞葉核亞數(shù)據(jù)結構（數(shù)據(jù)結構（Java版）版） 第1章 緒論 第2章 線性表第3章 排序 第4章 棧與隊列 第5章 數(shù)組和廣義表 第6章 樹和二叉樹 第7章 查找 第8章 圖 第9章 綜合應用設計第3章 排序 3.1 排序的基本概念 3.2 插入排序 3.3 交換排序 3.4 選擇排序 3.5 歸并排序數(shù)據(jù)結構（Java版）葉核亞3.1 排序的基本概念1數(shù)據(jù)序列數(shù)據(jù)序列（datalist）是待排序的數(shù)據(jù)元素的有限集合。2關鍵字通常數(shù)據(jù)元素由多個數(shù)據(jù)項組成，以其中某個數(shù)據(jù)項作為排序依據(jù)，則該數(shù)據(jù)項稱為關鍵字（key）。 3排序算法的穩(wěn)定性在數(shù)據(jù)序列中，如果有

2、兩個數(shù)據(jù)元素ri和rj，它們的關鍵字ki等于kj，且在未排序時，ri位于rj之前。如果排序后，元素ri仍在rj之前，則稱這樣的排序算法是穩(wěn)定的（stable），否則是不穩(wěn)定的排序算法。數(shù)據(jù)結構（Java版）葉核亞4內排序與外排序n內排序：在待排序的數(shù)據(jù)序列中，數(shù)據(jù)元素個數(shù)較少，整個排序過程中所有的數(shù)據(jù)元素都可以保留在內存，則這樣的排序稱為內排序。n外排序：待排序的數(shù)據(jù)元素非常多，以至于它們必須存儲在磁盤等外部存儲介質上，則這樣的排序稱為外排序。顯然，外排序過程中需要多次訪問外存。5排序算法的性能評價n排序算法的時間復雜度：指算法執(zhí)行中的數(shù)據(jù)比較次數(shù)、數(shù)據(jù)移動次數(shù)與待排序數(shù)據(jù)序列的元素個數(shù)n之間

3、的關系。n排序算法的空間復雜度：指算法執(zhí)行中，除待排序數(shù)據(jù)序列本身所占用的內存空間外，需要的附加內存空間與待排序數(shù)據(jù)序列的元素個數(shù)n之間的關系。數(shù)據(jù)結構（Java版）葉核亞3.2 插入排序n插入排序（insertion sort）的基本思想是：每趟將一個待排序的數(shù)據(jù)元素，按其關鍵字大小，插入到已排序的數(shù)據(jù)序列中，使得插入后的數(shù)據(jù)序列仍是已排序的，直到全部元素插入完畢。n3.2.1 直接插入排序n3.2.2 希爾排序數(shù)據(jù)結構（Java版）葉核亞3.2.1 直接插入排序1直接插入排序算法2順序存儲結構線性表的直接插入排序518765432table(a) k=5，i=1，插入535(b) k=3，

4、在子序列5中查找，i=1，5向后移動,插入3253(c) k=2，在3，5中查找，i=1，3,5向后移動,插入227543(e) k=7,在2，3，4，5中查找，i=5，插入7(f) k=1，在2，3，4，5，7中查找，i=1，2,3,4,5,7向后移動,插入11754322543(d) k=4，在2，3，5中查找，i=3，5向后移動,插入4序號iiiiii1234521圖3.1 直接插入排序算法描述數(shù)據(jù)結構（Java版）葉核亞【例3.1】 順序表的直接插入排序的算法實現(xiàn)與測試。import ds_java.LinearList1; /順序存儲結構的線性表類public class Inser

5、tSort1 extends LinearList1 /直接插入排序 public InsertSort1(int table) /將table數(shù)組元素依次插入已排序順序表 super(table.length); for(int i=0;i=i;j-)數(shù)據(jù)結構（Java版）葉核亞3算法分析n直接插入排序的平均比較次數(shù)為 n平均移動次數(shù)為n直接插入排序的時間復雜度為O(n2)。n直接插入排序算法是穩(wěn)定的。ninnniC12241434121平均ninnniM1244) 1(2平均數(shù)據(jù)結構（Java版）葉核亞4鏈表的直接插入排序pprior data next 1headq2 3 (a) 空表插

6、入(c) 中間插入(b) 頭插入q 3 3 head 1qheadrearheadrear 1headq2 3 (d) 尾插入rearrear 4 圖3.2 雙向鏈表的插入排序算法描述數(shù)據(jù)結構（Java版）葉核亞【例3.2】 雙向鏈表的直接插入排序import ds_java.TwolinkNode; /雙向鏈表的結點類import ds_java.Twolink1; /雙向鏈表類public class Twolink2 extends Twolink1 /雙向鏈表插入排序 protected TwolinkNode rear; /引用鏈表最后一個結點 Twolink2() /建立空鏈表 s

7、uper(); /head=null rear=null; Twolink2(int n) /n個隨機值插入雙向鏈表 int i=0,k; System.out.print(insert: ); for(i=0;ithis.get(j+jump)時，表示該元素this.get(j)已在這趟排序后的位置，不需交換，則退出最內層循環(huán)。數(shù)據(jù)結構（Java版）葉核亞希爾排序算法 public void shellsort()/對順序表對象進行希爾排序/數(shù)據(jù)元素已存儲在table數(shù)組中 int i,j,jump,n=this.length(); jump=n/2; while(jump0) /控制增量

8、for(i=jump;i0) if(this.get(j)this.get(j+jump) /與相隔jump的元素比較、交換 swap(j,j+jump); /反序時，交換 j=j-jump;/繼續(xù)與前面的元素比較 數(shù)據(jù)結構（Java版）葉核亞3.3 交換排序n3.3.1 冒泡排序n3.3.2 快速排序數(shù)據(jù)結構（Java版）葉核亞3.3.1 冒泡排序1冒泡排序算法public void bubblesort() int i,j,n=this.length(); for(i=1;in;i+) /n-1趟排序 for(j=1;jthis.get(j+1) this.swap(j,j+1); /反序

9、時，交換 System.out.print(第+i+趟 ); this.output(); 2算法分析 時間復雜度為O(n2)，空間復雜度為O(1) 。數(shù)據(jù)結構（Java版）葉核亞3改進的冒泡排序 public void bubblesort() int i=1,j,n=this.length(),index=1; boolean exchange=true; /是否交換的標記 while(in & exchange) /最多n-1趟排序 System.out.print(第+i+趟 index=+index+ n-i=+(n-i)+ ); exchange=false; /假定元素未

10、交換 j=index; /起始比較位置 while(j=n-i) /一輪比較、交換 System.out.print(this.get(j)+this.get(j+1) this.swap(j,j+1); /反序時，交換數(shù)據(jù)結構（Java版）葉核亞改進的冒泡排序算法描述1567843218765432table(a) 第1趟，i=1,從index到n-i+1的相鄰位置元素比較、交換交換index交換交換18567432(b) 第2趟，i=2,從index到n-i+1的相鄰位置元素比較、交換交換index交換n-i+1n-i+118756432(c) 第3趟，i=3，比較、交換交換indexn-

11、i+118765432(d) 第3趟，i=4，比較,沒有交換，已排序indexn-i+1序號數(shù)據(jù)結構（Java版）葉核亞3.3.2 快速排序圖3.6 快速排序算法描述5713842618765432table(a) vot=5，tablejvot，不移動，j- i j17685423(i) i+，j-，分成兩個子序列（left,j）與(i,right)ijrightleft57138426(b) vot=5，tablejvot，將tablei值賦給tablej，j-ijrightleft17638426(d) vot=5，tablejvot，將tablej值賦給tablei，i+ij17638

12、423(e) vot=5，tableivot，i+ij17638423(f) vot=5，tableivot，將tablei值賦給tablej，j-17688423(h) i=j，將vot值賦給tableiij序號圖3.6 快速排序算法描述數(shù)據(jù)結構（Java版）葉核亞1快速排序算法 public void quicksort(int left,int right) /實現(xiàn)一趟快速排序 int i,j,n,vot; if(leftright) /左邊界小于右邊界，序列有效 i=left; j=right; vot=this.get(i); /第一個值作為基準值 while(i!=j) /進行一輪

13、比較 while(votthis.get(j) & ij) j-; /從右向左尋找較小值 if(ij) this.set(i,this.get(j); /較小值元素向左移動數(shù)據(jù)結構（Java版）葉核亞2算法分析n快速排序的平均比較次數(shù)為O(nlog2n)，時間復雜度為O(nlog2n)。n由于快速排序是遞歸算法，系統(tǒng)調用時需要設立一個棧（stack）存放參數(shù)，最大遞歸調用層次數(shù)為。因此，算法的空間復雜度為O(nlog2n)。數(shù)據(jù)結構（Java版）葉核亞3.4 選擇排序1順序表的直接選擇排序算法 public void selectsort() int i,j,min,k,n = thi

14、s.length(); for(i=1;in;i+) /n-1趟排序 min=i; /記下本趟最小值位置 for(j=i+1;j=n;j+) /一輪比較、交換 if(get(j)get(min) min=j; /記下新的最小值位置 if(min!=i) swap(i,min); /本趟最小值交換到左邊 System.out.print(min=+min+ ); this.output(); 數(shù)據(jù)結構（Java版）葉核亞3單向鏈表的直接選擇排序 3 1head 4 minprior 2(b) 將min結點添加到已排序的單向鏈表之后 1 (a) 選擇值最小的結點(由min指向),將min結點刪除s

15、ortedheadmin 3head 4 minprior=null 2(d) 將min結點添加到已排序的單向鏈表之后 1 2 (c) 選擇值最小的結點(由min指向),將min結點刪除minheadsortedrearsortedrearsortedrearsortedrearminmin圖3.8 單向鏈表的直接選擇排序算法描述數(shù)據(jù)結構（Java版）葉核亞單向鏈表的直接選擇排序算法 public void selectsort() OnelinkNode sortedhead=null,sortedrear=null; OnelinkNode p=null,q=null,min=null,m

16、inprior=null; do min=head; p=head.next; q=head; while(p!=null) if(p.datamin.data) /比較,min記住最小值位置 minprior=q; /minprior是min的前驅結點 min=p;數(shù)據(jù)結構（Java版）葉核亞3.5 歸并排序1歸并排序算法描述n所謂歸并，就是將兩個已排序的數(shù)據(jù)序列合并，形成一個已排序的數(shù)據(jù)序列，又稱兩路歸并。圖3.9 歸并排序算法描述數(shù)據(jù)結構（Java版）葉核亞順序存儲線性表的歸并排序算法描述數(shù)據(jù)結構（Java版）葉核亞2順序表的歸并排序算法實現(xiàn) MergeSort1 temp; /輔助線性

17、表 public void mergesort() /歸并排序算法 MergeSort1 x=this; int len=1; /已排序的序列長度,初始值為1 temp=new MergeSort1(x.length(); /temp所需空間與x一樣 do x.mergepass(temp,len); /將x中元素歸并到temp中 temp.output(); len=len*2; temp.mergepass(x,len); /將temp中元素歸并到x中 x.output(); len=len*2; while(lenq.data) /比較兩個鏈表第1個結點的值 q=h1.head;數(shù)據(jù)結構（Java版）葉核亞實習31實習目的：學習多種排序算法，靈活運行排序算法