Java Core - Sắp xếp nổi bọt trong java
Sắp xếp nổi bọt (Bubble Sort) trong java
Định nghĩa sắp xếp nổi bọt: xuất phát từ phần tử cuối danh sách ta tiến hành so sánh với phần tử bên trái của nó. Nếu phần tử đang xét có khóa nhỏ hơn phần tử bên trái của nó ta tiến đưa nó về bên trái của dãy bằng cách hoán vị với phần tử bên trái của nó. Tiếp tục thực hiện như thế đối với bài toán có n phần tử thì sau n –1 bước ta thu được danh sách tăng dần.
ví dụ: sử dụng thuật toán Bubble Sort sắp xếp dãy số theo thứ tự tăng dần.
Input: 18 9 33 4 84 32
Output: 4 9 18 32 33 84
Sắp xếp nổi bọt (Bubble Sort)
Chương trình sau dãy số theo tứ tự tăng dần bằng thuật toán sắp xếp nổi bọt:
package com.hiepsiit.baitap;
import java.util.Scanner;
public class bubbleSort {
private static void nhap_mang(int []A, int n) {
Scanner scn = new Scanner(System.in);
for(int i = 0; i < n; i++) {
System.out.print("A[ "+i+" ]: ");
A[i] = scn.nextInt();
}
}
private static void xuat_mang(int []A, int n) {
Scanner scn = new Scanner(System.in);
for(int i = 0; i < n; i++) {
System.out.println("A[ "+i+" ]: "+A[i]);
}
}
private static void hoan_vi(int []A, int a, int b) {
int temp = A[a];
A[a] = A[b];
A[b] = temp;
}
private static void sap_xep_noi_bot(int []A, int n) {
for(int i=0; i<n-1; i++) {
for(int j=n-1; j>i; j--) {
if(A[j]<A[j-1]) {
hoan_vi(A, j, j-1);
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int []A;
int n = 0;
Scanner scn = new Scanner(System.in);
System.out.print("Nhập số phần tử: ");
n = scn.nextInt();
A = new int[n];
nhap_mang(A, n);
System.out.println("Mảng sau khi sắp xếp (Bubble Sort)");
sap_xep_noi_bot(A, n);
xuat_mang(A, n);
}
}
kết quả: