Tiếp nối ý tưởng của mục 2, liệu khi đã có ý tưởng và giải thuật cơ bản, bạn có thể tự mình triển khai thuật Insertion Sort trong Java không?
Để việc học lập trình được tốt nhất, mình khuyên bạn hãy dừng lại và thử tự mình thực hiện trước cho đến khi nào chịu thua thì quay lại đây.
Còn nếu bạn có thể thì cũng không cần đọc tiếp nữa :D
package insertion.sort.algo;
public class InsertionSort {
// Phương thức sắp xếp chèn
void sort(int arr[]) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
// Di chuyển các phần tử của arr [0 ... i - 1], lớn hơn key
// đến một vị trí trước vị trí hiện tại của chúng
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
// In các phần tử của mảng
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[]) {
int arr[] = { 12, 11, 13, 5, 6 };
System.out.println("Mảng ban đầu:");
printArray(arr);
InsertionSort ob = new InsertionSort();
ob.sort(arr);
System.out.println("Mảng sau khi sắp xếp:");
printArray(arr);
}
}
Khi chạy chương trình, ta nhận được kết quả là:
Mảng ban đầu:
12 11 13 5 6
Mảng sau khi sắp xếp:
5 6 11 12 13
Sắp xếp chèn được sử dụng khi số lượng phần tử nhỏ.
Nó cũng có thể hữu ích khi mảng đầu vào gần như được sắp xếp, chỉ có một số phần tử bị đặt sai vị trí trong một mảng lớn hoàn chỉnh.
Chúng ta có thể sử dụng tìm kiếm nhị phân để giảm số lượng so sánh trong sắp xếp chèn thông thường. Binary Insertion Sort được sử dụng để tìm kiếm nhị phân vị trí thích hợp để chèn mục đã chọn ở mỗi lần lặp.
Trong trường hợp chèn thông thường, việc sắp xếp lấy O(i) (ở lần lặp thứ i). Chúng ta có thể giảm nó thành O(logi) bằng cách sử dụng tìm kiếm nhị phân.
Nói chung, thuật toán vẫn có thời gian chạy trong trường hợp xấu nhất là O(n2) vì chuỗi hoán đổi cần thiết cho mỗi lần chèn.
Trong sắp xếp chèn thông thường, nó cần O(n2) so sánh (ở lần lặp thứ n) trong trường hợp xấu nhất. Chúng ta có thể giảm nó thành O(log n) bằng cách sử dụng tìm kiếm nhị phân.
package insertion.sort.algo;
import java.util.Arrays;
public class BinaryInsertionSort {
public static void main(String[] args) {
final int[] arr = { 12, 11, 13, 5, 6 };
new BinaryInsertionSort().sort(arr);
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
}
public void sort(int array[]) {
for (int i = 1; i < array.length; i++) {
int x = array[i];
// Tìm vị trí để chèn bằng tìm kiếm nhị phân
int j = Math.abs(Arrays.binarySearch(array, 0, i, x) + 1);
// Chuyển mảng sang đúng một vị trí
System.arraycopy(array, j, array, j + 1, i - j);
// Đặt phần tử vào đúng vị trí của nó
array[j] = x;
}
}
}
Binary Insertion Sort có thể được xem là Insertion Sort cải tiến, nhưng bạn hãy nhìn xem – code tuy ngắn gọn hơn nhưng mang tính nâng cao hơn khá nhiều.
Nhờ vậy, trong đa số trường hợp (không phải là xấu nhất) thì tốc độ ăn đứt Insertion Sort.
Thuật toán Insertion sort không phải là thuật toán quá khó khăn, thậm chí rất gần gũi với thực tiễn cuộc sống – nhưng đôi khi bạn không nhận ra mình đang áp dụng thuật toán insertion sort mà thôi.
> Đối với việc HỌC LẬP TRÌNH thì không có sự trùng hợp như vậy được, bạn phải trải qua gian khổ - luyện code mới sớm thành thục được.
---
HỌC VIỆN ĐÀO TẠO CNTT NIIT - ICT HÀ NỘI
Học Lập trình chất lượng cao (Since 2002). Học làm Lập trình viên. Hành động ngay!
Đc: Tầng 3, 25T2, N05, Nguyễn Thị Thập, Cầu Giấy, Hà Nội
SĐT: 02435574074 - 0914939543
Email: hello@niithanoi.edu.vn
Fanpage: https://facebook.com/NIIT.ICT/
#niit #niithanoi #niiticthanoi #hoclaptrinh #khoahoclaptrinh #hoclaptrinhjava #hoclaptrinhphp #java #php #python