Thuật toán sắp xếp chèn vào Java với ví dụ về chương trình
James Hartman
⚡ Tóm tắt thông minh
Sắp xếp chèn trong Java Phương pháp này xây dựng một phần mảng đã được sắp xếp từng phần tử một, dịch chuyển các giá trị lớn hơn sang phải cho đến khi mỗi khóa nằm ở vị trí chính xác của nó, lý tưởng cho các tập dữ liệu nhỏ.
Thuật toán sắp xếp chèn là gì?
Sắp xếp chèn là một thuật toán sắp xếp đơn giản phù hợp với các tập dữ liệu nhỏ. Trong mỗi lần lặp, thuật toán:
- Loại bỏ một phần tử khỏi một mảng.
- So sánh nó với giá trị lớn nhất trong mảng.
- Di chuyển phần tử đến đúng vị trí của nó.
Hành vi này phản ánh cách người chơi bài sắp xếp bài: mỗi lá bài mới được nhặt lên và đẩy sang trái, vượt qua mọi lá bài lớn hơn cho đến khi nó nằm đúng vị trí. Vì tất cả các thao tác dịch chuyển đều diễn ra bên trong mảng ban đầu, nên thuật toán sắp xếp chèn vừa thực hiện tại chỗ vừa ổn định.
Nó thuộc cùng một dòng sản phẩm thân thiện với người mới bắt đầu. Java các quy trình sắp xếp như phân loại bong bóngTuy nhiên, nó thường thực hiện ít thao tác ghi hơn trên dữ liệu đã được sắp xếp một phần.
Quy trình thuật toán sắp xếp chèn
Đây là cách quy trình thuật toán sắp xếp chèn hoạt động bằng đồ họa:
Hoạt hình lặp lại ba bước giống nhau. Java Chương trình bên dưới thực hiện. Bảng chạy thử tracHãy thực hiện các bước đó trên mảng mẫu {860, 8, 200, 9}, chính xác như chương trình in ra khi chạy.
| Qua | Yếu tố quan trọng | Các so sánh đã được thực hiện | Mảng sau khi truyền |
|---|---|---|---|
| 1 | 8 | 8 chọi 860 | 8 860 200 9 |
| 2 | 200 | 200 chọi 860 | 8 200 860 9 |
| 3 | 9 | 9 đấu với 860, sau đó 9 đấu với 200. | 8 9 200 860 |
Lưu ý rằng lượt 3 cần hai phép so sánh vì khóa 9 phải đi qua hai giá trị lớn hơn. Do đó, số lượng phép so sánh tăng lên tùy thuộc vào khoảng cách mà mỗi phần tử bắt đầu ở vị trí không đúng thứ tự.
Java Ví dụ chương trình để sắp xếp một mảng bằng thuật toán sắp xếp chèn:
Chương trình bên dưới sắp xếp mảng {860, 8, 200, 9} và in ra chú thích liên tục, để mọi phép so sánh và mọi thao tác dịch chuyển đều được hiển thị. Hãy lưu nó dưới dạng [tên tệp]. InsertionSortExample.java và biên dịch nó với bất kỳ phiên bản JDK 8 trở lên nào.
package com.guru99; public class InsertionSortExample { public static void main(String a[]) { int[] myArray = {860,8,200,9}; System.out.println("Before Insertion Sort"); printArray(myArray); insertionSort(myArray);//sorting array using insertion sort System.out.println("After Insertion Sort"); printArray(myArray); } public static void insertionSort(int arr[]) { int n = arr.length; for (int i = 1; i < n; i++) { System.out.println("Sort Pass Number "+(i)); int key = arr[i]; int j = i-1; while ( (j > -1) && ( arr [j] > key ) ) { System.out.println("Comparing "+ key + " and " + arr [j]); arr [j+1] = arr [j]; j--; } arr[j+1] = key; System.out.println("Swapping Elements: New Array After Swap"); printArray(arr); } } static void printArray(int[] array){ for(int i=0; i < array.length; i++) { System.out.print(array[i] + " "); } System.out.println(); } }
Việc chạy lớp học tạo ra trace được hiển thị ở đây. Mỗi Số thứ tự sắp xếp Dòng này đánh dấu một lần lặp của vòng lặp ngoài, và dòng được in sau mỗi lần hoán đổi cho thấy mảng ở trạng thái hiện tại.
Code Đầu ra:
Before Insertion Sort 860 8 200 9 Sort Pass Number 1 Comparing 8 and 860 Swapping Elements: New Array After Swap 8 860 200 9 Sort Pass Number 2 Comparing 200 and 860 Swapping Elements: New Array After Swap 8 200 860 9 Sort Pass Number 3 Comparing 9 and 860 Comparing 9 and 200 Swapping Elements: New Array After Swap 8 9 200 860 After Insertion Sort 8 9 200 860
Độ phức tạp về thời gian và không gian của thuật toán sắp xếp chèn
Hiệu năng của thuật toán sắp xếp chèn phụ thuộc rất nhiều vào mức độ sắp xếp sẵn có của dữ liệu đầu vào, đó là lý do tại sao trường hợp tốt nhất và trường hợp tệ nhất lại chênh lệch nhau cả một bậc về mức độ tăng trưởng.
| Khay | Điều kiện đầu vào | Thời gian phức tạp |
|---|---|---|
| Tốt | Mảng đã được sắp xếp, do đó vòng lặp while bên trong sẽ không bao giờ chạy. | O (n) |
| Trung bình | Các phần tử xuất hiện theo thứ tự ngẫu nhiên | O (n²) |
| tệ nhất | Mảng được sắp xếp ngược, do đó mỗi khóa sẽ được đưa lên đầu. | O (n²) |
Việc sử dụng không gian đơn giản hơn nhiều. Chỉ có các quầy. i, j, n và key được tạo ra và mảng được sắp xếp lại tại chỗ, do đó không gian phụ trợ là O(1) bất kể đầu vào lớn đến mức nào.
Vì vòng lặp bên trong dừng lại ngay khi gặp giá trị nhỏ hơn, thuật toán sắp xếp chèn được mô tả là thích ứng: dữ liệu đầu vào càng gần với thứ tự đã được sắp xếp, thời gian thực thi càng tiến gần đến tuyến tính.
Ưu điểm và nhược điểm của sắp xếp chèn
Thuật toán sắp xếp chèn vẫn được sử dụng trong các thư viện thực tế mặc dù có trường hợp trung bình bậc hai, bởi vì các hằng số của nó rất nhỏ và hành vi của nó có thể dự đoán được.
Ưu điểm
- Dễ viết và dễ hiểu tracViết tay, rất phù hợp cho việc giảng dạy và phỏng vấn.
- Ổn định, vì vậy các bản ghi có chung khóa sẽ giữ nguyên thứ tự tương đối ban đầu của chúng.
- Tại chỗ, chỉ cần thêm bộ nhớ O(1) ngoài mảng đầu vào.
- Có khả năng thích ứng, đạt độ phức tạp O(n) trên dữ liệu đã được sắp xếp gần như hoàn chỉnh.
- Trực tuyến, có nghĩa là nó có thể sắp xếp danh sách trong khi các phần tử mới vẫn đang được thêm vào.
Nhược điểm
- Thời gian xử lý bậc hai đối với dữ liệu đầu vào ngẫu nhiên hoặc được sắp xếp ngược khiến nó không phù hợp với các mảng lớn.
- Mỗi thao tác dịch chuyển ghi vào mảng, do đó nó di chuyển nhiều dữ liệu hơn so với thuật toán sắp xếp chọn.
- Thuật toán sắp xếp trộn (Merge sort) và sắp xếp nhanh (Quicksort) hoạt động hiệu quả hơn hẳn khi số lượng phần tử đầu vào vượt quá vài chục.
Một nguyên tắc thực tiễn là nên sử dụng thuật toán sắp xếp chèn khi mảng nhỏ, khi dữ liệu gần như đã được sắp xếp theo thứ tự, hoặc khi thuật toán sắp xếp chia để trị đã giảm một phân vùng xuống chỉ còn một vài phần tử.
Thuật toán sắp xếp chèn so với Bubble Sort so với Selection Sort
Cả ba thuật toán đều là thuật toán sắp xếp so sánh bậc hai, tuy nhiên chúng khác nhau về độ ổn định, cách phản ứng với dữ liệu đầu vào có thứ tự và số lần ghi mà chúng thực hiện.
| Tiêu chí | Sắp xếp chèn | Bubble Sắp xếp | Sắp xếp lựa chọn |
|---|---|---|---|
| Trường hợp tốt nhất | O (n) | O(n) với cờ thoát sớm | O (n²) |
| trường hợp trung bình và trường hợp xấu nhất | O (n²) | O (n²) | O (n²) |
| Không gian thêm | O (1) | O (1) | O (1) |
| Ổn định | Có | Có | Không, trong phiên bản mảng tiêu chuẩn |
| Thích nghi | Có | Đúng vậy, khi sử dụng phương pháp tối ưu hóa cờ. | Không |
| Ghi vào mảng | Nhiều ca làm việc, nhưng ít ca dựa trên dữ liệu đã được sắp xếp. | Nhiều cuộc trao đổi | Chính xác n-1 lần hoán đổi |
Thuật toán sắp xếp chọn (Selection sort) thắng thế khi thao tác ghi tốn kém, vì nó thực hiện ít thao tác hoán đổi nhất. Thuật toán sắp xếp chèn (Insertion sort) thắng thế ở hầu hết mọi trường hợp khác ở quy mô này, đặc biệt là trên dữ liệu được sắp xếp một phần, đó là lý do tại sao các thuật toán sắp xếp trong thư viện như thuật toán được đề cập ở trên lại hiệu quả. chung Java bài tập và các thành phần nội bộ của JDK sẽ chuyển sang sử dụng nó cho các phân vùng rất nhỏ.
