tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Sắp xếp - Nguyễn Mạnh Hiển (HKI năm 2020-2021)

Bài giảng "Cấu trúc dữ liệu và giải thuật: Sắp xếp" cung cấp cho người học các kiến thức: Sắp xếp chọn, sắp xếp nổi bọt, sắp xếp chèn, sắp xếp vun đống, sắp xếp trộn, sắp xếp nhanh. | Sắp xếp Sorting Nguyễn Mạnh Hiển hiennm@ Nội dung 1. Sắp xếp chọn 2. Sắp xếp nổi bọt 3. Sắp xếp chèn 4. Sắp xếp vun đống 5. Sắp xếp trộn 6. Sắp xếp nhanh 1. Sắp xếp chọn selection sort Sắp xếp chọn Dãy A gồm n phần tử a0 a1 an-1. Mỗi bước xét một danh sách con chưa sắp xếp unsorted sublist - USL . Có n-1 bước Bước 0 USL0 a0 a1 an-1 Bước 1 USL1 a1 an-1 Bước n-2 USLn-1 an-2 an-1 Sắp xếp chọn tiếp Mỗi bước Tìm phần tử nhỏ nhất amin trong USL. Đổi chỗ amin và phần tử đầu tiên của USL. Dịch chuyển biên trái của USL sang phải một vị trí. Ví dụ sắp xếp chọn Ban đầu 64 25 12 22 11 11 64 Sau bước 0 11 25 12 22 64 12 25 Sau bước 1 11 12 25 22 64 22 25 Sau bước 2 11 12 22 25 64 25 25 Sau bước 3 11 12 22 25 64 Danh sách con chưa sắp xếp được gạch chân Cài đặt sắp xếp chọn template void selectionSort vector amp a for int i 0 i lt - 1 i int vt i Vị trí của min for int j i 1 j lt j if a vt gt a j vt j Cập nhật vị trí của min if vt i Đổi chỗ min và phần tử đầu USL T tg a vt a vt a i a i tg Phân tích sắp xếp chọn Đếm số phép so sánh a vt gt a j . Vòng for bên trong lặp với j từ i 1 đến n-1 tức là có n-1-i phép so sánh. Vòng for bên ngoài lặp với i từ 0 đến n-2. 2 1 1 2 1 0 1 2 2 2. Sắp xếp nổi bọt bubble sort Sắp xếp nổi bọt Mỗi bước duyệt qua các phần tử a0 a1 ak. Tại mỗi phần tử ai i lt k So sánh ai với ai 1 Đổi chỗ nếu chúng chưa đúng thứ tự Sau mỗi bước phần tử lớn nhất sẽ được đặt nổi bọt xuống cuối dãy ak là max . Ví dụ sắp xếp nổi bọt Ban đầu 64 25 12 22 11 k n-1-0 Sau bước 0 25 12 22 11 64 k n-1-1 Sau bước 1 12 22 11 25 64 k n-1-2 Sau bước 2 12 11 22 25 64 k n-1-3 Sau bước 3 11 12 22 25 64 Danh sách con chưa sắp xếp được gạch chân Cài đặt sắp xếp nổi bọt template void bubbleSort vector amp a for int i 0 i lt -1 i Bước i for int j 0 j lt -1-i j if a j gt a j 1 T tg a j a j a j 1 a j 1 tg Phân tích sắp xếp nổi bọt Đếm số phép so sánh a j gt a j 1 . Vòng for bên trong lặp với j từ 0 đến n-2-i tức là có n-1-i phép so sánh. Vòng for bên .