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
NỘI
DUNG
QUICK SORT
MERGE SORT
HEAP SORT
01.
02.
03.
感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！
ibaotu.com
3
KHOA CÔNG NGHỆ THÔNG TIN
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:
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
感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！
ibaotu.com
4
KHOA CÔNG NGHỆ THÔNG TIN
01. QUICK SORT
3141592653
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)
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ị < mốc, một danh sách chứa các phần tử có giá trị ≥ mốc
2 1 1
Danh sách 1 < mốc = 4593653Danh sách 2 ≥ mốc =
3. Đệ quy
Danh sách 1 2 1 1 Danh sách 2 4593653
1 1 2
xong xong
433 9655
3 3 4565 9
5 5 6
xong xong
xong xong
xong
Đây là danh sách được sắp cuối cùng…
感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！
ibaotu.com
5
KHOA CÔNG NGHỆ THÔNG TIN
01. QUICK SORT
3 1 41592653
3
pval
3141592653
lr
3141592653
lr
2141593653
lr
2 1 4 1 593653
lr
2114593653
lr
2114593653
l,r
211 4593653
l là biên trái, r là biên phải
l từ biên trái tìm ptử ≥ pval, r từ biên
phải tìm ptử < pval
Nếu l != r Hoán vị ptử l với r
Khi l < r, tìm tiếp l và r
Nếu l != r Hoán vị ptử l với r
Khi l < r, tìm tiếp l và r. Dừng khi l ≥
r
Tách làm 2 danh sách dựa vào chỉ mục l