Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật (Data structures and Algorithms): Chương 3 - Ngô Công Thắng

Chương 3 - Sắp xếp và tìm kiếm nâng cao. Những nội dung chính được trình bày trong chương này gồm có: Sắp xếp nhanh (Quick Sort), sắp xếp vun đống (Heap Sort), sắp xếp hòa nhập (Merge Sort), tìm kiếm nhị phân, cây nhị phân tìm kiếm. Mời các bạn cùng tham khảo. | CHƯƠNG 3 SẮP XẾP VÀ TÌM KIẾM NÂNG CAO GV. Ngô Công Thắng Bộ môn Công nghệ phần mềm Khoa Công nghệ thông tin Website dse.vnua.edu.vn ncthang Email ncthang@vnua.edu.vn Nội dung Chương 3 1. Sắp xếp nhanh Quick Sort 2. Sắp xếp vun đống Heap Sort 3. Sắp xếp hòa nhập Merge Sort 4. Tìm kiếm nhị phân 5. Cây nhị phân tìm kiếm Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.2 1. Sắp xếp nhanh Quick Sort 1.1. Phương pháp Sắp xếp nhanh quick sort còn được sắp xếp phân đoạn partition sort . Ý tưởng thuật toán Chọn ngẫu nhiên một phần tử x. Duyệt từ bên trái mảng cho tới khi có một phần tử ai gt x Sau đó duyệt từ bên phải mảng cho tới khi có một phần tử aj x. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.4 Thủ tục sắp xếp nhanh Procedure Q_sort L R 1 If L gt R then return 2 i L j R k L R div 2 3 x a k 4 Repeat While a i x Do j j-1 If i 2. Sắp xếp vun đống Heap Sort 2.1. Phương pháp Một cây nhị phân có chiều cao h được gọi là đống khi Là cây nhị phân hoàn chỉnh mà các nút lá ở mức h- 1 phải nằm phía bên trái. Khoá ở nút cha bao giờ cũng lớn hơn khoá ở nút con. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.7 2. Sắp xếp vun đống Heap Sort 2.1. Phương pháp Thuật toán sắp xếp vun đống chia làm 2 giai đoạn. Giai đoạn 1 Tạo đống. Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.8 Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.9 Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.10 Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.11 Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 03 3.12 - Lặp lại các bước tương tự cho các cây còn lại. Cuối cùng ta thu được dãy đã sắp là s 11 23 42 58 65 74 Giải thuật vun đống - Một lá coi như cây con là một đống. - Thuật toán tiến hành từ đáy lên Chuyển đổi thành đống cho một cây con mà cây con trái và cây con phải của gốc đã là một đống. Cây nhị phân hoàn chỉnh có n