Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
ComboBox - ListBox trong lập trình C# winforms 
Random trong Python: Tạo số random ngẫu nhiên 
Lệnh cin và cout trong C++ 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Thuật toán sắp xếp trộn trong Java, giải bài toán Merge Sort Java
Trong bài này mình sẽ giới thiệu đến các bạn thuật toán sắp xếp hỗn hợp (Merge Sort). Đây là một trong những thuật toán sắp xếp trong Java.
Chúng ta sẽ cùng nhau tìm hiều về Merge Sort là gì và cách triển khai thuật toán Merge Sort trong Java. Ở cuối bài viết, mình sẽ giải một bài toán cụ thể để các bạn hiểu hơn về cách áp dụng thuật toán trong thực tế.
Thuật toán Merge Sort trong Java
Merge Sort là một thuật toán sắp xếp dựa trên giải thuật Divide and Conquer (Chia để trị).
Nó hoạt động bằng cách chia một mảng thành các mảng con nhỏ hơn, sắp xếp từng mảng con, sau đó hợp nhất các mảng con đã sắp xếp lại với nhau để tạo thành mảng được sắp xếp cuối cùng.
Bài viết này được đăng tại [free tuts .net]
Nhiều bạn có thắc mắc là chúng ta đã có một số thuật toán sắp xếp rồi thì tại sao chúng ta lại cần đến thuật toán này?
- Độ phức tạp về thời gian là O(n log n), có nghĩa là nó có thể sắp xếp các mảng lớn tương đối nhanh chóng.
- Nó cũng là một cách sắp xếp mà trong thời gian đó thứ tự của các phần tử có giá trị bằng nhau được giữ nguyên.
- Thuật toán này thường được dùng với các tập dữ liệu lớn.
- Nó thường được sử dụng cùng với các thuật toán khác, chẳng hạn như sắp xếp nhanh, để cải thiện hiệu suất tổng thể của quy trình sắp xếp.
Để dễ hình dung thì chúng ta cùng xem ví dụ sau đây.
Ví dụ minh họa cho thuật toán Merge Sort trong Java
Như các bạn đã thấy ở hình trên, dãy số ban đầu bao gôm các số: 38 27 43 3 9 82 10.
Chúng ta sẽ chia thành hai phần là một bên 4 số và một bên 3 số. Rồi tiếp tục chia 4 số đó thành hai phần là mỗi bên 2 số. Cứ chia như vậy cho đến khi được kết quả như dòng thứ 4.
Sau khi chia xong, bây giờ chúng ta bắt đầu vào việc so sanh từng phần nhỏ. Rồi gom chúng lại thành một dãy số hoàn chỉnh đã sắp xếp ở các dòng 5, 6, 7 như trong hình.
Sau khi gom lại và so sánh xong ta được dãy số mới đã sắp xếp: 3 9 10 27 38 43 82.
Chương trình triển khai thuật toán Merge Sort trong Java
Bây giờ hãy xem đoạn code mà freetuts triển khai dưới đây để hiểu được thuật toán này nhé.
/**
* Học lập trình Java miễn phí tại freetuts.net
*
* @author freetuts
*/
import java.util.Arrays;
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr.length > 1) {
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, arr.length);
mergeSort(left);
mergeSort(right);
merge(arr, left, right);
}
}
public static void merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < left.length) {
arr[k++] = left[i++];
}
while (j < right.length) {
arr[k++] = right[j++];
}
}
public static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {38, 27, 43, 3, 9, 82, 10};
System.out.println("Học lập trình miễn phí tại freetuts");
System.out.println("Mảng ban đầu:");
printArray(arr);
mergeSort(arr);
System.out.println("Mảng sau khi dùng Merge Sort:");
printArray(arr);
}
}
Giải thích:
- Hàm
mergeSortsử dụng đệ quy để chia mảng thành các mảng con đến khi mỗi mảng con chỉ có 1 phần tử. - Hàm
mergesắp xếp các mảng con đã chia và gộp lại với nhau để tạo ra một mảng lớn đã sắp xếp. - Hàm
printArrayđược sử dụng để in mảng ra màn hình.
Kết quả:
Như vậy là chúng ta đã thực hiện xong chương trình sắp xếp các phần tử trong mảng, sử dụng thuật toán Merge Sort trong Java. Cũng như kết thúc phần giới thiệu và hướng dẫn triển khai thuật toán Merge Sort trong Java. Chúc các bạn thực hiện thành công!!!
