Java - Sắp xếp mảng tăng dần sử dụng phương pháp nổi bọt (Bubble sort).

Viết chương trình sắp xếp tăng dần các phần tử trong mảng bằng phương pháp nổi bọt (Bubble sort).

Bài giải

-------------------- ######## --------------------

Trong phần bài học, tôi đã hướng dẫn các bạn phương pháp phương pháp sắp xếp thông qua phép đổi chỗ trực tiếp (Exchange sort). Ngoài ra, chúng ta còn một phương pháp sắp xếp cũng khá phổ biến mà tôi sẽ sử dụng trong bài tập này đó là phương pháp nổi bọt (Bubble sort). Ý tưởng chính của phương pháp nổi bọt là các phần tử trong mảng sẽ được duyệt từ đáy lên đỉnh. Trên đường duyệt, nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho nhau. Do đó, trong lần duyệt đầu tiên, phần tử có giá trị nhỏ nhất sẽ được chuyển lên đỉnh. Lần duyệt thứ 2, khóa có giá trị nhỏ thứ 2 được chuyển lên vị trí thứ 2... Và cứ tiếp tục như thế cho đến khi toàn bộ mảng các phần tử đã được sắp xếp theo thứ tự tăng dần.

Bài giải
public static void main(String[] args) {
	int n, tempSort;	// số phần tử của mảng
	Scanner scanner = new Scanner(System.in);
		
	// nếu n < 0 thì phải nhập lại
	do {
		System.out.println("Nhập vào số phần tử của mảng: ");
		n = scanner.nextInt();
	} while (n < 0);
		
	// khai báo và cấp phát bộ nhớ cho mảng
	int array[] = new int[n];
		
	// nhập giá trị các phần tử cho mảng
	for (int i = 0; i < n; i++) {
		System.out.print("Nhập phần tử thứ " + i + ": ");
		array[i] = scanner.nextInt();
	}
		
	// hiển thị mảng ban đầu
	System.out.println("\nMảng ban đầu: ");
	for (int i = 0; i < n; i++) {
		System.out.print(array[i] + "\t");
	}
		
	// sắp xếp mảng sử dụng phương pháp Bubble sort 
	// duyệt i từ 0 đến n - 2
	// sau mỗi lần duyệt j = n - 1 đến j >= 1
	// thì sẽ tìm được phần tử nhỏ nhất
	// sau đó tăng i lên 1 và quay lại duyệt j
	// khi i > n - 1 thì ngừng vòng lặp
	for (int i = 0; i < n - 1; i++) {
		for (int j = n - 1; j >= 1; j--) {
			// nếu phần tử đứng sau nhỏ hơn phần tử đứng trước
			// thì đổi chỗ 2 phần tử đó cho nhau
			// với cách sắp xếp này thì trong lần duyệt đầu tiên
			// phần tử nhỏ nhất sẽ được chuyển lên trên cùng.
			if (array[j] < array[j - 1]) {
				tempSort = array[j];
				array[j] = array[j-1];
				array[j-1] = tempSort;
			}
		}
	}
		
	System.out.println("\nMảng sau khi sắp xếp: ");
	for (int i = 0; i < n; i++) {
		System.out.print(array[i] + "\t");
	}
}

Kết quả sau khi biên dịch chương trình:

ketqua baitap2mang1chieu PNG

Nguồn: freetuts.net

Tham khảo
Java - Nhập mảng và thực hiện các thao tác trên mảng.
Java - Sắp xếp mảng tăng dần sử dụng phương pháp nổi bọt (Bubble sort).
Java - Tìm kiếm một phần tử sử dụng trong mảng sử dụng thuật tìm kiếm nhị phân.
Java - Kiểm tra mảng một chiều vừa nhập có phải là mảng đối xứng hay không?
Java - Tìm và in ra màn hình số lượng số nguyên lẻ, số lượng số nguyên chẵn trong mảng.
Java - Xóa phần tử có giá trị k trong mảng (k nhập từ bàn phím).
Java - Nhập mảng và thực hiện tách các số chẵn và lẻ trong mảng sang hai mảng khác.
Java - Tách một nửa đầu của mảng ban đầu sang mảng thứ nhất và nửa còn lại sang mảng thứ hai.
Java - Viết chương trình hiển thị các phần tử chia hết cho 5 trong mảng.
Java - Đếm số lần xuất hiện của 1 phần tử được nhập từ bàn phím.
Java - Bài tập tổng hợp các thao tác trên mảng.
Java - Viết chương trình nhập mảng sao cho không có phần tử nào trùng nhau.