TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu & thuật toán: Chương 5 - Nguyễn Đức Nghĩa

Bài giảng Cấu trúc dữ liệu & thuật toán - Chương 5: Sắp xếp (Sorting) giúp người học nắm được các kiến thức về bài toán sắp xếp, ba thuật toán sắp xếp cơ bản, sắp xếp trộn, sắp xếp nhanh, sắp xếp vun đống, cận dưới cho độ phức tạp tính toán của bài toán sắp xếp và các phương trình sắp xếp đặc biệt. | Chương 5 Sắp xếp Sorting Heap Sort Quick Sort William A. Martin Sorting. ACM Computing Surveys Vol. 3 Nr 4 Dec 1971 pp. 147-174. .The bibliography appearing at the end of this article lists 37 sorting algorithms and 100 books and papers on sorting published in the last 20 years. Suggestions are made for choosing the algorithm best suited to a given situation. D. Knuth 40 thời gian hoạt động của các máy tính là dành cho sắp xếp NGUYỄN ĐỨC NGHĨA Bộ môn KHMT - ĐHBKHN NỘI DUNG . Bài toán sắp xếp . Ba thuật toán sắp xếp cơ bản . Sắp xếp trộn Merge Sort . Sắp xếp nhanh Quick Sort . Sắp xếp vun đống Heap Sort . Cận dưới cho độ phức tạp tính toán của bài toán sắp xếp . Các phương pháp sắp xếp đặc biệt NGUYỄN ĐỨC NGHĨA Bộ môn KHMT - ĐHBKHN 2 . Bài toán sắp xếp . Bài toán sắp xếp . Giới thiệu sơ lược về các thuật toán sắp xếp 3 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT - ĐHBKHN . Bài toán sắp xếp Sắp xếp Sorting - Là quá trình tổ chức lại họ các dữ liệu theo thứ tự giảm dần hoặc tăng dần ascending or descending order Dữ liệu cần sắp xếp có thể là - Số nguyên Integers - Xâu ký tự Character strings - Đối tượng Objects Khoá sắp xếp Sort key - Là bộ phận của bản ghi xác định thứ tự sắp xếp của bản ghi trong họ các bản ghi. - Ta cần sắp xếp các bản ghi theo thứ tự của các khoá. NGUYỄN ĐỨC NGHĨA Bộ môn KHMT - ĐHBKHN 4 . Bài toán săp xêp Chú ý Việc sắp xếp tiến hành trực tiếp trên bản ghi đòi hỏi di chuyển vị trí bản ghi có thể là thao tác rất tốn kém. Vì vậy người ta thường xây dựng bảng khoá gồm các bản ghi chỉ có hai trường là khoá con trỏ - trường khoá chứa giá trị khoá - trường con trỏ để ghi địa chỉ của bản ghi tương ứng. Việc sắp xếp theo khoá trên bảng khoá không làm thay đổi bảng chính nhưng trình tự các bản ghi trong bảng khoá cho phép xác định trình tự các bản ghi trong bảng chính. phép xác định trình tự các bản ghi trong bảng chính. NGUYỄN ĐỨC NGHĨA Bộ môn KHMT - ĐHBKHN 5 . Bài toán săp xêp . Bài toán săp xêp Ta có thể hạn chế .

TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.