Bài giảng Cấu trúc dữ liệu - Chương 5: Sắp xếp

Phương pháp chọn, phương pháp chèn, phương pháp chèn nhị phân, phương pháp nổi bọt, phương pháp sắp xếp nhanh, phương pháp vun đống là những nội dung chính trong "Bài giảng Cấu trúc dữ liệu - Chương 5: Sắp xếp". Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu - Chương 5: Sắp xếpCHƯƠNG5SẮP XẾP 1 Chương5:Sắpxếp5.1Phươngphápchọn5.2Phươngphápchèn5.3Phươngphápchènnhịphân5.4Phươngphápnổibọt5.5Phươngphápsắpxếpnhanh5.6Phươngphápvunđống 24.1bàitoánsắpxếp ̣ ̣ Cómôttâpnđô ́itượng.Mỗiđốitượngcónhiềuthuôcti ̣ ́nh,đượcthêhiên ̉ ̣ ̣ ̉ ̉bằngmôtkiêubanghigô ̀mnhiềutrường.Sắpxếplàquátrìnhbốtrílạicácbảnghitheomộttrườnggoila ̣ ̀khóa. Vídụtrongbảngdanhbạgồmcácbảnghicótêncơquan,địachỉ,sốđiệnthoại.Sổdanhbạthườngđượcsắpxếptheotrườngkhóalàtêncơquanđểdễtìmkiếm. 34.1bàitoánsắpxếp Sắpxếplàthaotáccầnthiếthaygặptrongquátrìnhlưutrữvàquảnlýdữliệu.Có2phươngphápsắpxếp:sắpxếptrongtácđộnglêncácbảnghilưutrữởbộnhớtrongvàSắpxếpngoàiliênquanđếntậplớncácbảnghilưutrữtrêntệp.Chươngnàychỉxétbàitoánsắpxếptrongtheothứtựtăngcủakhóa.Sắpxếptheothứtựgiảmđượclàmhoàntoàntươngtự. 45.1PhươngphápchọnÝtưởng: Dãykhóacầnsắpxếplàk[1],k[2],…,k[n]. Ởlượtthứi(i=1,2,3,…,n2)tasẽchọn trongdãykhóak[i+1],….,k[n]khóanhỏ nhấtvàđổichỗnóvớik[i] Saun1lượtkhóatừnhỏđếnlớnsẽđược sắpxếpởcácvịtríthứ1,thứ2,…thứn1, thứn. 55.1Phươngphápchọn Thuậttoán: voidSX_chon(int*k,intn) {inti,x; for(i=1;i5.2PhươngphápchènÝtưởng: Dãykhóacầnxếplàk[1],k[2],…,k[n]. Đầutiênkhóak[1]chỉcómộtkhóađãđược sắpxếp.Xétthêmk[2],sosánhnóvớik[1] đểxácđịnhchỗchènnóvàovàtacó2 khóađượcsắpxếp.Đốivớik[3]lạiso sánhvớik[2],k[1]vàcứnhưvậyđếnkhi xétxongk[n]. 75.2PhươngphápchènCàiđặt: Đểcóchỗchokhóamớiphảidịchchuyển cáckhóalùilạisauvàdùngXlàmônhớ phụchứakhóađangđượcxét.Đểkhóa mớidùởvịtríđầutiêncũngđượcchèn vàogiữakhóanhỏvàlớnhơnnó,tathêm vàokhóagiảk[0]=∞. 85.2Phươngphápchèn voidSX_chen(int*k,intn) {intj; for(inti=2;i5.3PhươngphápnổibọtCàiđặt: Bảngcáckhóasẽđượcduyệttừđáylên đỉnh.Dọcđườngnếugặp2khóakếcận ngượcthứtựtasẽđổichỗchúngvới nhau. Saumỗilượtsắpxếpcácgiátrịkhóanhỏ sẽnổidầnlêngiốngnhưbọtnướctrong nồinướcđangsôi. 105.3Phươngphápnổibọt voidSX_noibot(int*k,intn) {for(inti=1;i=i+1;j) if(k[j]5.3Phươngphápnổibọt voidswap(int*c,int*d) {inta; a=*c; *c=*d; *d=a; return; } 12Đánhgiá3phươngpháp: Độphứctạptrungbìnhcủathuậttoán chungchocả3phươngpháplàO(n2) 135.4PhươngphápsắpxếpnhanhÝtưởng:Chọnkhóađầutiêncủadãylàmchốt. Mọiphầntửnhỏhơnkhóachốtphải đượcxếpvàođầudãy.Mọiphầntử lớnhơnkhóachốtphảiđượcxếpvào cuốidãy.Muốnvậy,cácphầntửtrong dãysẽđượcsosánhvớikhóachốtvà sẽđổivịtríchonhau. 145.4PhươngphápsắpxếpnhanhKhiviệcđổichỗđãthựchiệnxong,dãy khóađượcphânlàm2đoạn.Đoạnđầu gồmcáckhóanhỏhơnchốt,đoạnsau gồmcáckhóalớnhơnchốt,khóachốt nằmgiữa2đoạn.Haiđoạnsẽđượcxửlýriênggiốngnhư vậy.Quátrìnhxửlýtừngđoạnsẽkết thúckhichỉcòn1phầntử. 155.4Phươngphápsắpxếpnhanh voidSX_nhanh(int*k,intL,intU) {intB=1; if(L5.4Phươngphápsắpxếpnhanh swap(&k[L],&k[j]); SX_nhanh(k,L,j1); SX_nhanh(k,j+1,U); } return;} 175.4Phươngphápsắpxếpnhanh Đánhgiá: Độphứctạptrungbìnhcủathuậttoánlà O(nlog2n) Khikíchthướcphânđoạnđãnhỏ,tadùng phươngphápsắpxếpđơngiảntiệnhơn. 185.5PhươngphápvunđốngCàiđặt: Trướchếtphảitạođốnglàtạoracâynhị phânhoànchỉnhmàkhóaởnútchabao giờcũnglớnhơnkhóaởcácnútconcủa nó.Câynhịphânnàyđượclưutrữkế tiếptrongmáy. 195.5Phươngphápvunđống Giaiđoạnthứ2gồm: Đổichỗcủavịtrícuốicùngvớikhóaở gốccủađốngđểđưakhóalớnnhấtvềvị tríđúng. Vunlạithànhđốngchocâychứanhững nútcònlại. 20 ...