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

Đăng ngày | Thể loại: | Lần tải: 1 | Lần xem: 0 | Page: 100 | FileSize: M | File type: PDF
of x

Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 5. 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 sắp xếp gồm các nội dung chính được trình bày như sau: 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 bài toán sắp xếp, các phương pháp sắp xếp đặc biệt,... Giống những giáo án bài giảng khác được thành viên chia sẽ hoặc do sưu tầm lại và chia sẽ lại cho các bạn với mục đích nghiên cứu , chúng tôi không thu phí từ thành viên ,nếu phát hiện nội dung phi phạm bản quyền hoặc vi phạm pháp luật xin thông báo cho chúng tôi,Ngoài thư viện tài liệu này, bạn có thể download giáo án miễn phí phục vụ tham khảo Một số tài liệu tải về lỗi font chữ không xem được, có thể máy tính bạn không hỗ trợ font củ, bạn tải các font .vntime củ về cài sẽ xem được.

https://tailieumienphi.vn/doc/bai-giang-cau-truc-du-lieu-va-thuat-toan-chuong-5-31obuq.html

Nội dung


Chương 5 : Các thuật toán sắp xếp
Trịnh Anh Phúc
1 Bộ

1

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 20 tháng 4 năm 2016

Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuật
Cấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 4 năm 2016
Ngày 20 tháng

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

Các phương pháp sắp xếp đặc biệt

8

Tổng kết

Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuật
Cấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 4 năm 2016
Ngày 20 tháng

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ện CNTT & TT, Trường thuật
Cấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 4 năm 2016
Ngày 20 tháng

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ỏ) :
trường "khóa" chứa giá trị khóa
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 bảng khóa trên không đòi hỏi di chuyển
các bản ghi dữ liệu - trong bảng chính, nhưng trình tự các bản ghi
trong bảng khóa cho phép xác định trình tự các bản ghi dữ liệu trong
bản chính.

Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuật
Cấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 4 năm 2016
Ngày 20 tháng

4 / 92

Bài toán sắp xếp

Mô tả giải thuật của bài toán sắp xếp
Đầu vào : Dãy gồm n khóa A = (a1 , a2 , · · · , an )
Đầu ra : Một hoán vị của dãy A là dãy A = (a1 , a2 , · · · , an ) sao cho
dãy thỏa mãn
a1 ≤ a2 ≤ · · · ≤ an

Độ quan trọng của thuật toán sắp xếp

40% thời gian hoạt động của máy tính là dành cho
việc sắp xếp - D.Knuth

Trịnh Anh Phúc ( Bộ môn Khoa Học Máy Tính, Viện CNTT & TT, Trường thuật
Cấu trúc dữ liệu và giải Đại Học Bách Khoa Hà Nội. ) 4 năm 2016
Ngày 20 tháng

5 / 92

1116937

Tài liệu liên quan


Xem thêm