Sắp xếp chèn trong Java

1. Khái quát chung

Trong hướng dẫn này, chúng ta sẽ thảo luận về thuật toán Insertion Sort và xem xét việc triển khai Java của nó .

Insertion Sort là một thuật toán hiệu quả để sắp xếp một số lượng nhỏ các mặt hàng. Phương pháp này dựa trên cách người chơi bài sắp xếp một ván bài.

Chúng ta bắt đầu với một bàn tay trái trống rỗng và các quân bài được đặt trên bàn. Sau đó, chúng tôi lấy từng thẻ một khỏi bảng và đưa thẻ vào đúng vị trí bên tay trái. Để tìm vị trí chính xác cho một thẻ mới, chúng tôi so sánh nó với bộ thẻ đã được sắp xếp trong tay, từ phải sang trái.

Hãy bắt đầu bằng cách tìm hiểu các bước thuật toán ở dạng mã giả.

2. Mã giả

Chúng ta sẽ trình bày mã giả của chúng ta để sắp xếp chèn dưới dạng một thủ tục được gọi là INSERTION-SORT , lấy tham số là một mảng A [1 .. n] trong số n mục được sắp xếp. Thuật toán sắp xếp mảng đầu vào tại chỗ (bằng cách sắp xếp lại các mục trong mảng A).

Sau khi thủ tục kết thúc, mảng đầu vào A chứa một hoán vị của chuỗi đầu vào nhưng theo thứ tự được sắp xếp:

INSERTION-SORT(A) for i=2 to A.length key = A[i] j = i - 1 while j > 0 and A[j] > key A[j+1] = A[j] j = j - 1 A[j + 1] = key

Hãy xem qua thuật toán ở trên.

Chỉ số i cho biết vị trí của mục hiện tại trong mảng để xử lý.

Chúng ta bắt đầu từ mục thứ hai vì theo định nghĩa, một mảng có một mục được coi là đã được sắp xếp. Mục ở chỉ mục i được gọi là khóa . Sau khi có khóa, phần thứ hai của thuật toán đề cập đến việc tìm chỉ mục chính xác của nó. Nếu khóa nhỏ hơn giá trị của mục tại chỉ số j , thì khóa sẽ di chuyển sang trái một vị trí. Quá trình tiếp tục cho đến khi chúng ta đạt được một phần tử nhỏ hơn khóa.

Điều quan trọng cần lưu ý là trước khi bắt đầu lặp để tìm vị trí chính xác của khóa tại chỉ mục i , mảng A [1 .. j - 1] đã được sắp xếp .

3. Thực hiện bắt buộc

Đối với trường hợp bắt buộc, chúng ta sẽ viết một hàm có tên là inserttionSortImperative , lấy một mảng các số nguyên dưới dạng tham số. Hàm bắt đầu lặp qua mảng từ mục thứ hai.

Tại bất kỳ thời điểm nào trong quá trình lặp, chúng ta có thể coi mảng này được chia thành hai phần một cách hợp lý; phía bên trái là một đã được sắp xếp và phía bên phải chứa các mục chưa được sắp xếp.

Một lưu ý quan trọng ở đây là sau khi tìm được vị trí chính xác mà chúng tôi sẽ chèn mục mới, chúng tôi chuyển (và không hoán đổi) các mục sang bên phải để giải phóng không gian cho nó.

public static void insertionSortImperative(int[] input) { for (int i = 1; i 
    
     = 0 && input[j] > key) { input[j + 1] = input[j]; j = j - 1; } input[j + 1] = key; } }
    

Tiếp theo, hãy tạo một bài kiểm tra cho phương thức trên:

@Test public void givenUnsortedArray_whenInsertionSortImperative_thenSortedAsc() { int[] input = {6, 2, 3, 4, 5, 1}; InsertionSort.insertionSortImperative(input); int[] expected = {1, 2, 3, 4, 5, 6}; assertArrayEquals("the two arrays are not equal", expected, input); }

