By GokiSoft.com| 15:39 10/07/2023|
Java Advanced

Bài tập - Giải thuật sắp xếp - Tìm kiếm trong Java - Lập trình Java nâng cao

Bài 1: Nhập vào mảng số nguyên gồm N phần tử -> Sử dụng giải thuật quick sort để sắp xếp mảng theo thứ tự tăng dần -> Hiển thị kết quả ra màn hình

Bài 2: Nhập vào chuỗi s1 từ bàn phím, không sử dụng Pattern/Matcher -> yêu cầu tìm kiếm tất cả các chuỗi con trong s1 tuân theo các quy tắc sau: abb (a -> [a-z]{2,5}, b -> [0-9]{2,4}

Tags:

Phản hồi từ học viên

5

(Dựa trên đánh giá ngày hôm nay)

Hieu Ngo [community,C2009G]
Hieu Ngo

2021-09-04 06:03:00


#Main.java


import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public int partition(ArrayList<Integer> arr, int low, int high) {
        int pivot = arr.get(high);
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr.get(j) < pivot) {
                i++;
                // swap arr[i] và arr[j]
                int temp = arr.get(i);
                arr.set(i, arr.get(j));
                arr.set(j, temp);
            }
        }
        // swap arr[i+1] và arr[high] (hoặc pivot)
        int temp = arr.get(i + 1);
        arr.set(i + 1, arr.get(high));
        arr.set(high, temp);

        return i + 1;
    }
    public void quirkSort(ArrayList<Integer> arr, int low, int high) {
        if(low < high) {
            int pi = partition(arr, low, high);
            quirkSort(arr, low, pi-1);
            quirkSort(arr,pi+1,high);
        }
    }
    public static void main(String [] args) {
        int n;
        ArrayList<Integer> arr = new ArrayList<>();
        System.out.println("Enter N");
        n = (new Scanner(System.in)).nextInt();
        for(int i =0; i<n; i++) {
            System.out.println(String.format("arr[%d] =" ,i));
            arr.add((new Scanner(System.in)).nextInt());
        }
        for(Integer i : arr) {
            System.out.print(i+" ");
        }
        System.out.println("After sort:");
        Main sort = new Main();
        sort.quirkSort(arr, 0,n-1);

        for(Integer i : arr) {
            System.out.print(i+" ");

        }
    }

}