Lựa chọn Sắp xếp theo Java Chương trình có ví dụ
James Hartman
⚡ Tóm tắt thông minh
Sắp xếp chọn trong Java Thuật toán liên tục quét phần chưa được sắp xếp của mảng, tìm giá trị nhỏ nhất còn lại và hoán đổi nó vào vị trí, hoàn thành công việc với tối đa n-1 lần hoán đổi bất kể thứ tự đầu vào.
Sắp xếp lựa chọn hoạt động như thế nào?
Sắp xếp lựa chọn thực hiện một thuật toán sắp xếp đơn giản như sau:
- Thuật toán liên tục tìm kiếm phần tử thấp nhất.
- Hoán đổi phần tử hiện tại với phần tử có giá trị thấp nhất
- Với mỗi lần lặp/chuyển sắp xếp lựa chọn, các phần tử sẽ được hoán đổi.
Do đó, mỗi lượt xử lý đều xử lý mảng Dữ liệu được chia thành hai vùng: một khối đã được sắp xếp phát triển từ bên trái và một khối chưa được sắp xếp thu hẹp dần về bên phải. Thuật toán sẽ duyệt qua khối chưa được sắp xếp, ghi nhớ chỉ số của giá trị nhỏ nhất gặp được và hoán đổi giá trị đó với vị trí đầu tiên trong khối chưa được sắp xếp.
Vì mỗi lượt chỉ có một lần hoán đổi diễn ra, nên một mảng gồm n phần tử sẽ được sắp xếp sau tối đa n-1 lần hoán đổi. Đặc tính đó là điều làm nên sự khác biệt giữa thuật toán này với các thuật toán cấp độ người mới bắt đầu khác. Java Các thuật toán sắp xếp, vốn di chuyển dữ liệu thường xuyên hơn nhiều.
tracVí dụ bên dưới hiển thị mảng mẫu {860, 8, 200, 9} chính xác như chương trình trong phần tiếp theo in ra khi chạy.
| Qua | So sánh được in | Giá trị nhỏ nhất được tìm thấy | Mảng sau khi hoán đổi |
|---|---|---|---|
| Bắt đầu | - | - | 860 8 200 9 |
| 1 | 860 và 8, 8 và 200, 8 và 9 | 8 | 8 860 200 9 |
| 2 | 860 và 200, 200 và 9 | 9 | 8 9 200 860 |
| 3 | 200 và 860 | 200 | 8 9 200 860 |
Có hai chi tiết trong đó tracCó hai điểm đáng chú ý. Thứ nhất, lượt chạy thứ 3 vẫn báo cáo việc hoán đổi mặc dù thứ tự không thay đổi, bởi vì giá trị nhỏ nhất còn lại đã nằm ở chỉ mục hiện tại và chương trình hoán đổi phần tử với chính nó. Thứ hai, số lượng phép so sánh giảm đi một trong mỗi lượt chạy (ba, sau đó hai, rồi một), đây là quy luật đằng sau các số liệu về độ phức tạp ở phần dưới trang.
Java Chương trình thực hiện Sắp xếp lựa chọn
Lớp bên dưới có tên là SelectionSortAlgo và nằm trong gói com.guru99. Phương thức main() khai báo mảng mẫu, in ra, chuyển nó cho phương thức selection() để sắp xếp, và in lại. Phương thức trợ giúp printArray() ghi tất cả các phần tử trên một dòng duy nhất, đó là điều tạo ra nhật ký từng bước dễ đọc.
Bên trong hàm selection(), vòng lặp ngoài đánh dấu ranh giới giữa vùng đã sắp xếp và vùng chưa sắp xếp, biến index lưu giữ vị trí của giá trị nhỏ nhất đã thấy cho đến nay, và ba phép gán ở cuối mỗi lượt thực hiện việc hoán đổi.
package com.guru99; public class SelectionSortAlgo { public static void main(String a[]) { int[] myArray = {860,8,200,9}; System.out.println("------Before Selection Sort-----"); printArray(myArray); selection(myArray);//sorting array using selection sort System.out.println("-----After Selection Sort-----"); printArray(myArray); } public static void selection(int[] array) { for (int i = 0; i < array.length - 1; i++) { System.out.println("Sort Pass Number "+(i+1)); int index = i; for (int j = i + 1; j < array.length; j++) { System.out.println("Comparing "+ array[index] + " and " + array[j]); if (array[j] < array[index]){ System.out.println(array[index] + " is greater than " + array[j] ); index = j; } } int smallerNumber = array[index]; array[index] = array[i]; array[i] = smallerNumber; System.out.println("Swapping Elements: New Array After Swap"); printArray(array); } } static void printArray(int[] array){ for(int i=0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
Đầu ra:
Việc biên dịch và chạy lớp sẽ tạo ra nhật ký console bên dưới, với một khối đầu ra cho mỗi lần chạy.
------Before Selection Sort----- 860 8 200 9 Sort Pass Number 1 Comparing 860 and 8 860 is greater than 8 Comparing 8 and 200 Comparing 8 and 9 Swapping Elements: New Array After Swap 8 860 200 9 Sort Pass Number 2 Comparing 860 and 200 860 is greater than 200 Comparing 200 and 9 200 is greater than 9 Swapping Elements: New Array After Swap 8 9 200 860 Sort Pass Number 3 Comparing 200 and 860 Swapping Elements: New Array After Swap 8 9 200 860 -----After Selection Sort----- 8 9 200 860
Có hai vấn đề mà người mới bắt đầu thường gặp phải khi chạy ví dụ này lần đầu tiên. Bởi vì tệp này khai báo... package com.guru99;Nguồn phải nằm trong một khu vực phù hợp. com/guru99 nếu không, trình biên dịch sẽ báo lỗi không khớp tên gói hoặc tên lớp. Khi đó, lớp phải được khởi chạy bằng tên đầy đủ của nó. java com.guru99.SelectionSortAlgo, bởi vì đơn giản java SelectionSortAlgo Gây ra lỗi NoClassDefFoundError.
Giới hạn vòng lặp là một cạm bẫy phổ biến khác. Vòng lặp ngoài dừng lại ở array.length - 1 và vòng lặp bên trong bắt đầu từ i + 1Việc thay đổi bất kỳ ranh giới nào đều tạo ra một lượt truyền dữ liệu trống bổ sung hoặc một ngoại lệ ArrayIndexOutOfBoundsException.
Độ phức tạp về thời gian và không gian của thuật toán sắp xếp chọn
Vòng lặp bên trong chương trình luôn chạy đến cuối mảng, vì vậy thuật toán thực hiện cùng số phép so sánh bất kể dữ liệu trông như thế nào. Đối với một mảng gồm n phần tử, tổng số phép so sánh là n(n-1)/2, đối với mẫu bốn phần tử thì bằng sáu, và kết quả đầu ra ở trên thực sự in ra chính xác sáu dòng "Comparing".
| Khay | So sánh | Hoán đổi | Thời gian phức tạp | Không gian phụ trợ |
|---|---|---|---|---|
| Tốt nhất (mảng đã được sắp xếp) | n (n-1) / 2 | n-1 | O (n²) | O (1) |
| Trung bình (thứ tự ngẫu nhiên) | n (n-1) / 2 | n-1 | O (n²) | O (1) |
| Tệ nhất (sắp xếp ngược) | n (n-1) / 2 | n-1 | O (n²) | O (1) |
Từ dãy số đồng đều đó, có ba hệ quả sau:
- Thuật toán sắp xếp chọn không thích ứng. Đầu vào đã được sắp xếp có chi phí chính xác bằng đầu vào đảo ngược, vì vậy không có lối tắt thoát sớm nào như vậy. phân loại bong bóng cung cấp.
- Điểm mạnh của thuật toán này là số lần hoán đổi. Tối đa chỉ có n-1 lần hoán đổi diễn ra, ít hơn nhiều so với số bước di chuyển bậc hai mà các thuật toán sắp xếp đơn giản khác có thể thực hiện.
- Việc sử dụng bộ nhớ là hằng số. Chỉ cần bộ đếm vòng lặp và hai biến tạm thời index và smallerNumber, do đó không gian phụ trợ là O(1) và việc sắp xếp diễn ra tại chỗ.
Sự tăng trưởng theo hàm bậc hai là giới hạn thực tế. Việc tăng gấp đôi kích thước mảng sẽ làm tăng gấp bốn lần khối lượng công việc so sánh, vì vậy thuật toán sắp xếp chọn phù hợp hơn cho việc giảng dạy, các mảng nhỏ và mã nhúng hơn là các tập dữ liệu sản xuất, nơi các thuật toán có độ phức tạp O(n log n) là lựa chọn đúng đắn.
Ưu điểm và nhược điểm của thuật toán sắp xếp chọn
Hiểu được thuật toán có ích ở đâu và có hại ở đâu sẽ giúp bạn dễ dàng quyết định khi nào nên sử dụng nó.
Ưu điểm
- Logic này ngắn gọn và dễ đọc, đó là lý do tại sao nó là một bài toán sắp xếp đầu tiên tiêu chuẩn. sắp xếp chèn.
- Nó sắp xếp tại chỗ, do đó không cần cấp phát mảng thứ hai và mức sử dụng bộ nhớ không tăng theo dữ liệu đầu vào.
- Nó thực hiện tối đa n-1 thao tác ghi vào mảng, điều này rất quan trọng đối với các thiết bị lưu trữ mà thao tác ghi chậm hoặc làm hao mòn phương tiện lưu trữ.
- Thời gian chạy của nó hoàn toàn có thể dự đoán được, bởi vì số lần so sánh chỉ phụ thuộc vào độ dài của mảng.
Nhược điểm
- Mỗi trường hợp đều có độ phức tạp O(n²), do đó thuật toán không thể mở rộng quy mô đối với các tập dữ liệu lớn.
- Nó không thể phát hiện một mảng đã được sắp xếp và do đó không bao giờ kết thúc sớm.
- Dạng biểu diễn cổ điển ở trên không ổn định, vì vậy hai giá trị bằng nhau có thể kết thúc ở vị trí ngược lại.
- Nó so sánh thường xuyên hơn thuật toán sắp xếp chèn trên dữ liệu gần như đã được sắp xếp, trong đó thuật toán sắp xếp chèn có thời gian thực hiện gần bằng tuyến tính.
Tóm lại, hãy chọn thuật toán sắp xếp chọn khi mảng nhỏ và mỗi lần ghi đều tốn kém, và tránh sử dụng nó khi tập dữ liệu lớn hoặc đã gần được sắp xếp.
Thuật toán sắp xếp chọn so với thuật toán sắp xếp chọn BubblSo sánh thuật toán sắp xếp e với thuật toán sắp xếp chèn
Cả ba thuật toán đều là thuật toán sắp xếp so sánh tại chỗ bậc hai, nhưng chúng hoạt động khác nhau khi hình dạng của dữ liệu đầu vào thay đổi.
| Tiêu chí | Sắp xếp lựa chọn | Bubblsắp xếp e | Sắp xếp chèn |
|---|---|---|---|
| Thời gian lý tưởng nhất | O (n²) | O (n) | O (n) |
| thời gian trung bình và thời gian tồi tệ nhất | O (n²) | O (n²) | O (n²) |
| Đổi ca hoặc thay ca trong trường hợp xấu nhất | hoán đổi n-1 | n(n-1)/2 hoán đổi | Lên đến n(n-1)/2 ca |
| Ổn định | Không | Có | Có |
| Thích ứng với dữ liệu đầu vào đã được sắp xếp | Không | Có | Có |
| Không gian phụ trợ | O (1) | O (1) | O (1) |
| Sử dụng điển hình | Số lần ghi tối thiểu cần thiết | Dạy và nhận biết dữ liệu đã được sắp xếp | Mảng nhỏ hoặc gần như đã được sắp xếp |
Bảng dưới đây giải thích một câu trả lời phỏng vấn thường gặp. Thuật toán sắp xếp chọn (Selection sort) thắng về số lần hoán đổi, thuật toán sắp xếp nổi bọt (Bubble sort) thắng về khả năng nhận diện dữ liệu đã được sắp xếp, và thuật toán sắp xếp chèn (Insertion sort) thường nhanh nhất trong ba thuật toán này trên thực tế vì dữ liệu thực thường đã được sắp xếp một phần. Không thuật toán nào có thể cạnh tranh với thuật toán sắp xếp trộn (Merge sort) hoặc sắp xếp nhanh (Quicksort) khi mảng có số lượng phần tử vượt quá vài chục.
