Sắp xếp chọn
Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm


Bài hoặc đoạn này cần được wiki hóa theo các quy cách định dạng và văn phong Wikipedia. Xin hãy giúp phát triển bài này bằng cách liên kết trong đến các mục từ thích hợp khác.

Sắp xếp chọn




Thông tin chung

Phân loại:
Thuật toán sắp xếp

Cấu trúc dữ liệu:
Ngẫu nhiên

Phức tạp thời gian:
Trung bình O(n2)

Phức tạp dữ liệu:
Không tốn thêm vùng nhớ

Tối ưu:
Thỉnh thoảng



Tư tưởng:
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 1 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 tiến hành như sau:
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í.
Ví dụ: Cho dãy a = (12,2,8,5,1,6,4,15)
12 2 8 5 1 6 4 15
Bước 1: 1 2 8 5 12 6 4 15
Bước 2: 1 2 8 5 12 6 4 15
Bước 3: 1 2 4 5 12 6 8 15
Bước 4: 1 2 4 5 12 6 8 15
Bước 5: 1 2 4 5 6 12 8 15
Bước 6: 1 2 4 5 6 8 12 15
Bước 7: 1 2 4 5 6 8 12 15
Giải thuật:
Void SelectionSort(int a[], int n)
{
int min;
for(int i=0;i {
min=i;
for(int j=i+1;j if(a[j] HoanVi(a[min],a[i]);
}
}