tailieunhanh - Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 5 - Trịnh Anh Phúc

Bài giảng "Cấu trúc dữ liệu và thuật toán - Chương 5: Các thuật toán xắp xếp" cung cấp cho người học các kiến thức: 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,. nội dung chi tiết. | Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 5 - Trịnh Anh Phúc Chương 5 : Các thuật toán sắp xếp Trịnh Anh Phúc 1 1 Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường Đại Học Bách Khoa Hà Nội. Ngày 5 tháng 3 năm 2014 Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa Ngày Hà 5Nội. tháng ) 3 năm 2014 1 / 92 Giới thiệu 1 Bài toán sắp xếp 2 Ba thuật toán sắp xếp cơ bản 3 Sắp xếp trộn 4 Sắp xếp nhanh 5 Sắp xếp vun đống 6 Cận dưới cho bài toán sắp xếp 7 Tổng kết 8 Các phương pháp sắp đặc biệt Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa Ngày Hà 5Nội. tháng ) 3 năm 2014 2 / 92 Bài toán sắp xếp Định nghĩa 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 (Intergers) Xâu ký tự (String) Đối tượng (Object) Ta cần có khóa sắp xếp (sort key) dùng để phân biệt các dữ liệu với nhau. Khóa này duy nhất cho từng dữ liệu và được dùng để sắp xếp. Lưu ý, không có khóa trùng lặp cho hai dữ liệu phân biệt chính bởi vậy các giải thuật sắp xếp mới thực hiện được. Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, ViệnCấu CNTT trúc&dữTT, liệu Trường và giải thuật Đại Học Bách Khoa Ngày Hà 5Nội. tháng ) 3 năm 2014 3 / 92 Bài toán sắp xếp Lưu ý khi biểu diễn bài toán sắp xếp trong máy tính Việc sắp xếp tiến hành trực tiếp trên bản ghi dữ liệu đòi hỏi các thao tác di chuyển tốn kém. Vì vậy người ta thường xây dựng một bảng khóa gồm các bản ghi chỉ gồm hai trường là (khóa, con trỏ) : I trường "khóa" chứa giá trị khóa I trường "con trỏ" chứa địa chỉ trỏ đến các bản ghi dữ liệu tương ứng Việc sắp xếp theo khóa trong