Sắp xếp chèn Java đánh giá từng mục trong danh sách. Nếu một mục ít hơn một mục trước đó, sắp xếp sẽ hoán đổi các mục. Nếu không, các mục sẽ ở cùng một vị trí và hai mục tiếp theo sẽ được so sánh trong danh sách.
Máy tính rất tốt trong việc phân loại danh sách các mục. Bằng cách sử dụng các vòng lặp, bạn có thể tìm kiếm qua tất cả các mục trong danh sách và thay đổi thứ tự của chúng cho đến khi chúng xuất hiện theo một cách nhất định.
Trong lập trình, có một số phương pháp sắp xếp danh sách tiêu chuẩn. Chúng tôi gọi đây là các thuật toán sắp xếp. Thuật toán sắp xếp đọc qua tất cả các mục trong danh sách và sắp xếp chúng bằng cách sử dụng một bộ hướng dẫn cụ thể. Một trong những thuật toán sắp xếp phổ biến nhất mà bạn sẽ gặp là sắp xếp chèn.
Trong hướng dẫn này, chúng ta sẽ thảo luận về cách triển khai thuật toán sắp xếp chèn Java. Chúng tôi sẽ xem qua một ví dụ trong quá trình thực hiện để bạn có thể tìm hiểu cách logic đằng sau cách sắp xếp này hoạt động.
Hãy bắt đầu!
Sắp xếp chèn Java là gì?
Sắp xếp chèn Java hoạt động tương tự như sắp xếp các thẻ trong tay bạn trong trò chơi bài. Sắp xếp chèn kiểm tra từng mục trong danh sách và hoán đổi chúng với một mục ở bên trái của nó. Một mặt hàng có được hoán đổi hay không tùy thuộc vào việc mặt hàng đó lớn hơn hay nhỏ hơn các mặt hàng trước đó.
Hãy tưởng tượng, trong giây lát, bạn đang chơi một trò chơi bài - huýt sáo, xì xào, bất cứ thứ gì. Khi sắp xếp các thẻ của mình, bạn sẽ làm gì?
Bạn sẽ bắt đầu ở bên trái và kiểm tra xem thẻ thứ hai có được sắp xếp hay không. Nếu thẻ đó lớn hơn thẻ cuối cùng, nó sẽ được giữ nguyên ở vị trí cũ. Ngược lại, nó sẽ tăng lên một vị trí trong danh sách.
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ọ.
Bạn sẽ xem qua từng thẻ trong tay và thực hiện thao tác này cho đến khi mọi thẻ xuất hiện theo đúng thứ tự của nó.
Khi nào bạn nên sử dụng sắp xếp chèn?
Sắp xếp chèn được sử dụng nhiều nhất khi chỉ có một số phần tử bên trái cần được sắp xếp.
Có nhiều thuật toán hiệu quả hơn mà bạn có thể sử dụng để sắp xếp danh sách dữ liệu lớn, chẳng hạn như sắp xếp hợp nhất. Đây là lý do tại sao bạn không nên luôn mặc định sử dụng sắp xếp chèn. Như đã nói, sắp xếp chèn hiệu quả hơn sắp xếp bong bóng và sắp xếp lựa chọn khi sắp xếp các phần tử trong danh sách.
Sắp xếp chèn là một thuật toán sắp xếp đơn giản có nghĩa là nó tốt cho người mới bắt đầu học.
Hướng dẫn sắp xếp chèn
Hình dung một bộ bài không phải là cách trực quan nhất trên thế giới. Hãy xem qua một ví dụ lập trình để giúp bạn bắt đầu. Xem xét danh sách sau:
| 8 | 6 | 3 | 9 |
Trong danh sách này, chúng tôi giả sử phần tử đầu tiên đã được sắp xếp.
Bước tiếp theo của chúng tôi là so sánh mục thứ hai trong danh sách của chúng tôi với mục đầu tiên. Nếu mục đầu tiên lớn hơn mục thứ hai, thì mục đó được đặt trước mục đầu tiên.
Trong trường hợp này, 6 lớn hơn 8. Điều này có nghĩa là 6 sẽ lùi lại trong danh sách của chúng ta một vị trí và 8 sẽ di chuyển về phía trước một vị trí:
| 6 | 8 | 3 | 9 |
Bây giờ chúng ta cần so sánh phần tử thứ ba với các phần tử bên trái của nó:3 có lớn hơn 8 không? Không, vì vậy 8 di chuyển vị trí sang phải:
| 6 | 3 | 8 | 9 |
3 có lớn hơn 6 không? Không, vì vậy chúng tôi chuyển số 6:
| 3 | 6 | 8 | 9 |
Bây giờ, chúng ta phải so sánh xem mục thứ tư trong danh sách của chúng ta - mục cuối cùng - có lớn hơn mọi mục khác trong danh sách của chúng tôi hay không. Trong trường hợp này, 9 lớn hơn tất cả các mục đứng trước nó:8, 6 và 3.
Đây là thuật toán mà chúng tôi đã sử dụng để sắp xếp danh sách của mình:
- Phần tử đầu tiên được sắp xếp.
- So sánh mục thứ hai với mục bên trái.
- Nếu mục này lớn hơn giá trị bên trái của nó, mục này vẫn ở vị trí cũ. Nếu không, chúng tôi di chuyển giá trị sang trái.
- Lặp lại cho đến khi tất cả các mục xuất hiện theo thứ tự.
Bây giờ chúng ta có một mảng được sắp xếp. Chèn sắp xếp sắp xếp từng mục một. Hãy thảo luận về cách triển khai thuật toán sắp xếp này trong Java.
Cách thực hiện sắp xếp chèn trong Java
Giá trị cao nhất của hai giá trị đang được so sánh được chèn vào một vị trí bên phải mỗi khi chạy hàm sắp xếp.
Về mặt lý thuyết thì chúng ta đều nói rõ về vấn đề này, nhưng làm thế nào để bạn triển khai nó trong Java? Đó là một câu hỏi hay. Hãy viết một lớp thực hiện sắp xếp chèn vào danh sách các điểm của sinh viên.
Chuẩn bị Thư viện Mảng
Hãy bắt đầu bằng cách nhập thư viện Mảng vào chương trình Java của chúng tôi. Chúng tôi sẽ sử dụng thư viện này để in danh sách của mình ra bảng điều khiển sau khi chúng tôi đã sắp xếp xong:
import java.util.Arrays;
Khai báo một phương pháp sắp xếp
Chúng tôi sẽ bắt đầu bằng cách khai báo một phương pháp đi qua danh sách của chúng tôi và sắp xếp dữ liệu của chúng tôi theo thứ tự tăng dần :
class SortGrades {
public static void insertionSort(int [] numbersToSort) {
int itemCount = numbersToSort.length;
for (int value = 1; value < itemCount; value++) {
int key = numbersToSort[value];
int last = value - 1;
while (last >= 0 && key < numbersToSort[last]) {
numbersToSort[last + 1] = numbersToSort[last];
--last;
}
numbersToSort[last + 1] = key;
}
}
}
Chúng tôi bắt đầu bằng cách tìm ra có bao nhiêu mục trong mảng đầu vào của chúng tôi. Điều này cho phép chúng tôi tạo một vòng lặp đi qua mọi mục trong danh sách của chúng tôi. Chúng tôi khởi tạo một vòng lặp for sẽ lặp lại cho đến khi chúng tôi sắp xếp danh sách của mình.
Trong vòng lặp for của chúng tôi, chúng tôi đã khai báo hai biến:key và last.
Biến Java "khóa" theo dõi mục mà chúng tôi hiện đang phân loại. Biến "cuối cùng" theo dõi số lượng mục phải được sắp xếp ở bên trái của mục.
Chương trình của chúng tôi sẽ so sánh giá trị của “key” với từng phần tử ở bên trái của nó cho đến khi chúng tôi tìm thấy một phần tử nhỏ hơn. Điều này xảy ra trong vòng lặp Java “while” của chúng tôi.
Xác định chức năng chính
Khi chúng tôi chạy mã này, không có gì xảy ra. Đó là bởi vì chúng tôi chưa xác định chức năng chính của mình. Hãy xác định một hàm chính xác định một mảng int (một mảng số). Hàm chính này sử dụng inserttionSort () chúng tôi đã khai báo để sắp xếp các số đó. Dán mã này sau khi khai báo phương thức Java inserttionSort của bạn:
public static void main(String args[]) {
int[] numbers = { 8, 6, 3, 9 };
InsertionSort sortNumbers = new InsertionSort();
sortNumbers.insertionSort(numbers);
String arrayToString = Arrays.toString(numbers);
System.out.println("Sorted list: " + arrayToString);
}
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 số mà chúng tôi muốn sắp xếp. Chúng tôi đã tạo một phiên bản của InsertionSort () của chúng tôi phương thức được gọi là sortNumbers . Chúng tôi sử dụng phương pháp này để sắp xếp danh sách các số của chúng tôi theo thứ tự tăng dần. Phương thức này thay đổi các giá trị bên trong mảng "số" của chúng ta; chúng tôi đã không khai báo một mảng riêng biệt để lưu trữ các giá trị của nó.
Tiếp theo, chúng tôi đã sử dụng Arrays.toString () để chuyển đổi mảng số của chúng ta thành một chuỗi. Chúng tôi in danh sách đã sắp xếp ra bảng điều khiển.
Đánh giá độ phức tạp
Sắp xếp chèn có độ phức tạp chữ hoa chữ thường trung bình là O (n ^ 2). Điều này xảy ra khi không có phần tử nào được sắp xếp.
Trường hợp phức tạp tốt nhất xảy ra nếu một mảng được sắp xếp. Điều này sẽ mang lại độ phức tạp về thời gian là O (n). Điều này là do vòng lặp bên trong trong một sắp xếp chèn sẽ không chạy chút nào trong trường hợp này.
Trong trường hợp xấu nhất, sắp xếp chèn thực hiện tại O (n ^ 2). Điều này xảy ra nếu một mảng theo thứ tự tăng dần hoặc giảm dần và bạn muốn sắp xếp nó theo chiều ngược lại (tức là tăng dần đến giảm dần). Điều này sẽ liên quan đến việc so sánh mọi phần tử với tất cả các phần tử khác.
Kết luận
Sắp xếp chèn là một phương pháp sắp xếp dữ liệu hiệu quả. Chèn sắp xếp so sánh các giá trị bắt đầu với giá trị thứ hai trong danh sách. Nếu giá trị này lớn hơn giá trị bên trái của nó, danh sách của chúng ta không thay đổi. Nếu không, giá trị được di chuyển cho đến khi mục bên trái nhỏ hơn giá trị đó.
Bây giờ bạn đã sẵn sàng để bắt đầu viết thuật toán sắp xếp chèn của riêng mình trong Java! Nếu bạn đang tìm kiếm thêm tài nguyên học Java, hãy xem hướng dẫn Cách học Java của chúng tôi.