Sắp xếp lựa chọn Java tìm mục nhỏ nhất trong danh sách và di chuyển giá trị đó đến đầu danh sách. Điều này xảy ra lặp đi lặp lại cho đến khi mọi phần tử trong danh sách đầu tiên đã được sắp xếp. Sắp xếp lựa chọn trả về danh sách đã sắp xếp.
Làm thế nào để bạn sắp xếp một danh sách trong Java? Bạn có một vài lựa chọn. Một tùy chọn phổ biến là sắp xếp lựa chọn.
Trong hướng dẫn này, chúng ta sẽ nói về các loại lựa chọn là gì và cách chúng hoạt động. Chúng tôi cũng sẽ hướng dẫn cách tạo một loại lựa chọn trong Java để bạn biết cách tạo một loại lựa chọn của riêng mình. Hãy bắt đầu!
Sắp xếp lựa chọn Java là gì?
Sắp xếp lựa chọn lặp đi lặp lại tìm mục tối thiểu trong danh sách và di chuyển nó lên đầu các mục chưa được sắp xếp trong danh sách. Quá trình này lặp lại đối với mọi mục trong danh sách cho đến khi danh sách được sắp xếp thứ tự.
Mục đầu tiên trong danh sách được coi là mục nhỏ nhất. Mục này được so sánh với phần tử tiếp theo. Nếu phần tử tiếp theo nhỏ hơn, các phần tử sẽ hoán đổi. Thuật toán này tìm phần tử tối thiểu cho đến khi đạt đến phần tử cuối cùng. Sau đó, chương trình của chúng tôi chuyển mục nhỏ nhất lên đầu danh sách.
Trong cách sắp xếp lựa chọn, một danh sách chứa hai phần:danh sách đã sắp xếp và danh sách chưa được sắp xếp. Khi các phần tử được sắp xếp, chúng sẽ di chuyển từ mảng con chưa được sắp xếp sang mảng con đã được sắp xếp.
Bạn có thể sắp xếp một danh sách theo thứ tự tăng dần hoặc giảm dần.
Khi nào bạn nên sử dụng sắp xếp lựa chọn?
Sắp xếp lựa chọn là tối ưu khi bạn cần sắp xếp một danh sách nhỏ. Điều này là do có nhiều cách hiệu quả hơn để sắp xếp các danh sách lớn. Các thuật toán, chẳng hạn như sắp xếp hợp nhất, sắp xếp chèn và sắp xếp nhanh, hiệu quả hơn so với sắp xếp lựa chọn trong lập trình Java.
81% người tham gia cho biết họ cảm thấy tự tin hơn về triển vọng công việc công nghệ của mình sau khi tham gia một cuộc thi đào tạo. Kết hợp với bootcamp ngay hôm nay.
Sinh viên tốt nghiệp bootcamp trung bình đã dành ít hơn sáu tháng để chuyển đổi nghề nghiệp, từ khi bắt đầu bootcamp đến khi tìm được công việc đầu tiên của họ.
Sắp xếp lựa chọn hoạt động tốt nhất khi việc kiểm tra tất cả các phần tử của mảng là bắt buộc. Đây sẽ là trường hợp nếu ít hoặc không có mục nào trong danh sách được sắp xếp. Sắp xếp lựa chọn thường tốt hơn sắp xếp bong bóng, dễ hiểu hơn.
Cách sắp xếp lựa chọn hoạt động?
Không có ích lợi gì khi cố gắng triển khai một thuật toán trong Java mà trước tiên không biết chúng ta muốn thuật toán của mình làm gì. Hãy bắt đầu bằng cách xem qua các bước mà sắp xếp lựa chọn thực hiện để sắp xếp danh sách theo thứ tự.
Hãy xem xét mảng không được sắp xếp sau:
| 17 | 14 | 9 | 12 |
Sắp xếp lựa chọn đặt mục đầu tiên là mục nhỏ nhất trong danh sách. Đây là giá trị tạm thời thay đổi mỗi khi chương trình của chúng tôi thực hiện so sánh. Giá trị này được lưu trữ trong biến riêng của nó.
| Minimum =17 | | | |
| 17 | 14 | 9 | 12 |
Mục "tối thiểu" được so sánh với phần tử thứ hai. Phần tử này nằm trong phần chưa được sắp xếp của mảng; mọi phần tử sau các phần tử đã sắp xếp đều không được sắp xếp.
Giả sử phần tử thứ hai nhỏ hơn mục "tối thiểu". Trong trường hợp này, giá trị của mục "tối thiểu" được đặt thành giá trị của mục thứ hai. 14 nhỏ hơn 17, vì vậy giá trị nhỏ nhất mới của chúng ta trở thành 14.
| Minimum =14 | | | |
| 17 | 14 | 9 | 12 |
Quá trình này lặp lại cho từng mục trong danh sách của chúng tôi. 9 nhỏ hơn 14. Vì vậy, giá trị của "tối thiểu" trở thành 9. 9 không nhỏ hơn 12, vì vậy giá trị của tối thiểu không đổi.
Sau một lần lặp lại, danh sách của chúng tôi nhận thấy rằng 9 là số nhỏ nhất. Mục này được chuyển đến đầu danh sách:
| 9 | 17 | 14 | 12 |
Quá trình này bắt đầu lại từ phần tử chưa được sắp xếp đầu tiên. Vì vậy, tập hợp so sánh tiếp theo của chúng tôi sẽ bắt đầu với 17:
- 17 là mức tối thiểu.
- Chương trình của chúng tôi so sánh 17 với 14. Giá trị "tối thiểu" trở thành 14.
- Chương trình của chúng tôi so sánh 14 là với 12. Giá trị của "tối thiểu" trở thành 12.
- Chương trình của chúng tôi chuyển 12 đến cuối các mục được sắp xếp trong danh sách.
Danh sách của chúng tôi trông giống như sau:
| 9 | 12 | 17 | 14 |
Quá trình này lặp lại cho đến khi danh sách của chúng tôi được đặt hàng. Khi thuật toán của chúng tôi kết thúc quá trình thực thi, danh sách sau được trả về:
| 9 | 12 | 14 | 17 |
Danh sách của chúng tôi được sắp xếp theo thứ tự tăng dần.
Cách tạo Sắp xếp Lựa chọn trong Java
Đó là một điều cần biết cách sắp xếp lựa chọn hoạt động; đó là cách khác để xây dựng một cái. Hãy viết mã một loại lựa chọn trong Java sử dụng logic mà chúng ta đã thảo luận trong phần hướng dẫn.
Thiết lập chương trình
Tạo một tệp có tên là selection_sort.java. Chúng tôi sẽ bắt đầu bằng cách nhập thư viện Mảng Java vào mã của chúng tôi:
import java.util.Arrays;
Chúng tôi sử dụng thư viện này sau đó trong mã của chúng tôi. Chúng tôi sử dụng nó để chuyển đổi mảng đã sắp xếp của chúng tôi thành một chuỗi để chúng tôi có thể in nó ra bảng điều khiển.
Tạo một chức năng sắp xếp
Tiếp theo, chúng ta sẽ khai báo một lớp và tạo một phương thức thực hiện việc sắp xếp lựa chọn của chúng ta. Thêm phần sau vào select_sort.java của bạn tệp:
class SelectionSort {
void sortNumbers(int array[]) {
int size = array.length;
for (int item = 0; item < size - 1; item++) {
int minimum = item;
for (int number = minimum + 1; number < size; number++) {
if (array[number] < array[minimum]) {
minimum = number;
}
}
int temporary = array[item];
array[item] = array[minimum];
array[minimum] = temporary;
}
}
}
Trong lớp của chúng tôi, chúng tôi đã định nghĩa một phương thức có tên là sortNumbers thực hiện sắp xếp của chúng tôi. Chúng tôi bắt đầu bằng cách tính độ dài của mảng của chúng tôi. Chúng tôi lưu trữ độ dài của mảng của chúng tôi trong một biến Java.
Sau đó, chúng tôi tạo một vòng lặp Java for. Vòng lặp này lặp lại qua mọi mục trong danh sách của chúng tôi. Bên trong vòng lặp for này, chúng tôi tìm thấy mục tối thiểu, là mục đầu tiên trong danh sách.
Sau đó, chúng tôi bắt đầu một vòng lặp for khác để so sánh mục tối thiểu với mọi mục trong danh sách.
Nếu số mà vòng lặp for đang đọc nhỏ hơn số tối thiểu, giá trị của "tối thiểu" sẽ trở thành số đó. Trong vòng lặp của chúng tôi, "số" đại diện cho giá trị chỉ mục của số mà chúng tôi đang so sánh với giá trị nhỏ nhất.
Khi số tối thiểu đã được so sánh với mọi số trong danh sách, vòng lặp for bên trong của chúng ta sẽ dừng lại. Sau đó, số tối thiểu được di chuyển sau tất cả các số được sắp xếp trong danh sách.
Gọi hàm sắp xếp
Mã của chúng tôi chưa thực hiện bất cứ điều gì. Chúng tôi vẫn chưa gọi lớp của mình và đưa cho lớp đó một danh sách để sắp xếp.
Bên dưới Số phân loại trong danh sách, thêm mã sau:
public static void main(String args[]) {
int[] toSort = { 17, 14, 9, 12 };
SelectionSort newSort = new SelectionSort();
newSort.sortNumbers(toSort);
System.out.println(Arrays.toString(toSort));
}
Bên trong phương thức chính của chúng tôi, chúng tôi đã khai báo một danh sách các mục để sắp xếp được gọi là toSort . Sau đó, chúng tôi khởi tạo một thể hiện của lớp SelectionSort được gọi là newSort. Chúng tôi sử dụng điều này để gọi Số sắp xếp của chúng tôi phương thức sắp xếp các giá trị trong mảng toSort.
Sau khi phương thức sortNumbers được thực thi, chúng tôi in mảng đã sắp xếp ra bảng điều khiển. Chúng tôi thực hiện việc này bằng cách sử dụng Arrays.toString () phương thức này chuyển đổi mảng của chúng ta thành một danh sách các chuỗi.
Hãy chạy mã của chúng tôi:
[9, 12, 14, 17]
Danh sách của chúng tôi đã được sắp xếp!
Sắp xếp theo lựa chọn Java:Sắp xếp các giá trị theo thứ tự giảm dần
Điều đáng chú ý là bạn có thể sắp xếp các giá trị theo thứ tự giảm dần. Để làm như vậy, hãy thay thế dòng mã sau trong Số sắp xếp của bạn phương pháp:
if (array[number] < array[minimum]) { Với mã này:
if (array[number] > array[minimum]) { Mã này kiểm tra xem giá trị "tối thiểu" có lớn hơn giá trị đang được truy cập bởi vòng lặp for hay không. Điều này có nghĩa là giá trị "tối thiểu" sẽ phản ánh giá trị cao nhất trong danh sách thay vì giá trị thấp nhất.
Để tránh nhầm lẫn, bạn nên đổi tên "tối thiểu" thành "tối đa", nếu bạn đang sắp xếp danh sách theo thứ tự giảm dần.
Bạn đã hoàn thành nó. Bạn đã sắp xếp một danh sách trong Java bằng thuật toán sắp xếp lựa chọn.
Độ phức tạp của Sắp xếp Lựa chọn Java là gì?
Có ba mức độ phức tạp về thời gian mà chúng ta cần xem xét khi đánh giá một thuật toán:trường hợp tốt nhất, trường hợp xấu nhất và trường hợp trung bình.
Loại lựa chọn có độ phức tạp tốt nhất, trung bình và trường hợp xấu nhất là O (n ^ 2). Điều này có nghĩa là thuật toán sẽ mất nhiều thời gian hơn theo cấp số nhân khi số lượng các mục trong danh sách tăng lên.
Bạn có bị bối rối bởi sự phức tạp của các thuật toán không? Hãy xem loạt bài gồm hai phần của chúng tôi trên Big O Notation. Đây là ký hiệu chúng tôi sử dụng để mô tả độ phức tạp của các thuật toán.
Kết luận
Sắp xếp lựa chọn là một phương pháp hiệu quả để sắp xếp danh sách dữ liệu. Chúng hoạt động bằng cách chọn mục nhỏ nhất từ danh sách chưa được sắp xếp và chuyển mục đó lên đầu danh sách chưa được sắp xếp. Quá trình này lặp lại cho đến khi danh sách được sắp xếp.
Bạn có muốn trở thành một nhà phát triển Java? Xem hướng dẫn Cách học Java của chúng tôi. Bạn sẽ tìm thấy các mẹo học tập hàng đầu và lời khuyên về các khóa học trực tuyến và tài nguyên học tập tốt nhất trong hướng dẫn này.