Sắp xếp mảng là một trong những thao tác phổ biến nhất mà người mới bắt đầu sử dụng Java nên biết cách thực hiện. Mặc dù mảng không phải lúc nào cũng là cách thuận tiện nhất để sắp xếp dữ liệu và điều này chủ yếu áp dụng cho các số nhỏ, nhưng khái niệm đằng sau việc sắp xếp mảng có rất nhiều ứng dụng trong khoa học dữ liệu và phần mềm phức tạp. Trong bài đăng này, chúng ta sẽ xem xét kỹ hơn về sắp xếp chèn là gì. Chúng tôi đã bao gồm một số ví dụ và bài toán thực hành để giúp bạn hoàn toàn nắm bắt được khái niệm này.
Chúng ta hãy xem xét kỹ hơn đầu vào và đầu ra của sắp xếp chèn:
Sắp xếp chèn là gì?
Về cơ bản, sắp xếp chèn là một thuật toán mà các nhà phát triển sử dụng để tổ chức các chuỗi số nhỏ. Nó chia tất cả các giá trị thành hai ngăn xếp - một ngăn xếp được sắp xếp và một ngăn xếp chưa được sắp xếp. Lần lượt, các số trong ngăn xếp “chưa sắp xếp” được chọn ra và sắp xếp theo đúng thứ tự.
- Đầu vào: một mảng A với các phần tử số chưa được sắp xếp: A[0,1, n, n-2...].
- Đầu ra: một mảng chứa các số giống nhau nhưng được sắp xếp đầy đủ. Cái này thường được gọi là B: B[0]B[1]...B[n-1].
- Sắp xếp theo số (thứ tự tăng dần): [1, 2, 3, 4, 5]
- Sắp xếp theo số (thứ tự giảm dần): [5, 4, 3, 2, 1]
- Sắp xếp theo thứ tự chữ cái: [a, b, c, d]
Hiểu lý thuyết về sắp xếp chèn
Trước khi khám phá mã đằng sau sắp xếp chèn, hãy chia nhỏ thuật toán bằng cách sử dụng ngôn ngữ phi kỹ thuật. Bởi vì chúng tôi sẽ hiển thị mã để sắp xếp theo thứ tự tăng dần, nên việc giải thích thuật toán từng bước trong bài đăng này là điều hợp lý. Bước 1. Lặp lại giữaarr[1]
và arr[n]
ở đâu n
là một giá trị số thường nhỏ hơn 10. Bước 2. So sánh phần tử bạn đã chọn (được gọi là key
) với số trước đó trong chuỗi bằng sort()
phương pháp. Bước 3. Nếu tất cả các phần tử đều nhỏ hơn phần tử kế tiếp, hãy lặp lại phép so sánh cho đến khi bạn tìm thấy giá trị lớn hơn. Bước 4. Hoán đổi giá trị lớn hơn một vị trí so với giá trị nhỏ hơn để tạo một chuỗi có thứ tự. Bước 5. Lặp lại quy trình cho đến khi bạn nhận được chuỗi ký tự đã sắp xếp
Sắp xếp mảng nguyên thủy
Vì thuật toán là một trong những thao tác Java đơn giản nhất nên ngay cả những người mới bắt đầu hoàn chỉnh cũng không gặp nhiều khó khăn khi thực hiện nó. Dưới đây là hướng dẫn từng bước để sắp xếp một mảng1. Khai báo một mảng để sắp xếp
Để bắt đầu, hãy tạo một chuỗi giá trị mà sau này chúng ta sẽ hiển thị bằng Java. Để sử dụng sắp xếp chèn, bạn cần tạo một mảng. Đối với điều đó, sử dụngint[]
int[] arrayA = {10, 14, 20, 30};
2. Sử dụng sort_arr để thực hiện thuật toán
Phương thức sort_arr là một trong những cách phổ biến nhất để triển khai sắp xếp chèn. Trong thực tế, nó trông như thế này:
for(int i=0; i< sort_arr.length; ++i){
int j = i;
3. Tạo vòng lặp và trình vòng lặp
Bằng cách sử dụng một vòng lặp trong thuật toán sắp xếp chèn, các nhà phát triển không phải lặp lại logic cho mọi phần tử. Mặc dù việc tạo các vòng lặp có vẻ phức tạp, nhưng nó khá đơn giản - đây là một ví dụ:
for(int i=0; i< sort_arr.length; ++i){
Bây giờ bạn đã có một vòng lặp hoạt động, đã đến lúc tạo một trình vòng lặp sẽ sắp xếp tất cả các phần tử theo thứ tự mong muốn. Từ giờ trở đi, chúng ta sẽ gọi iterator là " j
".
int j = i;
4. Tạo "vòng lặp while"
Khi nói đến sắp xếp chèn, một vòng lặp "trong khi" là điều cần thiết cho một mảng mới được sắp xếp. Để thiết lập nó cho sắp xếp chèn theo thứ tự tăng dần, nhà phát triển cần tuân thủ hai điều kiện:- Giá trị được gán cho j phải lớn hơn 0
- Giá trị được gán cho
j-1
cần phải lớn hơnj
chỉ mục
j
mục.
5. Sắp xếp mảng
Sau khi bạn thiết lập vòng lặp while, các giá trịj
và j-1
sẽ được hoán đổi cho đến khi một hoặc cả hai điều kiện trong vòng lặp while không thành công. Tương tự, việc sắp xếp sẽ được lặp lại cho mọi giá trị trong vòng lặp for cho đến khi các điều kiện của vòng lặp for cũng không thành công. Đây là cách quá trình sắp xếp chèn hoạt động trong thực tế:
int key = sort_arr[j];
sort_arr[j] = sort_arr[j-1];
sort_arr[j-1] = key;
j = j-1;
Sắp xếp một ArrayList
Mặc dù việc hiểu toán học đằng sau sắp xếp chèn là rất quan trọng, nhưng khi nói đến phát triển phần mềm thực tế, bạn sẽ sắp xếp ArrayLists nhiều hơn so với trình tự trong các mảng nguyên thủy. Dưới đây là hướng dẫn từng bước để sắp xếp một ArrayList:- Tạo một
Element
lớp mới cho các mục thuộc bộ sưu tập.public class Element { private int id; public Element(int id) { this.id = id; }
- Trong một bộ sưu tập, có một
compareTo()
phương thức - chúng tôi sẽ sử dụng phương thức này để so sánh id của hai phần tử.public int compareTo(Element element) { int res = 0; if (this.id < element.getId()) { res = -1; } if (this.id > element.getId()) { res = 1; } return res; } }
- Áp dụng thuật toán và tạo một số vòng lặp để sắp xếp các đối tượng
ArrayList
thay vì so sánh chúng.public static void insertionSortArrayList(List<element> list) { for (int j = 1; j < list.size(); j++) { Element current = list.get(j); int i = j-1; while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) { list.set(i+1, list.get(i)); i--; } list.set(i+1, current); } }
ArrayList
Bạn cũng có thể thêm nhiều yếu tố hơn vào , như được hiển thị bên dưới:List<element> list = new ArrayList<>(); // Create elements w/ IDs 0-24 for (int i = 0; i < 25; i++) { list.add(new Element(i)); } // To use insertion sort, shuffle the values Collections.shuffle(list);
- Bây giờ là lúc để sắp xếp:
// This helps print values before sorting list.forEach(e -> System.out.print(e.getId() + ", ")); // Sort the list insertionSortArrayList(list); System.out.println(); // Display a sorted array list.forEach(e -> System.out.print(e.getId() + ", "));
- Bây giờ hãy so sánh đầu vào và đầu ra để đảm bảo chúng tôi không mắc lỗi nào. Đây là so sánh của chuỗi chúng tôi đã sử dụng làm ví dụ.
4, 2, 6, 7, 0, 5, 9, 1, 8, 3, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
GO TO FULL VERSION