intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - Trường ĐH Văn Lang

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:32

Thêm vào BST
Báo xấu
18
lượt xem 4
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 Các giải thuật sắp xếp nâng cao, cung cấp cho người học những kiến thức như: quick sort; merge sort; heap sort. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - Trường ĐH Văn Lang

  1. 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
  2. 01. QUICK SORT NỘI 02. MERGE SORT DUNG 03. HEAP SORT
  3. 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: 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 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 3 KHOA CÔNG NGHỆ THÔNG TIN
  4. 01. QUICK SORT 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) 3 1 4 1 5 9 2 6 5 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 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com Danh sách 1 < mốc = 2 1 1 Danh sách 2 ≥ mốc = 4 5 9 3 6 5 3 3. Đệ quy Danh sách 1 2 1 1 Danh sách 2 4 5 9 3 6 5 3 1 1 2 4 3 3 9 6 5 5 xong xong 3 3 4 5 6 5 9 xong xong xong 5 5 6 Đây là danh sách được sắp cuối cùng… xong xong 4 KHOA CÔNG NGHỆ THÔNG TIN
  5. 01. QUICK SORT 3 1 4 1 5 9 2 6 5 3 l r l là biên trái, r là biên phải pval 3 3 1 4 1 5 9 2 6 5 3 l r l từ biên trái tìm ptử ≥ pval, r từ biên 3 1 4 1 5 9 2 6 5 3 phải tìm ptử < pval 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com l r Nếu l != r Hoán vị ptử l với r 2 1 4 1 5 9 3 6 5 3 l r Khi l < r, tìm tiếp l và r 2 1 4 1 5 9 3 6 5 3 l r Nếu l != r Hoán vị ptử l với r 2 1 1 4 5 9 3 6 5 3 l,r Khi l < r, tìm tiếp l và r. Dừng khi l ≥ 2 1 1 4 5 9 3 6 5 3 r Tách làm 2 danh sách dựa vào chỉ mục l 2 1 1 4 5 9 3 6 5 3 5 KHOA CÔNG NGHỆ THÔNG TIN
  6. 01. QUICK SORT public int[] sort( int[] list ) { Giao diện return (qsort( list, 0, list.Length - 1 )); } // Sort private int[] qsort( int[] list, int left, int right ) { 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com int pval, l = left, r = right, temp; if ( l == r ) return list; if ( list[l] >= list[l+1] ) Lấy giá trị lớn nhất pval = list[l]; trong hai số bên trái else trong danh sách pval = list[l+1]; 6 KHOA CÔNG NGHỆ THÔNG TIN
  7. 01. QUICK SORT Ở đây ta phân vùng danh sách thành hai danh sách. Đây là hai danh sách ảo là danh sách được xác định bởi các chỉ số, không phải hai mảng riêng biệt… while ( l < r ) { Chụm vào từ bên phải và bên while (( list[l] < pval ) && ( l < r )) 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com trái cho đến khi tìm thấy các giá l ++; trị để hoán vị hoặc ta chạy hết while (( list[r] >= pval ) && ( l < r )) các phần tử trong danh sách. r --; 7 KHOA CÔNG NGHỆ THÔNG TIN
  8. 01. QUICK SORT if ( l != r ) { Nếu chỉ mục trái khác chỉ temp = list[l]; mục phải là ta đã tim được list[l] = list[r]; các giá trị để hoán vị, và ở list[r] = temp; đây ta thực hiện hoán vị… } // if 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com } // while qsort( list, left, l-1 ); Nếu xảy ra bất kỳ hoán vị qsort( list, l, right ); nào thì ta đệ quy; ngược lại, ta kết thúc… return list; } // qsort 8 KHOA CÔNG NGHỆ THÔNG TIN
  9. 01. QUICK SORT Hiệu năng của Quick Sort bị tác động bởi phần tử được chọn làm điểm mốc. Hiệu xuất của quick sort trong trường hợp xấu nhất, O(n2). 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com Trường hợp tổng quát, quick sort có sự thực thi O(n log n) thời gian biểu thị ở bên phải… Quick Sort được coi là sắp xếp nhanh nhất Ưu điểm: Nhược điểm: cực nhanh rất phức tạp đệ quy ồ ạt 9 KHOA CÔNG NGHỆ THÔNG TIN
  10. 02. MERGE SORT •Merge Sort (Sắp Xếp Trộn) cũng là thuật toán đệ quy, chia để trị •Các bước của thuật toán là: ̶ Đệ quy phân vùng danh sách đầu vào thành hai danh 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com sách, L1 và L2 khoảng n/2 phần tử mỗi danh sách cho đến khi ta có tập các danh sách với 1 hoặc 2 phần tử trong mỗi danh sách. ̶ Đến đây, mỗi L1 và L2 được trộn lại thành danh sách duy nhất S, các phần tử của L1 và L2 được đưa vào danh sách S theo thứ tự. 10 KHOA CÔNG NGHỆ THÔNG TIN
  11. 02. MERGE SORT Merge Sort tương đối đơn giản như sau: void MergeSort(int[] arr, int left, int right) { Kết thúc khi danh v if(left < right) sách chỉ có 1 { phần tử 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com v int mid = (left + right) / 2; Xác định phần tử giữa MergeSort(arr, left, mid); v để chia danh sách MergeSort(arr, mid + 1, right); Chia thành hai tập v right); Merge(arr, left, mid, L1, L2 và đệ quy } } Trộn L1 và L2 với nhau cho ra danh sách được sắp xếp 11 KHOA CÔNG NGHỆ THÔNG TIN
  12. 02. MERGE SORT void Merge(int[] arr, int left, int mid, int right) { int[] leftarray = new int[mid - left + 1]; int[] rightarray = new int[right - mid]; Array.Copy(arr, left, leftarray, 0, mid - left + 1); 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com Array.Copy(arr, mid + 1, rightarray, 0, right - mid); Tạo hai mảng con leftarray (L1), rightarray (L2) 12 KHOA CÔNG NGHỆ THÔNG TIN
  13. 02. MERGE SORT int i = 0; int j = 0; for(int k = left; k < right + 1; k++){ if(i == leftarray.Length){ arr[k] = rightarray[j]; j++; Trộn các phần tử trong } mảng leftarray, mảng else if(j == rightarray.Length){ 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com rightarray vào mảng arr[k] = leftarray[i]; i++; arr theo thứ tự giá trị } phần tử else if(leftarray[i]
  14. 02. MERGE SORT 3 1 4 1 5 9 2 6 5 3 3 1 4 1 5 9 2 6 5 3 3 1 4 1 5 9 2 6 5 3 3 1 4 1 5 9 2 6 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ 5 3 ibaotu.com 3 1 9 2 1 3 2 9 1 3 4 1 5 2 6 9 3 5 1 1 3 4 5 2 3 5 6 9 1 1 2 3 3 4 5 5 6 9 14 KHOA CÔNG NGHỆ THÔNG TIN
  15. 02. MERGE SORT •Ta có thể thấy rằng thời gian chạy của merge sort cho danh sách có độ dài n là T(n) •Vì ta cắt đôi danh sách và sau đó đệ quy, ta có thể kết luận: 2T(n/2)+n •Lưu ý là ta cộng them n bước để trộn kết quả hai danh sách 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com •Hiệu năng trung bình của Merger Sort là O(n log n) •Merge Sort yêu cầu không gian nhớ O(n) •Merge Sort có thể là một lựa chọn tối ưu vì nó thực thi ngang bằng với Quick Sort nhưng sử dụng ít bộ nhớ hơn 15 KHOA CÔNG NGHỆ THÔNG TIN
  16. 03. HEAP SORT •Heap Sort (Sắp xếp vun đống) là thuật toán sắp xếp dựa trên cấu trúc dữ liệu Binary Heap (Đống nhị phân). Tìm phần tử lớn nhất và đặt nó ơ cuối danh sách; lặp lại cho danh sách gồm các phần tử còn lại. •Binary Heap là gì?感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com ▪ Binary Heap là một Complete Binary Tree (cây nhị phân hoàn chỉnh) với nút cha có giá trị lớn hơn giá trị hai nút con. ▪ Cây nhị phân hoàn chỉnh là cây nhị phân trong đó mọi cấp, ngoại trừ cấp cuối cùng, được lấp đầy hoàn toàn. • Mảng biểu diễn cho đống nhị phân. Nếu nút cha lưu ở chỉ mục i thì nút con bên trái là 2*i+1, và nút con bên phải là 2*i+2. 16 KHOA CÔNG NGHỆ THÔNG TIN
  17. 03. HEAP SORT 12 11 13 5 6 7 12 13 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 11 13 11 12 5 6 7 5 6 7 Cây nhị phân hoàn chỉnh Đống nhị phân (Binary Heap) (Complete Binary Tree) 17 KHOA CÔNG NGHỆ THÔNG TIN
  18. 03. HEAP SORT •Thuật toán Heap Sort cho sắp xếp tăng dần: 1. Tạo Binary Heap (đống nhị phân) từ danh sách 2. Lúc này, phần tử lớn nhất được lưu ở nút gốc của đống. Hoán vị nó với phần tử cuối cùng của đống. Giảm kích thước đống đi 1 đơn vị. Cuối cùng, chất đống gốc của cây 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 3. Lặp lại các bước trên khi kích thước của đống lớn hơn 1 18 KHOA CÔNG NGHỆ THÔNG TIN
  19. 03. HEAP SORT Ví dụ 1: 12 11 13 5 6 7 13 11 12 5 6 7 7 11 12 5 6 13 12 13 7 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 11 13 11 12 11 12 5 6 7 5 6 7 5 6 13 Cây nhị phân hoàn chỉnh Đống nhị phân (Complete Binary Tree) (Binary Heap) 19 KHOA CÔNG NGHỆ THÔNG TIN
  20. 03. HEAP SORT 7 11 12 5 6 13 7 11 12 5 6 12 11 7 5 6 6 11 7 5 12 7 7 12 6 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 11 12 11 12 11 7 11 7 5 6 13 5 6 5 6 5 12 Đống nhị phân (Binary Heap) 20 KHOA CÔNG NGHỆ THÔNG TIN
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2