Cấu trúc dữ liệu và giải thuật (phần 8)

Chia sẻ: Nguyen Kien | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

101
lượt xem 27
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Còn trong phần 8 này các bạn sẽ làm quen với thuật toán Trộn nhưng trong đó có bổ sung các thuật toán trộn khác nhau, như có trộn đa pha, nâng cao của thuật toán trộn

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Cấu trúc dữ liệu và giải thuật (phần 8)

Polyphase Merge sort Polyphase Tr n a pha: Tr n a l i cân b ng các m ng chưa ư c s d ng 1 cách hi u qu b i vì trong cùng 1 l n duy t thì phân n a s m ng luôn luôn gi vai trò tr n (ngu n) và phân n a gi vai trò phân ph i ( ích) C i ti n: Thay i vai trò c a các m ng trong cùng 1 l n duy t Phương pháp tr n a pha
Polyphase Merge sort Polyphase Gi i thu t: Ta xét ví d v i 3 m ng a1,a2,a3 B1: Phân ph i luân phiên các run ban u c a a vào a1,a2 B2: Tr n các run c a a1,a2 vào a3. Gi i thu t k t thúc n u a3 ch còn 1 run B3: Chép ½ run c a a3 vào a1 B4: Tr n các run c a a1,a3 vào a2. Gi i thu t k t thúc n u a2 ch còn 1 run B5: Chép ½ s run c a a2 vào a1. L p l i B2
Polyphase Merge sort Polyphase Như c i m: - M t th i gia sao chép ½ s run c a m ng này vào m ng kia. Vi c sao chép này có th lo i b n u ta b t u v i Fn-1 run c a m ng 1 và Fn-2 run c a m ng 2. V i Fn-1, Fn-2 là các s liên ti p trong nãy Fibonaci
Polyphase Merge sort Polyphase Ví d : a=[13,12,11,10,9,8,7,6,5,4,3,2,1] có t t c 13 run F6=13 (1 1 2 3 5 8 13) Có t t c 6 phase a1 có 8 run, a2 có 5 run
Polyphase Merge sort Polyphase Phase a1 a2 a3 1 13,12,11,10,9,8,7,6 5,4,3,2,1 2 8,7,6 (5,13);(4,12);(3,11) (2,10);(1,9) 3 (5,8,13);(4,7,12) (2,10), (1,9) (3,6,11) 4 (2,5,8,10,13); (3,6,11) (1,4,7,9,12) 5 (1,4,7,9,12) (2,3,5,6,8,10,11,13 (1,2,3,4,5,6,7,8, ) 6 9,10,11,12,13)

CÓ THỂ BẠN MUỐN DOWNLOAD

ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn