第 1 页
goupee.vn goupee.com Phần 3: Cấu trúc dữ liệu và giải thuật Chương 12: Các giải thuật sắp xếp cuu duong than cong . com fb.com/goupee.vn 1 CuuDuongThanCong.com https://fb.com/tailieudientucntt
资料内容
第 2 页
goupee.vnNội dung chính goupee.com 1. Đặt vấn đề 2. Các giải thuật sắp xếp cơ bản Sắp xếp chọn (selection sort) Sắp xếp nổi bọt (bubble sort) Sắp xếp chèn (insertion sort) 3. Các giải thuật sắp xếp nâng cao Sắp xếp nhanh (quick sort)cuu duong than cong . com Sắp xếp vun đống (heap sort) Sắp xếp trộn (merge sort) Trường ĐHBK Hà nội fb.com/goupee.vn Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt
第 3 页
goupee.vnĐặt vấn đề goupee.com Yêu cầu: Bài toán tổng quát: Cho trước một dãy N phần tử a1, a2, …, aN. Ta cần tìm giải thuật sắp xếp các phần tử của dãy trên trên một thứ tự nào đó theo một tiêu chuẩn nào đó. Bài toán đơn giản: Không giảm tính tổng quát của các giải thuật sắp xếp, đồng thời để đơn giản hóa việc trình bầy, sau này ta sẽ minh họa các giải thuật thông qua việc sắp xếp một dãy N số theo trật tự tăng dầncuu duong than cong . com. Trường ĐHBK Hà nội fb.com/goupee.vn Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 3 CuuDuongThanCong.com https://fb.com/tailieudientucntt
第 4 页
goupee.vnĐặt vấn đề goupee.com a1,a2,…,aN a’1,a’2,…,a’N Sorting Algorithm? Với mỗi giải thuật, sẽ đưa ra: Ý tưởng giải thuật Cài đặt cơ bản (gồm 1 hoặc 1 số hàm)cuu duong than cong . com Trường ĐHBK Hà nội fb.com/goupee.vn Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 4 CuuDuongThanCong.com https://fb.com/tailieudientucntt
第 5 页
goupee.vnCác giải thuật sắp xếp cơ bản goupee.com Giới thiệu chung: Các GTSX cơ bản đều có chung ý tưởng là ở mỗi bước, chỉ tập trung vào việc đưa từng phần tử của dãy cần SX vào đúng vị trí của nó trong dãy kết quả, mà không cần quan tâm đến vị trí của các phần tử khác Với các GTSX nâng cao, mỗi bước của giải thuật không chỉ đưa từng phần tử vào đúng vị trí của nó trong dãy kết quả, mà nó còn kết hợp bố trí hợp lý các phần tử còn lại, nhằm giảm thiểu số thao tác ở những bước sau. Chính vì lý do ở trên, các GTSX nâng cao thường chạy nhanhcuu duong than cong . com hơn các GTSX cơ bản, nhưng cũng thường phức tạp hơn trong ý tưởng giải thuật và cài đặt. Trường ĐHBK Hà nội fb.com/goupee.vn Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 5 CuuDuongThanCong.com https://fb.com/tailieudientucntt
第 6 页
goupee.vnCác giải thuật sắp xếp cơ bản goupee.com Sắp xếp chọn Sắp xếp nổi bọt Sắp xếp chèn cuu duong than cong . com Trường ĐHBK Hà nội fb.com/goupee.vn Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt
第 7 页
goupee.vn Sắp xếp chọngoupee.com Ý tưởng giải thuật Đầu vào: dãy N số a1,a2,…,aN Đầu ra: dãy vào đã được sx theo chiều tăng dần Giải thuật: GT thực hiện trong đúng N-1 bước, đánh số các bước i=1,2,…,N-1 Ở bước thứ i, tìm số nhỏ thứ i rồi đưa nó vào vị trí thứ i trong dãy cuu duong than cong . com Trường ĐHBK Hà nội fb.com/goupee.vn Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 7 CuuDuongThanCong.com https://fb.com/tailieudientucntt
第 8 页
goupee.vnMinh họa hoạt động của GT goupee.com G/s cho dãy ban đầu với N=7 3 2 4 5 1 7 6 i = 1 1 2 4 5 3 7 6 i = 2 1 2 4 5 3 7 6 i = 3 1 2 3 5 4 7 6 i = 4 1 2 3 4 5 7 6 i = 5 cuu duong than cong . com1 2 3 4 5 7 6 i = 6 1 2 3 4 5 6 7 Trường ĐHBK Hà nội fb.com/goupee.vn Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 8 CuuDuongThanCong.com https://fb.com/tailieudientucntt
第 9 页
goupee.vn Sắp xếp chọngoupee.com Mô tả tựa lập trình for (i=1;i<=N-1;i++) { //Tìm phần tử bé thứ i (bé nhất kể từ ai đến aN) m=i; for (k=i+1;k<=N;k++) if (ak < am) m=k; //Đưa phần tử bé thứ i về vị trí thứ i if (m<>i) swap(acuu duong than cong . comm,ai); } Trường ĐHBK Hà nội fb.com/goupee.vn Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 9 CuuDuongThanCong.com https://fb.com/tailieudientucntt
第 10 页
goupee.vn Sắp xếp chọn – Cài đặt hàmgoupee.com void selectionSort(int A[], int N) { int m; for (int i=0; i < N-1; i++){ m=i; for (int k=i+1; k < N; k++) if (A[k] < A[m]) m=k; if (m != i) swap(A[i],A[m]); } cuu duong than cong . com } Trường ĐHBK Hà nội fb.com/goupee.vn Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 10 CuuDuongThanCong.com https://fb.com/tailieudientucntt
第 11 页
goupee.vnSắp xếp nổi bọt goupee.com Ý tưởng giải thuật: đây là một giải thuật cải tiến so với GTSX chọn, bằng cách thay đổi cách tìm và đưa phần tử nhỏ nhất về đầu dãy ở mỗi bước Đầu vào: dãy N số a1,a2,…,aN Đầu ra: dãy vào đã được sx theo chiều tăng dần Giải thuật: GT thực hiện trong tối đa là N-1 bước, đánh số các bước i=1,2,3,… Ở bước thứ i, so sánh lần lượt N-i cặp số (ak và ak+1), với k=N-1,N- 2,…,i; sao cho nếu ak > ak+1 thì Hoán Đổi ak và ak+1 Nếu ở một bước i nào đó mà ta không phải hoán đổi cặp nào thìcuu duong than cong . com chứng tỏ dãy đã sắp xếp, nên dừng GT ở đây. Trường ĐHBK Hà nội fb.com/goupee.vn Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 11 CuuDuongThanCong.com https://fb.com/tailieudientucntt
第 12 页
goupee.vnMinh họa hoạt động của GT goupee.com G/s cho dãy N=7 số 3 2 4 5 1 7 6 i = 1 1 3 2 4 5 6 7 i = 2 1 2 3 4 5 6 7 i = 3 1 2 3 4 5 6 7 dừng ở đây cuu duong than cong . com Trường ĐHBK Hà nội fb.com/goupee.vn Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 12 CuuDuongThanCong.com https://fb.com/tailieudientucntt
第 13 页
goupee.vnMô tả tựa lập trình goupee.com i = 1; sorted = False; while (!sorted && i<N) { sorted = True; for (k=N-1;k>=i;k--) if (ak > ak+1) { swap(ak, ak+1); sorted = False; cuu duong than cong . com} i++; } Trường ĐHBK Hà nội fb.com/goupee.vn Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 13 CuuDuongThanCong.com https://fb.com/tailieudientucntt
第 14 页
goupee.vn Sắp xếp nổi bọt – Cài đặt hàmgoupee.com void bubbleSort(int A[], int N) { int i = 0; bool sorted = false; while (!sorted && i<N-1) { sorted = true; for (k=N-2;k>=i;k--) if (A[k] > A[k+1]) { swap(A[k], A[k+1]); sorted = false; } i++;cuu duong than cong . com } } Trường ĐHBK Hà nội fb.com/goupee.vn Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 14 CuuDuongThanCong.com https://fb.com/tailieudientucntt
第 15 页
goupee.vnSắp xếp chèn goupee.com Ý tưởng giải thuật: tiến hành xây dựng dãy được sắp xếp có số phần tử tăng dần, ban đầu là 1 phần tử, sau đó là 2 phần tử, … và cuối cùng đủ N phần tử được sắp xếp. Ở mỗi bước, ta cần chèn một phần tử trong dãy chưa được sắp xếp vào một dãy các phần tử đã được sắp xếp, sao cho sau khi chèn thì dãy mới cũng được sx. Đầu vào: dãy N số a1,a2,…,aN Đầu ra: dãy vào đã được sx theo chiều tăng dần Giải thuật: GT thực hiện trong N-1 bước, đánh số các bước i=1,2,…,N-1 Ở bước thứ i, ta được dãy (acuu duong than cong . com1,a2,…,ai) đã được sắp xếp, ta cần chèn phần tử ai+1 vào dãy trên sao cho sau khi chèn ta được dãy mới cũng được sx. Trường ĐHBK Hà nội fb.com/goupee.vn Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 15 CuuDuongThanCong.com https://fb.com/tailieudientucntt
第 16 页
goupee.vnGiải thuật chèn goupee.com Đầu vào: Dãy (a , a ,…, a ) đã được sắp xếp, và phần tử cần chèn b 1 2 i Đầu ra: Dãy (a , a ,…, a , a ) cũng được sx. 1 2 i i+1 Giải thuật: Tìm vị trí k cần chèn trong dãy ban đầu thỏa mãn các điều kiện sau: 1 k i+1 b<a1 hoặc ai b hoặc ak-1 b < ak Dịch các phần tử (ak,ak+1,…,ai) sang phải một vị trí để nhường chỗ cho phần tử b Chèn b vào vị trí k Lưu ý: để kết hợp việc tìm vị trí k và dịch các phần tử sang phải, ta sẽ tiến hành tìm từ cuối dãy trở về đầu. Ban đầu so sánh b với ai+1, sau đó với ai,…,cuu duong than cong . com rồi cứ lùi dần cho đến khi điều kiện vị trí ở trên thỏa mãn. Đồng thời ở mỗi bước trên ta lại dịch được một phần tử vừa so sánh với b sang bên phải 1 vị trí. Trường ĐHBK Hà nội fb.com/goupee.vn Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 16 CuuDuongThanCong.com https://fb.com/tailieudientucntt
第 17 页
goupee.vnMô tả tựa lập trình cho GTSX chèngoupee.com for (i=1;i<N;i++){ k = i; b = ai+1; while (k>=1 AND b<ak){ ak+1 = ak; k--; } cuu duong than cong . comak+1 = b; } Trường ĐHBK Hà nội fb.com/goupee.vn Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 17 CuuDuongThanCong.com https://fb.com/tailieudientucntt
第 18 页
goupee.vnMinh họa hoạt động của GT goupee.com 3 2 5 4 1 7 6 i = 1 2 3 5 4 1 7 6 i = 2 2 3 5 4 1 7 6 i = 3 2 3 4 5 1 7 6 i = 4 1 2 3 4 5 7 6 i = 5 1 2 3 4 5 7 6 cuu duong than cong . com i = 6 1 2 3 4 5 6 7 Trường ĐHBK Hà nội fb.com/goupee.vn Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 18 CuuDuongThanCong.com https://fb.com/tailieudientucntt
第 19 页
goupee.vn Sắp xếp chèn – Cài đặt hàmgoupee.com void insertionSort(int A[], int N) { int i,k,b; for (i=0;i < N-1;i++){ k = i; b = A[i+1]; while (k>=0 && b<A[k]){ A[k+1] = A[k]; k--; } A[k+1] = b;cuu duong than cong . com } } Trường ĐHBK Hà nội fb.com/goupee.vn Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 19 CuuDuongThanCong.com https://fb.com/tailieudientucntt
第 20 页
goupee.vnCác giải thuật sắp xếp nâng cao goupee.com Sắp xếp nhanh (Quick Sort) Sắp xếp trộn (Merge Sort) Sắp xếp vun đống (Heap Sort) cuu duong than cong . com Trường ĐHBK Hà nội fb.com/goupee.vn Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 20 CuuDuongThanCong.com https://fb.com/tailieudientucntt
显示前 20 页。下载资料查看完整内容。
评论 (0)
暂无评论。快来抢沙发吧！