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.152
442
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
887
284
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.391
561
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
853
441
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
712
293
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
730
324
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
951
441
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
820
600
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
Tâm lý xã hội VÀ Hệ tư tưởng
Tham khảo 12 bài tập nguyên lý thống kê có lời giải
4 đề thi học sinh giỏi Toán lớp 2, có đáp án kèm theo
Trắc nghiệm kinh tế
PHÂN TÍCH CHUỖI CUNG ỨNG CỦA COCA COLA VIỆT NAM
Địa lý 12 Phát triển cây công nghiệp lâu năm Tây Nguyên
yêu cầu tài liệu
Giúp bạn tìm tài liệu chưa có
×
