Thuật toán selection sort c++

      37
1. Overview (Tổng Quan)

Là một lập trình viên hẳn những bạn ai cũng đã từng phải áp dụng thuật toán sắp đến xếp. Vào SERI về thuật toán tìm kiếm này bọn họ sẽ tò mò tư tưởng của những loại thuật toán sắp xếp cơ bản nhất: Bubble Sort, Insertion Sort, Merge Sort, Heap Sort, QuickSort, Radix Sort, Counting Sort, Bucket Sort, ShellSort. Trong nội dung bài viết này mình bọn họ sẽ tò mò về Selection Sort :

Thuật toán Selection Sort là gì?Các thành phần bao gồm của thuật toán Selection Sort.

Bạn đang xem: Thuật toán selection sort c++

Cách xúc tiến thuật toán Selection Sort qua ví dụ.

Toàn bộ ví dụ bản thân sẽ thực hiện python giúp các bạn dễ hiểu với dễ nỗ lực bắt. Let"s vì chưng it ^^

2. Selection Sort (Sắp Xếp Chọn)

Thuật toán Selection Sort bố trí một mảng bằng phương pháp liên tục tra cứu phần tử nhỏ nhất (xét theo máy tự tăng dần) trường đoản cú phần không được sắp xếp với đặt nó ở đầu. Thuật toán bảo trì hai mảng nhỏ trong một mảng độc nhất vô nhị định.

Mảng nhỏ đã được chuẩn bị xếp.

Xem thêm: Tài Liệu Chi Tiết Máy Chọn Lọc, Giao Trinh Chi Tiet May Pdf

Mảng con còn sót lại chưa được sắp xếp.

Trong mỗi lần lặp lại sắp xếp lựa chọn, phần tử tối thiểu (xét theo lắp thêm tự tăng dần) từ mảng con không được sắp xếp sẽ tiến hành chọn với chuyển cho mảng nhỏ đã sắp đến xếp.

Ví dụ sau giải thích công việc trên:

//Dãy không sắp xếparr<> = 64 25 12 22 11// tìm phần tử nhỏ bé nhất trong dãy arr<0...4>// đưa bộ phận đó lên đầu dãy arr<0...4>**11** 25 12 22 64// search phần tử bé nhất trong hàng arr<1...4>// đưa bộ phận đó lên đầu hàng arr<1...4>11 **12** 25 22 64// kiếm tìm phần tử bé bỏng nhất trong hàng arr<2...4>// đưa phần tử đó lên đầu dãy arr<2...4>11 12 **22** 25 64// search phần tử bé nhất trong hàng arr<3...4>// đưa bộ phận đó lên đầu hàng arr<3...4>11 12 22 **25** 64 Dưới đó là sơ vật khối theo từng bước triển khai của thuật toán trên

*

Dưới đó là cách thiết lập thuật toán bằng ngôn từ Python:

import sysA = <64, 25, 12, 22, 11> for i in range(len(A)): # kiếm tìm kiếm phần tử nhỏ xíu nhất vào dãy không được sắp xếp min_idx = i for j in range(i+1, len(A)): if A > A: min_idx = j # Đổi địa điểm phần tử bé nhất với phần tử đầu tiên A, A = A, A # chạy thử Kết Quảprint ("Sorted array")for i in range(len(A)): print("%d" %A), Đây là kết quả

Sorted array: 11 12 22 25 64Thuật toán Selection Sort là một trong thuật toán khá dễ dàng khi mua đặt. Thuật toán này có độ phức hợp là O(n2) vì có 2 vòng lặp.

3. Conclusion (Kết Luận)

Trong nội dung bài viết này chúng ta đã tìm hiểu được thuật toán thu xếp chọn (Selection Sort). Bao gồm cài chú ý tổng quan liêu về thuật toán. Cách thiết lập thuật toán bằng ngữ điệu Python. Độ thức tạp thuật toán. Rất ao ước đã đem lại cho bạn đọc những kỹ năng thú vị.Nếu thấy hay chúng ta nhớ bấm follow mình nhé !!