Code java thuật toán sắp xếp java core năm 2024

Đề bài: Viết chương trình Java nhập một mảng số nguyên a0, a1, a2, …, an-1. Hãy sắp xếp mảng theo thứ tự tăng dần.

Lời giải

Sau đây là chương trình Java sắp xếp mảng theo thứ tự tăng dần:

File: BaiTap22.java

package vn.viettuts.baitap.array; import java.util.Scanner; /

• Chương trình sắp xếp mảng số nguyên theo thứ tự tăng dần.
• @author viettuts.vn / public class BaiTap24 {

  public static Scanner scanner = new Scanner(System.in);  
  /*
  

  • main
  • @param args

     /  
    public static void main(String[] args) {  
        System.out.print("Nhập số phần tử của mảng: ");  
        int n = scanner.nextInt();  
        // khởi tạo arr  
        int [] arr = new int [n];  
        System.out.print("Nhập các phần tử của mảng: \n");  
        for (int i = 0; i < n; i++) {  
            System.out.printf("a[%d] = ", i);  
            arr[i] = scanner.nextInt();  
        }  
        // sắp xếp dãy số theo thứ tự tăng dần  
        sortASC(arr);  
        System.out.println("Dãy số được sắp xếp tăng dần: ");  
        show(arr);  
    }  
    /*  

  • sắp xếp mảng số nguyên theo thứ tự tăng dần
  • @param arr: mảng các số nguyên
  • @param n: số phần tử của mảng / public static void sortASC(int [] arr) { int temp = arr[0]; for (int i = 0 ; i < arr.length - 1; i++) { for (int j = i + 1; j < arr.length; j++) { if (arr[i] > arr[j]) { temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } } } } /*
  • in các phần tử của mảng ra màn hình
  • @param arr: mảng các số nguyên
  • @param n: số phần tử của mảng */ public static void show(int [] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } } Kết quả:

Nhập số phần tử của mảng: 7 Nhập các phần tử của mảng: a[0] = 1 a[1] = 2 a[2] = 5 a[3] = 6 a[4] = 3 a[5] = 1 a[6] = 9 Dãy số được sắp xếp tăng dần: 1 1 2 3 5 6 9

Trong bài này freetuts sẽ giới thiệu đến các bạn thuật toán sắp xếp chèn (Insertion Sort). Đây là một trong những thuật toán sắp xếp căn bản trong Java.

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 thuật toán sắp xếp chèn là gì và cách triển khai nó như thế nào trong Java. Ở cuối bài viết mình sẽ thực hành một bài tập đơn giản áp dụng thuật toán để các bạn dễ hiểu hơn.

Thuật toán sắp xếp chèn trong Java

Thuật toán sắp xếp chèn (Insertion Sort) trong Java là một trong những thuật toán sắp xếp đơn giản và phổ biến nhất trong lập trình. Thuật toán này hoạt động bằng cách chèn lần lượt các phần tử vào vị trí đúng của mình trong mảng.

Thuật toán sắp xếp chèn trong Java được phân loại là thuật toán sắp xếp trực tiếp, nghĩa là chúng ta sắp xếp trực tiếp các phần tử trong mảng. Thuật toán hoạt động bằng cách duyệt qua từng phần tử của mảng và chèn nó vào vị trí đúng của nó trong phần đã được sắp xếp.

Bài viết này được đăng tại [free tuts .net]

Cụ thể, thuật toán sắp xếp chèn hoạt động như sau:

• Bước 1: Duyệt từng phần tử trong mảng, bắt đầu từ phần tử thứ hai.
• Bước 2: So sánh phần tử hiện tại với các phần tử trước đó trong mảng.
• Bước 3: Nếu phần tử hiện tại nhỏ hơn phần tử đang xét, hoán đổi vị trí của chúng.
• Bước 4: Tiếp tục so sánh và hoán đổi vị trí cho đến khi phần tử hiện tại đứng đúng vị trí của nó trong mảng đã được sắp xếp.
• Bước 5: Lặp lại quá trình trên với các phần tử còn lại của mảng.

Đánh giá thuật toán sắp xếp chèn trong Java

Độ phức tạp thuật toán:

• Trường hợp tốt: O(n)
• Trung bình: O(n^2)
• Trường hợp xấu: O(n^2)
• Không gian bộ nhớ sử dụng: O(1)

Vừa rồi chúng ta vừa tìm hiểu qua khái niệm thuật toán sắp xếp chèn và cách thức hoạt động của thuật toán sắp xếp chèn trong Java. Bây giờ hãy cùng freetuts tìm hiểu cách thức triển khai của nó.

Ví dụ thuật toán sắp xếp Chèn trong Java

Trong ví dụ trên chúng ta thấy:

• Hàng đầu tiên mô phỏng trạng thái ban đầu của mảng(dãy số chưa sắp xếp).
• Từ hàng thứ 2 trở đi, ta tìm chèn số đang xét vào vị trí thích hợp để đảm bảo dãy số vẫn tăng dần.
• Và khi lặp hết tất cả các số trong mảng, ta có trạng thái đã sắp xếp ở hàng cuối cùng.

Như vậy, có thể thấy cách thức hoạt động của thuật toán sắp xếp chèn trong Java khá dễ hiểu và dễ triển khai.

Chương trình triển khai thuật toán sắp xếp chèn trong Java

Dưới đây là đoạn code minh họa ví dụ trên:

/

• Học lập trình Java miễn phí tại freetuts.net
• @author freetuts */ import java.util.Arrays; public class InsertionSort {

  public static void sort(int[] arr) {  
      int n = arr.length;  
      for (int i = 1; i < n; i++) {  
          int key = arr[i];  
          int j = i - 1;  
          while (j >= 0 && arr[j] > key) {  
              arr[j + 1] = arr[j];  
              j--;  
          }  
          arr[j + 1] = key;  
      }  
  }  
  public static void main(String[] args) {  
      int[] arr = {4, 3, 2, 10, 12, 1, 5, 6};  
      sort(arr);
      System.out.println("Học lập trình Java miễn phí tại freetuts.net");  
      System.out.println("Mảng sau khi được sắp xếp là: ");
      System.out.println(Arrays.toString(arr));  
  }  
  

  }

Kết quả:

Học lập trình Java miễn phí tại freetuts.net Mảng sau khi được sắp xếp là: [1, 2, 3, 4, 5, 6, 10, 12]

Qua bài này, freetuts đã giới thiệu cho các bạn về thuật toán sắp xếp chèn và cách triển khai thuật toán trong Java một cách dễ hiểu nhất, giúp các bạn có thể hiểu và áp dụng vào các bài toán khó và phức tạp hơn trong Java. Chúc các bạn thành công.