Tìm hiểu về các thuật toán sắp xếp
Giới thiệu
Các thuật toán sắp xếp
1
Nội dung trình bày
•Tiếp cận sắp xếp đơn giản
Sắp xếp chọn
Sắp xếp chèn
Sắp xếp nổi bọt
•
Tiếp cận sắp xếp độ phức tạp O(nlog(n))
•
Tiếp cận sắp xếp độ phức tạp O(nlog(n))
Sắp xếp theo phân đoạn (Quick sort)
Sắp xếp hòa nhập
Sắp xếp vung đống
•Một số tiếp cận khác
Sắp xếp theo cơ số
Sắp xếp hòa nhập hai file lớn
2
Sắp xếp phân đoạn - quicksort
•Ý tưởng
Cho một dãy, chọn một phần tử ở giữa, chia đoạn
thành 2 phần
Chuyển các phần tử nhỏ, hoặc bằng đến trước, các
phần tử lớn hơn về sau
phần tử lớn hơn về sau
Sẽ được nửa đầu bé hơn nửa sau
Lặp lại việc chuyển đổi cho các phần tử nửa đầu, và
nửa sau đến lúc số phần tử là 1
3
Sắp xếp phân đoạn – quicksort (t)
•Thuật toán ban đầu là chia: cố gắng chia thành
hai đoạn khác nhau
•Trị: thực hiện các thuật toán sắp xếp trên các
đoạn con
•
Thực hiện kết hợp: thuật toán tự kết hợp kết
•
Thực hiện kết hợp: thuật toán tự kết hợp kết
quả
4
Sắp xếp phân đoạn – quicksort (t)
•Phân đoạn
Chọn một phần tử chốt x (đầu tiên)
Duyệt từ vị trí tiếp theo sang phải tìm vị trí phần tử
đầu tiên >= x, i
Duyệt từ phải sang trái, tìm vị trí phần tử đầu tiên
Duyệt từ phải sang trái, tìm vị trí phần tử đầu tiên
<x, j
Nếu i<j thì hoán đổi vị trí
Tiếp tục đến lúc j<i
5
Sắp xếp phân đoạn – quicksort (t)
•Thuật toán: partition
•Input: A[l..r], l,r: đoạn cần phân chia
•Ouput: A[l..r], i chi số phân chia
1. X=a[l]
2.
i=l+1;
2.
i=l+1;
3. J=r;
4. While (i<j)
a. While (i<j && a[i]<x) i++
b. While (j>=i && a[j]>=x) j—
c. If(i<j) swap(a[i],a[j])
5. Swap(a[l],a[j])
6. Return j; 6
có thể bạn quan tâm
Tìm hiểu về thuật toán và thuật giải
97
2.183
452
Cơ sở dữ liệu
97
(New)
Đề tài: đánh giá hiện trạng sản xuất rau an toàn tại TP.Long Xuyên tỉn...
85
904
290
Thạc sĩ cao học
85
(New)
Tìm hiểu về kỹ thuật Radio over Fiber- Kết hợp kĩ thuật Radio over Fib...
80
1.415
569
Kỹ thuật
80
(New)
TỔNG QUAN MỘT SỐ KĨ THUẬT ĐIỀU CHẾ SỐ, TỔNG QUAN MỘT SỐ KĨ THUẬT ĐIỀU...
66
874
450
Kỹ thuật
66
(New)
Luận văn: Tính hiệu lực, tính đầy đủ trong bằng chứng kiểm toán và các...
43
742
307
Kinh tế quản lý
43
(New)
Lý luận chung về bằng chứng kiểm toán, tính hiệu lực, tính đầy đủ tron...
43
752
330
Kinh tế quản lý
43
(New)
Luận văn thạc sĩ: Tìm hiểu các đặc trưng của ảnh vân tay và hệ thống n...
23
971
450
Thạc sĩ cao học
23
(New)
Khái niệm phân tập và kỹ thuật phân tập đa người dùng, kỹ thuật OFDM,...
62
839
606
Kỹ thuật
62
(New)
thông tin tài liệu
Tài liệu cung cấp một cái nhìn khách quan về các thuật toán sắp xếp
Mở rộng để xem thêm
từ khóa liên quan
tài liệu mới trong mục này
tài liệu hot trong mục này
tài liệu giúp tôi
Nếu bạn không tìm thấy tài liệu mình cần có thể gửi yêu cầu ở đây để chúng tôi tìm giúp bạn!
xem nhiều trong tuần
Giáo trình Quản trị học của Đại học kinh tế quốc dân
4 đề thi học sinh giỏi Toán lớp 2, có đáp án kèm theo
Mẫu slide thuyết trình về Golf
Luận văn về các tác nhân ảnh hưởng đến kết quả học tập của sinh viên chính quy trường Đại Học Kinh Tế- TP HCM
Bài tập ôn tập cuối tuần lớp 3: Tuần 21
Bài tập ôn tập cuối tuần lớp 2: Tuần 21
yêu cầu tài liệu
Giúp bạn tìm tài liệu chưa có
×
