CĂN BẢN
CHUỖI
VÒNG LẶP
NUMBER
INPUT / OUTPUT
COLLECTIONS
Ví dụ danh sách liên kết đơn Java Đếm số node trong Singly Linked List trong Java Đảo ngược thứ tự của Singly Linked List trong Java Xóa node đầu tiên của Singly Linked List trong Java Xóa node ở giữa của Singly Linked List trong Java Xóa node cuối cùng của Singly Linked List trong Java Thêm node vào vị trí đầu tiên của Singly Linked List trong Java Thêm node vào vị trí cuối cùng của Singly Linked List trong Java Thêm node vào vị trí giữa của Singly Linked List trong Java Kiểm tra danh sách liên kết đơn palindrome trong Java Tìm giá trị lớn nhất của Singly Linked List trong Java Tìm giá trị nhỏ nhất của Singly Linked List trong Java Xóa phần tử trùng lặp khỏi Singly Linked List trong Java Tìm kiếm phần tử của Singly Linked List trong Java Tạo một Circular Linked List trong Java Tạo một Circular Linked List Java và đảo ngược nó Xóa node đầu tiên của Circular Linked List trong Java Xóa node cuối cùng của Circular Linked List trong Java Xóa node ở giữa của Circular Linked List trong Java Thêm node vào vị trí đầu tiên của Circular Linked List trong Java Thêm node vào vị trí cuối cùng của Circular Linked List trong Java Thêm node vào vị trí giữa của Circular Linked List trong Java Tìm giá trị lớn nhất trong Circular Linked List Java Tìm giá trị nhỏ nhất trong Circular Linked List Tìm kiếm phần tử của Circular Linked List trong Java Xóa phần tử trùng lặp khỏi Circular Linked List trong Java Sắp xếp các phần tử của Circular Linked List trong Java Chuyển đổi Binary Tree thành Double Linked List trong Java Tạo double linked list từ cây bậc ba (ternary tree) trong Java Cách chuyển đổi từ cây nhị phân thành cây nhị phân tìm kiếm trong Java Xác định các lá có cùng cấp trong Tree của Java Kiểm tra hai cây giống nhau trong Java Tìm chiều rộng tối đa của cây nhị phân trong Java Tìm phần tử lớn nhất của cây nhị phân trong Java Tìm khoảng cách lớn nhất giữa các node của cây nhị phân trong Java Tìm phần tử nhỏ nhất của cây nhị phân trong Java Tính tổng giá trị của các node của cây nhị phân trong Java Tính tổng số cây nhị phân tìm kiếm có thể được tạo ra bởi N nodes trong Java Triển khai cây nhị phân từ danh sách liên kết trong Java Tìm kiếm node của cây nhị phân tìm kiếm trong Java Cách tạo ra Mirror Tree từ Binary Tree bằng ngôn ngữ Java Xác định các lá của binary tree sử dụng preoder trong Java Xác định đường biên(boundary traversal) của cây nhị phân trong Java Xóa node của cây nhị phân tìm kiếm trong Java Duyệt cây nhị phân bằng phương pháp inOder trong Java
CALCULATE
SẮP XẾP - TÌM KIẾM
KHÁC
NÂNG CAO
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
MỚI CẬP NHẬT

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.

test php

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

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

MergeSortTutorial png

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 mergeSort sử 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 merge sắ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ả:

result merge sort jpg

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!!!

Cùng chuyên mục:

Hướng dẫn Upload file với Spring Boot và jQuery Ajax trong Java

Hướng dẫn Upload file với Spring Boot và jQuery Ajax trong Java

Hướng dẫn download file với Spring Boot trong Java

Hướng dẫn download file với Spring Boot trong Java

Hướng dẫn Upload file với Spring Boot trong Java

Hướng dẫn Upload file với Spring Boot trong Java

Hướng dẫn CRUD với Spring Boot, REST và AngularJS trong Java

Hướng dẫn CRUD với Spring Boot, REST và AngularJS trong Java

Cách sử dụng Spring  Scheduled trong Spring Boot

Cách sử dụng Spring Scheduled trong Spring Boot

Cách dùng Groovy trong Spring Boot Java

Cách dùng Groovy trong Spring Boot Java

Cách dùng Spring Boot và Mustache trong Java

Cách dùng Spring Boot và Mustache trong Java

Cách dùng Spring Boot và MongoDB trong Java

Cách dùng Spring Boot và MongoDB trong Java

Cách tạo Restful Client bằng RestTemplate trong Spring Boot

Cách tạo Restful Client bằng RestTemplate trong Spring Boot

Hướng dẫn sử dụng Interceptor trong Spring Boot

Hướng dẫn sử dụng Interceptor trong Spring Boot

Sử dụng Twitter Bootstrap trong Spring Boot

Sử dụng Twitter Bootstrap trong Spring Boot

Tạo trang web đa ngôn ngữ với Spring Boot trong Java

Tạo trang web đa ngôn ngữ với Spring Boot trong Java

Tạo ứng dụng Chat với Spring Boot và Websocket

Tạo ứng dụng Chat với Spring Boot và Websocket

Sử dụng JUnit để tạo unit test trong Spring Boot

Sử dụng JUnit để tạo unit test trong Spring Boot

Cách triển khai Spring Boot trên Tomcat Server

Cách triển khai Spring Boot trên Tomcat Server

Cách test RESTful API trong Spring Boot

Cách test RESTful API trong Spring Boot

Cách dùng Spring Security trong Spring Boot để xác thực và phân quyền

Cách dùng Spring Security trong Spring Boot để xác thực và phân quyền

Duyệt cây nhị phân bằng phương pháp inOder trong Java

Duyệt cây nhị phân bằng phương pháp inOder trong Java

Xóa node của cây nhị phân tìm kiếm trong Java

Xóa node của cây nhị phân tìm kiếm trong Java

Bảo mật Spring Boot RESTful Service sử dụng Basic Authentication trong Java

Bảo mật Spring Boot RESTful Service sử dụng Basic Authentication trong Java

Top