Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 Các giải thuật sắp xếp nâng cao, cung cấp cho người học những kiến thức như: quick sort; merge sort; heap sort. Mời các bạn cùng tham khảo! | KHOA CÔNG NGHỆ THÔNG TIN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Data Structures And Algorithms BÀI 4 CÁC GIẢI THUẬT SẮP XẾP NÂNG CAO 01. QUICK SORT NỘI 02. MERGE SORT DUNG 03. HEAP SORT 01. QUICK SORT Thuật toán sắp xếp Quick Sort sắp xếp nhanh phức tạp hơn một chút so với các thuật toán sắp xếp khác. Cho một danh sách các phần tử thuật toán quick sort là thuật toán chia để trị đệ quy bao gồm 3 phần chính 感谢您下载包图网平台上提供的PPT作品 为了您和包图网以及原创作者的利益 请勿复制 传播 销售 否则将承担法律责任 包图网将对作品进行维权 按照传播下载次数进行十倍的索取赔偿 1. Chọn một giá trị làm mốc pivot value 2. Phân vùng danh sách làm hai danh sách trái nhỏ hơn giá trị mốc và danh sách phải lớn hơn hoặc bằng giá trị mốc 3. Đệ quy cho danh sách trái đệ quy cho danh sách phải 3 KHOA CÔNG NGHỆ THÔNG TIN 01. QUICK SORT 1. Lấy một giá trị làm mốc Lấy giá trị lớn nhất trong hai giá trị bên trái 3 3 1 4 1 5 9 2 6 5 3 2. Phân vùng danh sách thành hai danh sách một danh sách chứa các phần tử có giá trị lt mốc một danh sách chứa các phần tử có giá trị mốc 感谢您下载包图网平台上提供的PPT作品 为了您和包图网以及原创作者的利益 请勿复制 传播 销售 否则将承担法律责任 包图网将对作品进行维权 按照传播下载次数进行十倍的索取赔偿 Danh sách 1 lt mốc 2 1 1 Danh sách 2 mốc 4 5 9 3 6 5 3 3. Đệ quy Danh sách 1 2 1 1 Danh sách 2 4 5 9 3 6 5 3 1 1 2 4 3 3 9 6 5 5 xong xong 3 3 4 5 6 5 9 xong xong xong 5 5 6 Đây là danh sách được sắp cuối cùng xong xong 4 KHOA CÔNG NGHỆ THÔNG TIN 01. QUICK SORT 3 1 4 1 5 9 2 6 5 3 l r l là biên trái r là biên phải pval 3 3 1 4 1 5 9 2 6 5 3 l r l từ biên trái tìm ptử pval r từ biên 3 1 4 1 5 9 2 6 5 3 phải tìm ptử lt pval 感谢您下载包图网平台上提供的PPT作品 为了您和包图网以及原创作者的利益 请勿复制 传播 销售 否则将承担法律责任 包图网将对作品进行维权 按照传播下载次数进行十倍的索取赔偿 l r Nếu l r Hoán vị ptử l với r 2 1 4 1 5 9 3 6 5 3 l r Khi l lt r tìm tiếp l và r 2 1 4 1 5 9 3 6 5 3 l r Nếu l r Hoán vị ptử l với r 2 1 1 4 5 9 3 6 5 3 l r Khi l lt r tìm tiếp l và r. Dừng khi l 2 1 1 4 5 9 3 6 5 3 r Tách làm 2 danh sách dựa vào chỉ mục l 2 1 1 4 5 9 3 6 5 3 5 KHOA CÔNG NGHỆ THÔNG TIN 01. QUICK SORT public int sort int list Giao diện return qsort list 0
