Sắp Xếp Chọn – Wikipedia Tiếng Việt

Bước tới nội dung

Nội dung

chuyển sang thanh bên ẩn

• Đầu
• 1 Các bước thực hiện
• 2 Đánh giá
• 3 Xem thêm
• 4 Tham khảo

• Bài viết
• Thảo luận

Tiếng Việt

• Đọc
• Sửa đổi
• Sửa mã nguồn
• Xem lịch sử

Công cụ Công cụ chuyển sang thanh bên ẩn Tác vụ

• Đọc
• Sửa đổi
• Sửa mã nguồn
• Xem lịch sử

Chung

• Các liên kết đến đây
• Thay đổi liên quan
• Trang đặc biệt
• Liên kết thường trực
• Thông tin trang
• Trích dẫn trang này
• Lấy URL ngắn gọn
• Tải mã QR

In và xuất

• Tạo một quyển sách
• Tải dưới dạng PDF
• Bản để in ra

Tại dự án khác

• Wikimedia Commons
• Khoản mục Wikidata

Giao diện chuyển sang thanh bên ẩn Bách khoa toàn thư mở Wikipedia

Bài này không có nguồn tham khảo nào. Mời bạn giúp cải thiện bài bằng cách bổ sung các nguồn tham khảo đáng tin cậy. Các nội dung không nguồn có thể bị nghi ngờ và xóa bỏ. Nếu bài được dịch từ Wikipedia ngôn ngữ khác thì bạn có thể chép nguồn tham khảo bên đó sang đây. (tháng 10/2021) (Tìm hiểu cách thức và thời điểm xóa thông báo này)

Sắp xếp chọn

Phân loại	Thuật toán sắp xếp
Cấu trúc dữ liệu	Ngẫu nhiên
Hiệu suất trường hợp tệ nhất	Trung bình O ( n 2 ) {\displaystyle O(n^{2})}
Độ phức tạp không gian trường hợp tệ nhất	Không tốn thêm vùng nhớ
Tối ưu	Thỉnh thoảng

Sắp xếp chọn là một thuật toán sắp xếp đơn giản, dựa trên việc so sánh tại chỗ.

Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu tiên của dãy hiện hành. Sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn n-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2. Lặp lại quá trình trên cho dãy hiện hành đến khi dãy hiện hành chỉ còn một phần tử. Dãy ban đầu có n phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy.

Các bước thực hiện

[sửa | sửa mã nguồn]

• Bước 1: i=1.
• Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n].
• Bước 3: Hoán vị a[min] và a[i]
• Bước 4: Nếu i<=n-1 thì i=i+1; Lặp lại bước 2.
• Ngược lại: Dừng. n-1 phần tử đã nằm ở đúng vị trí.

Đánh giá

[sửa | sửa mã nguồn]

• Thuật toán ít phải đổi chỗ các phần tử nhất trong số các thuật toán sắp xếp(n lần hoán vị) nhưng có độ phức tạp so sánh là O(n2) (n2/2 phép so sánh).
• Thuật toán tốn thời gian gần như bằng nhau đối với mảng đã được sắp xếp cũng như mảng chưa được sắp xếp.

Xem thêm

[sửa | sửa mã nguồn]

• Sắp xếp nổi bọt
• Sắp xếp nhanh
• Sắp xếp chèn
• Sắp xếp topo
• Sắp xếp trộn
• Sắp xếp vun đống

Tham khảo

[sửa | sửa mã nguồn]

x t s Thuật toán sắp xếp
Lý thuyết	Độ phức tạp thuật toán | Ký hiệu O lớn | Thứ tự toàn phần | Danh sách | Sắp xếp so sánh
Sắp xếp đổi chỗ	Sắp xếp nổi bọt | Sắp xếp cốc tai | Sắp xếp chẵn lẻ | Sắp xếp răng lược | Sắp xếp gnome | Sắp xếp nhanh
Sắp xếp chọn	Sắp xếp chọn | Sắp xếp vun đống
Sắp xếp chèn	Sắp xếp chèn | Sắp xếp Shell | Sắp xếp bằng cây | Sắp xếp thư viện | Patience sorting
Sắp xếp trộn	Sắp xếp trộn | Strand sort
Sắp xếp không so sánh	Sắp xếp theo cơ số | Sắp xếp thùng | Sắp xếp đếm | Sắp xếp chuồng bồ câu | Burstsort | Bead sort
Các loại khác	Sắp xếp topo | Mạng sắp xếp | Bitonic sorter | Pancake sorting | Bogosort | Stooge sort

Bài viết này vẫn còn sơ khai. Bạn có thể giúp Wikipedia mở rộng nội dung để bài được hoàn chỉnh hơn. x t s

Lấy từ “https://vi.wikipedia.org/w/index.php?title=Sắp_xếp_chọn&oldid=70961462” Thể loại:

• Thuật toán sắp xếp

Thể loại ẩn:

• Hoàn toàn không có nguồn tham khảo
• Pages using deprecated image syntax
• Tất cả bài viết sơ khai
• Sơ khai