zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Cấu trúc dữ liệu và giải thuật (phần 4)

Chia sẻ: Nguyen Kien | Ngày: | Loại File: PDF | Số trang:10

Báo xấu

130
lượt xem 33
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tiếp tục trong tài liệu này vẫn là nói về thuật toán shell sort, nhưng sẽ đi vào chi tiết , có ví dụ chạy bằng tay để cho các bạn dễ hiểu hơn.

Chủ đề:

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

Lưu

Nội dung Text: Cấu trúc dữ liệu và giải thuật (phần 4)

Shell sort Shell So sánh a[5] =11 > a[7] = 8 Swap (a[5],a[7]) 3 1 13 7 10 8 16 11 3. d=1 So sánh a[0] = 3 > a[1] =1 Swap (a[0],a[1]) 1 3 13 7 10 8 16 11 So sánh a[1] = 3 < a[2] =13 !Swap (a[1],a[2]) 1 3 13 7 10 8 16 11 So sánh a[2] =13 > a[3] = 7 Swap (a[2],a[3]) 1 3 7 13 10 8 16 11 So sánh a[3] =13 > a[4] =10 Swap (a[3],a[4]) 1 3 7 10 13 8 16 11 So sánh a[4] =13 > a[5] = 8 Swap (a[4],a[5]) 1 3 7 10 8 13 16 11
Shell sort Shell So sánh a[5] =13 < a[6] = 16 !Swap (a[5],a[6]) 1 3 7 10 8 13 16 11 So sánh a[6] = 16 > a[7] =11 Swap (a[6],a[7]) 1 3 7 10 8 13 11 16 ánh giá thu t toán: - Tương t Insertion nhưng Shell sort có s l n so sánh gi m hơn nhi u - O(n2) Bài t p: Trình bày k t qu c a t ng bư c Shell sort v i d = 5,2,1 v i dãy [3,5,2,9,8,1,6,4,7]. Bao nhiêu phép so sánh ư c s d ng
RADIX SORT RADIX
Radix sort Radix Gi i thi u: – Radix sort – S p x p theo cơ s d a trên tính ch t "s " c a các khóa. – Radix sort không ch so sánh giá tr c a các khóa, mà so sánh các thành ph n c a khóa. Gi s các khóa là các s bi u di n theo h ghi s cơ s M. Khi ó s p x p theo cơ s s so sánh t ng ký s c a nó.
Radix sort Radix Thu t toán: – Xem các ph n t trong m ng g m các l p có ưu tiên khác nhau. VD: các s t nhiên g m các l p: ơn v , ch c, trăm, ngàn,.. – Duy t các ph n t t trên xu ng dư i. – Bư c 1: s p x p dãy các ph n t l p có ưu tiên th p nh t (VD: các ch s hàng ơn v ). S nào có hàng ơn v th p hơn thì ta ưa lên trên. – Sau bư c 1 1 dãy s p x p m i. Tương t v i các l p k ti p (ch s thu c hàng ch c, hàng trăm,…) cu i cùng s có dãy ã s p x p.
Radix sort Radix Ví d : Cho dãy [310, 213, 023, 130, 013, 301, 222, 032, 201, 111, 323, 002, 330, 102, 231, 120] Bucket Number Contents 0 310, 130, 330, 120 1 301, 201, 111, 231 2 222, 032, 002, 102 3 213, 023, 013, 323 310, 130, 330, 120, 301, 201, 111, 231, 222, 032, 002, 102, 213, 023, 013, 323
Radix sort Radix Bucket Number Contents 0 301, 201, 002, 102 1 310, 111, 213, 013 2 120, 222, 023, 323 3 130, 330, 231, 032 301, 201, 002, 102, 310, 111, 213, 013, 120, 222, 023, 323, 130, 330, 231,032
Radix sort Radix Bucket Number Contents 0 002, 013, 023, 032 1 102, 111, 120, 130 2 201, 213, 222, 231 3 301, 310, 323, 330
Radix sort Radix Ví d 1: A= [701, 1725, 999, 9170, 3252, 4518, 7009, 1424]. Dãy ban u SX theo SX theo SX theo SX theo hàng ơn v hàng trăm hàng ch c hàng nghìn 9170 0701 7009 0701 0701 0701 7009 9170 0999 1725 3252 4518 3252 1424 0999 1424 1424 1424 1725 9170 1725 1725 4518 3252 3252 4518 3252 0701 4518 4518 0999 9170 1725 7009 7009 7009 0999 0999 9170 1424
Radix sort Radix ánh giá thu t toán: - V i m t dãy n s , m i s có t i a m ch s , thu t toán th c hi n m l n các thao tác phân Bucket và ghép Bucket. - Trong thao tác phân Bucket, m i ph n t ch ư c xét úng m t l n, khi ghép cũng v y. - Như v y, chi phí cho vi c th c hi n thu t toán hi n nhiên là O(2m*n) = O(n).

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.