Trong hướng dẫn này, bạn sẽ học cách sắp xếp lựa chọn hoạt động. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc về sắp xếp lựa chọn trong C, C ++, Java và Python.
Sắp xếp lựa chọn là một thuật toán chọn phần tử nhỏ nhất từ danh sách chưa được sắp xếp trong mỗi lần lặp và đặt phần tử đó ở đầu danh sách chưa được sắp xếp.
Cách phân loại lựa chọn hoạt động?
- Đặt phần tử đầu tiên là
minimum.
Chọn phần tử đầu tiên là tối thiểu - So sánh
minimumvới yếu tố thứ hai. Nếu phần tử thứ hai nhỏ hơnminimum, hãy gán phần tử thứ hai làminimum.
So sánhminimumvới yếu tố thứ ba. Một lần nữa, nếu phần tử thứ ba nhỏ hơn, thì hãy gánminimumcho phần tử thứ ba nếu không thì không làm gì cả. Quá trình tiếp tục cho đến phần tử cuối cùng.
So sánh tối thiểu với các yếu tố còn lại - Sau mỗi lần lặp lại,
minimumđược đặt ở phía trước của danh sách chưa được sắp xếp.
Đổi cái đầu tiên với tối thiểu - Đối với mỗi lần lặp, lập chỉ mục bắt đầu từ phần tử chưa được sắp xếp đầu tiên. Bước 1 đến bước 3 được lặp lại cho đến khi tất cả các phần tử được đặt vào đúng vị trí của chúng.
Lần lặp đầu tiên Lần lặp 
thứ hai Lần lặp 
thứ ba Lần lặp 
thứ tư
Thuật toán sắp xếp lựa chọn
lựa chọn Sắp xếp (mảng, kích thước) lặp lại (kích thước - 1) lần đặt phần tử chưa được sắp xếp đầu tiên làm giá trị tối thiểu cho mỗi phần tử chưa được sắp xếp nếu phần tử <hiện tại
Ví dụ về Python, Java và C / C ++
Python Java C C ++ # Selection sort in Python def selectionSort(array, size): for step in range(size): min_idx = step for i in range(step + 1, size): # to sort in descending order, change> to < in this line # select the minimum element in each loop if array(i) < array(min_idx): min_idx = i # put min at the correct position (array(step), array(min_idx)) = (array(min_idx), array(step)) data = (-2, 45, 0, 11, -9) size = len(data) selectionSort(data, size) print('Sorted Array in Ascending Order:') print(data)
// Selection sort in Java import java.util.Arrays; class SelectionSort ( void selectionSort(int array()) ( int size = array.length; for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) ( min_idx = i; ) ) // put min at the correct position int temp = array(step); array(step) = array(min_idx); array(min_idx) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( 20, 12, 10, 15, 2 ); SelectionSort ss = new SelectionSort(); ss.selectionSort(data); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Selection sort in C #include // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); printf("Sorted array in Acsending Order:"); printArray(data, size); )
// Selection sort in C++ #include using namespace std; // function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) // function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) ( cout << array(i) << " "; ) cout << endl; ) void selectionSort(int array(), int size) ( for (int step = 0; step < size - 1; step++) ( int min_idx = step; for (int i = step + 1; i to < in this line. // Select the minimum element in each loop. if (array(i) < array(min_idx)) min_idx = i; ) // put min at the correct position swap(&array(min_idx), &array(step)); ) ) // driver code int main() ( int data() = (20, 12, 10, 15, 2); int size = sizeof(data) / sizeof(data(0)); selectionSort(data, size); cout << "Sorted array in Acsending Order:"; printArray(data, size); )
Phức tạp
| Đi xe đạp | Số lượng so sánh |
|---|---|
| Ngày 1 | (n-1) |
| lần 2 | (n-2) |
| lần thứ 3 | (n-3) |
| … | … |
| Cuối cùng | 1 |
Số lần so sánh: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2gần bằng .n2
Độ phức tạp =O(n2)
Ngoài ra, chúng ta có thể phân tích độ phức tạp bằng cách quan sát số vòng lặp. Có 2 vòng lặp nên độ phức tạp là .n*n = n2
Thời gian phức tạp:
- Trường hợp xấu nhất Độ phức tạp: Nếu chúng ta muốn sắp xếp theo thứ tự tăng dần và mảng theo thứ tự giảm dần thì trường hợp xấu nhất sẽ xảy ra.
O(n2) - Độ phức tạp của trường hợp tốt nhất: Nó xảy ra khi mảng đã được sắp xếp
O(n2) - Độ phức tạp trường hợp trung bình: Nó xảy ra khi các phần tử của mảng có thứ tự lộn xộn (không tăng dần cũng không giảm dần).
O(n2)
Độ phức tạp về thời gian của việc sắp xếp lựa chọn là như nhau trong mọi trường hợp. Ở mỗi bước, bạn phải tìm ra phần tử tối thiểu và đặt nó vào đúng vị trí. Phần tử tối thiểu không được biết cho đến khi không đạt đến phần cuối của mảng.
Không gian phức tạp:
Không gian phức tạp là O(1)do một biến phụ tempđược sử dụng.
Ứng dụng Sắp xếp Lựa chọn
Loại lựa chọn được sử dụng khi:
- một danh sách nhỏ sẽ được sắp xếp
- chi phí hoán đổi không thành vấn đề
- kiểm tra tất cả các yếu tố là bắt buộc
- chi phí ghi vào bộ nhớ quan trọng như trong bộ nhớ flash (số lần ghi / hoán đổi
O(n)so với loại bong bóng)O(n2)