Kiểm tra ở trên chứng minh rằng thuật toán sắp xếp chính xác theo thứ tự tăng dần mảng đầu vào .

4. Thực hiện đệ quy

Chức năng đối với trường hợp đệ quy được gọi insertionSortR ecursive và chấp nhận như là đầu vào một mảng các số nguyên (giống như đối với trường hợp bắt buộc).

Sự khác biệt ở đây so với trường hợp mệnh lệnh (mặc dù thực tế là nó đệ quy) là nó gọi một hàm nạp chồng với đối số thứ hai bằng số lượng mục cần sắp xếp.

Khi chúng ta muốn sắp xếp mảng hoàn chỉnh, chúng ta sẽ chuyển một số mục bằng độ dài của nó:

public static void insertionSortRecursive(int[] input) { insertionSortRecursive(input, input.length); }

Trường hợp đệ quy khó hơn một chút. Trường hợp cơ sở xảy ra khi chúng ta cố gắng sắp xếp một mảng với một mục. Trong trường hợp này, chúng tôi không làm gì cả.

Tất cả các lệnh gọi đệ quy tiếp theo sắp xếp một phần được xác định trước của mảng đầu vào - bắt đầu từ mục thứ hai cho đến khi chúng ta đi đến cuối mảng:

private static void insertionSortRecursive(int[] input, int i) { if (i <= 1) { return; } insertionSortRecursive(input, i - 1); int key = input[i - 1]; int j = i - 2; while (j>= 0 && input[j] > key) { input[j + 1] = input[j]; j = j - 1; } input[j + 1] = key; }

Và đây là ngăn xếp cuộc gọi trông như thế nào đối với mảng đầu vào gồm 6 mục:

insertionSortRecursive(input, 6) insertionSortRecursive(input, 5) and insert the 6th item into the sorted array insertionSortRecursive(input, 4) and insert the 5th item into the sorted array insertionSortRecursive(input, 3) and insert the 4th item into the sorted array insertionSortRecursive(input, 2) and insert the 3rd item into the sorted array insertionSortRecursive(input, 1) and insert the 2nd item into the sorted array

Hãy cũng xem thử nghiệm cho nó:

@Test public void givenUnsortedArray_whenInsertionSortRecursively_thenSortedAsc() { int[] input = {6, 4, 5, 2, 3, 1}; InsertionSort.insertionSortRecursive(input); int[] expected = {1, 2, 3, 4, 5, 6}; assertArrayEquals("the two arrays are not equal", expected, input); }

Kiểm tra ở trên chứng minh rằng thuật toán sắp xếp chính xác theo thứ tự tăng dần mảng đầu vào .

5. Sự phức tạp về thời gian và không gian

Thời gian thực hiện thủ tục INSERTION-SORT để chạy là O (n ^ 2) . Đối với mỗi mục mới, chúng tôi lặp lại từ phải sang trái trên phần đã được sắp xếp của mảng để tìm vị trí chính xác của nó. Sau đó, chúng tôi chèn nó bằng cách chuyển các mục sang bên phải.

Thuật toán sắp xếp tại chỗ nên độ phức tạp không gian của nó O (1) đối với việc triển khai mệnh lệnh và O (n) đối với việc triển khai đệ quy.

6. Kết luận

Trong hướng dẫn này, chúng ta đã biết cách triển khai sắp xếp chèn.

Thuật toán này rất hữu ích để phân loại một số lượng nhỏ các mục. Nó trở nên không hiệu quả khi sắp xếp các chuỗi đầu vào có hơn 100 mục.

Hãy nhớ rằng bất chấp độ phức tạp bậc hai của nó, nó sắp xếp tại chỗ mà không cần không gian bổ trợ như trường hợp sắp xếp hợp nhất .

Toàn bộ mã có thể được tìm thấy trên GitHub.