Tóm Tắt
1. Sắp xếp nổi bọt (Bubble Sort) trong Java
Đề bài : Viết chương trình Java sắp xếp một dãy số theo thứ tự tăng dần bằng thuật toán nổi bọt ( Bubble Sort ) .
Lời giải
Sắp xếp nổi bọt ( Bubble Sort ) là một giải thuật sắp xếp đơn thuần. Giải thuật sắp xếp này được thực thi dựa trên việc so sánh cặp thành phần liền kề nhau và tráo đổi thứ tự nếu chúng không theo thứ tự .
Giải thuật này không thích hợp sử dụng với các tập dữ liệu lớn khi mà độ phức tạp trường hợp xấu nhất và trường hợp trung bình là Ο(n2) với n là số phần tử.
Giải thuật sắp xếp nổi bọt là giải thuật chậm nhất trong số những giải thuật sắp xếp cơ bản. Giải thuật này còn chậm hơn giải thuật đổi chỗ trực tiếp mặc dầu số lần so sánh bằng nhau, nhưng do đổi chỗ hai thành phần kề nhau nên số lần đổi chỗ nhiều hơn .
Dưới đây là chương trình Java để giải bài sắp xếp nổi bọt ( Bubble Sort ) trong Java :
package vn.eLib.array;
public class SapXepNoBot {
public void bubbleSort(int arr[]) {
int temp;
int i,
j;
boolean swapped = false;
// lap qua tat ca cac so
for (i = 0; i < arr.length - 1; i++) {
swapped = false;
// vong lap thu hai
for (j = 0; j < arr.length - 1 - i; j++) {
System.out.print("So sanh cac phan tu: [" + arr[j] + ", " + arr[j + 1] + "]");
// kiem xa xem so ke tiep co nho hon so hien tai hay khong
// trao doi cac so.
// (Muc dich: lam noi bot (bubble) so lon nhat)
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
System.out.println(" => trao doi [" + arr[j] + ", " + arr[j + 1] + "]");
} else {
System.out.println(" => khong can trao doi.");
}
}
// neu khong can trao doi nua, tuc la
// mang da duoc sap xep va thoat khoi vong lap.
if (!swapped) {
break;
}
System.out.println("Vong lap thu " + (i + 1));
display(arr);
}
}
public void display(int arr[]) {
int i;
System.out.print("[");
// Duyet qua tat ca phan tu
for (i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.print("]n");
}
public static void main(String[] args) {
// khoi tao mang arr
int arr[] = {
6,
7,
0,
2,
8,
1,
3,
9,
4,
5
};
SapXepNoBot sapXepNoBot = new SapXepNoBot();
System.out.println("Mang du lieu dau vao: ");
sapXepNoBot.display(arr);
System.out.println("-----------------------------");
sapXepNoBot.bubbleSort(arr);
System.out.println("-----------------------------");
System.out.println("nMang sau khi da sap xep: ");
sapXepNoBot.display(arr);
}
}
Chạy chương trình Java trên cho hiệu quả như sau :
2. Sắp xếp chọn (Selection Sort) trong Java
Đề bài : Viết chương trình Java sắp xếp một dãy số theo thứ tự tăng dần bằng thuật toán chọn ( Selection Sort ) .
Lời giải
Giải thuật sắp xếp chọn ( Selection Sort ) là một giải thuật đơn thuần. Giải thuật sắp xếp này là một giải thuật dựa trên việc so sánh in-place, trong đó list được chia thành hai phần, phần được sắp xếp ( sorted list ) ở bên trái và phần chưa được sắp xếp ( unsorted list ) ở bên phải. Ban đầu, phần được sắp xếp là trống và phần chưa được sắp xếp là hàng loạt list bắt đầu .
Phần tử nhỏ nhất được lựa chọn từ mảng chưa được sắp xếp và được tráo đổi với phần bên trái nhất và thành phần đó trở thành thành phần của mảng được sắp xếp. Tiến trình này liên tục cho tới khi hàng loạt từng thành phần trong mảng chưa được sắp xếp đều được chuyển dời sang mảng đã được sắp xếp .
Dưới đây là chương trình Java để giải bài sắp xếp chọn ( Selection Sort ) trong Java :
package vn.eLib.array;
public class SapXepChon {
public void selectionSort(int arr[]) {
int indexMin,
i,
j;
// lap qua ta ca cac so
for (i = 0; i < arr.length - 1; i++) {
// thiet lap phan tu hien tai la min
indexMin = i;
// kiem tra phan tu hien tai co phai la nho nhat khong
for (j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[indexMin]) {
indexMin = j;
}
}
if (indexMin != i) {
System.out.println(" ==> Trao doi phan tu: [" + arr[i] + ", " + arr[indexMin] + "]");
// Trao doi cac so
int temp = arr[indexMin];
arr[indexMin] = arr[i];
arr[i] = temp;
}
System.out.println("Vong lap thu " + (i + 1));
display(arr);
}
}
public void display(int arr[]) {
int i;
System.out.print("[");
// Duyet qua tat ca phan tu
for (i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.print("]n");
}
public static void main(String[] args) {
// khoi tao mang arr
int arr[] = {
6,
7,
0,
2,
8,
1,
3,
9,
4,
5
};
SapXepChon sapXepChon = new SapXepChon();
System.out.println("Mang du lieu dau vao: ");
sapXepChon.display(arr);
System.out.println("-----------------------------");
sapXepChon.selectionSort(arr);
System.out.println("-----------------------------");
System.out.println("nMang sau khi da sap xep: ");
sapXepChon.display(arr);
}
Chạy chương trình Java trên cho hiệu quả như sau :
3. Sắp xếp chèn (Insertion Sort) trong Java
Đề bài : Viết chương trình Java sắp xếp một dãy số theo thứ tự tăng dần bằng thuật toán chèn ( Insertion Sort ) .
Lời giải
Sắp xếp chèn là một giải thuật sắp xếp dựa trên so sánh in-place. Ở đây, một list con luôn luôn được duy trì dưới dạng đã qua sắp xếp. Sắp xếp chèn là chèn thêm một thành phần vào list con đã qua sắp xếp. Phần tử được chèn vào vị trí thích hợp sao cho vẫn bảo vệ rằng list con đó vẫn sắp theo thứ tự .
Với cấu trúc tài liệu mảng, tất cả chúng ta tưởng tượng là : mảng gồm hai phần : một list con đã được sắp xếp và phần khác là những thành phần không có thứ tự. Giải thuật sắp xếp chèn sẽ triển khai việc tìm kiếm liên tục qua mảng đó, và những thành phần không có thứ tự sẽ được vận động và di chuyển và được chèn vào vị trí thích hợp trong list con ( của cùng mảng đó ) .
Giải thuật này không thích hợp sử dụng với các tập dữ liệu lớn khi độ phức tạp trường hợp xấu nhất và trường hợp trung bình là Ο(n2) với n là số phần tử.
Dưới đây là chương trình Java để giải bài sắp xếp chèn ( Insertion Sort ) trong Java :
package vn.eLib.array;
public class SapXepChen {
public void insertionSort(int arr[]) {
int valueToInsert;
int holePosition;
int i;
// lap qua tat ca cac so
for (i = 1; i < arr.length; i++) {
// chon mot gia tri de chen
valueToInsert = arr[i];
// lua chon vi tri de chen
holePosition = i;
// kiem tra xem so lien truoc co lon hon gia tri duoc chen khong
while (holePosition > 0 && arr[holePosition - 1] > valueToInsert) {
arr[holePosition] = arr[holePosition - 1];
holePosition--;
System.out.println("Di chuyen phan tu: " + arr[holePosition]);
}
if (holePosition != i) {
System.out.println(" Chen phan tu: " + valueToInsert + ", tai vi tri: " + holePosition);
// chen phan tu tai vi tri chen
arr[holePosition] = valueToInsert;
}
System.out.println("Vong lap thu " + i);
display(arr);
}
}
public void display(int arr[]) {
int i;
System.out.print("[");
// Duyet qua tat ca phan tu
for (i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.print("]n");
}
public static void main(String[] args) {
// khoi tao mang arr
int arr[] = {
6,
7,
0,
2,
8,
1,
3,
9,
4,
5
};
SapXepChen sapXepChen = new SapXepChen();
System.out.println("Mang du lieu dau vao: ");
sapXepChen.display(arr);
System.out.println("-----------------------------");
sapXepChen.insertionSort(arr);
System.out.println("-----------------------------");
System.out.println("nMang sau khi da sap xep: ");
sapXepChen.display(arr);
}
}
Chạy chương trình Java trên cho tác dụng như sau :
4. Sắp xếp nhanh (Quick Sort) trong Java
Đề bài : Viết chương trình Java sắp xếp một dãy số theo thứ tự tăng dần bằng thuật toán nhanh ( Quick Sort ) .
Lời giải
Giải thuật sắp xếp nhanh ( Quick Sort ) là một giải thuật hiệu suất cao cao và dựa trên việc chia mảng dữa liệu thành những mảng nhỏ hơn. Giải thuật sắp xếp nhanh chia mảng thành hai phần bằng cách so sánh từng thành phần của mảng với một thành phần được chọn gọi là thành phần chốt ( Pivot ) : một mảng gồm có những thành phần nhỏ hơn hoặc bằng thành phần chốt và mảng còn lại gồm có những thành phần lớn hơn hoặc bằng thành phần chốt .
Dưới đây là chương trình Java để giải bài sắp xếp nhanh ( Quick Sort ) trong Java :
package vn.eLib.array;
public class SapXepNhanh {
// ham de trao doi gia tri
public void swap(int arr[], int num1, int num2) {
int temp = arr[num1];
arr[num1] = arr[num2];
arr[num2] = temp;
}
// ham de chia mang thanh 2 phan, su dung phan tu chot (pivot)
public int partition(int arr[], int left, int right, int pivot) {
int leftPointer = left - 1;
int rightPointer = right;
while (true) {
while (arr[++leftPointer] < pivot) {
// khong lam gi
}
while (rightPointer > 0 && arr[--rightPointer] > pivot) {
// khong lam gi
}
if (leftPointer >= rightPointer) {
break;
} else {
System.out.println(" Phan tu duoc trao doi: " + arr[leftPointer] + ", " + arr[rightPointer]);
swap(arr, leftPointer, rightPointer);
}
}
System.out.println(" Phan tu chot duoc trao doi: " + arr[leftPointer] + ", " + arr[right]);
swap(arr, leftPointer, right);
display(arr);
return leftPointer;
}
// ham sap xep
public void quickSort(int arr[], int left, int right) {
if (right - left <= 0) {
return;
} else {
int pivot = arr[right];
int partitionPoint = partition(arr, left, right, pivot);
quickSort(arr, left, partitionPoint - 1);
quickSort(arr, partitionPoint + 1, right);
}
}
public void display(int arr[]) {
int i;
System.out.print("[");
// Duyet qua tat ca phan tu
for (i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.print("]n");
}
public static void main(String[] args) {
// khoi tao mang arr
int arr[] = {
6,
7,
0,
2,
8,
1,
3,
9,
4,
5
};
SapXepNhanh sapXepNhanh = new SapXepNhanh();
System.out.println("Mang du lieu dau vao: ");
sapXepNhanh.display(arr);
System.out.println("-----------------------------");
sapXepNhanh.quickSort(arr, 0, arr.length - 1);
System.out.println("-----------------------------");
System.out.println("nMang sau khi da sap xep: ");
sapXepNhanh.display(arr);
}
}
Javahạy chương trình Java trên cho tác dụng như sau :
5. Sắp xếp trộn (Merge Sort) trong Java
Đề bài : Viết chương trình Java sắp xếp một dãy số theo thứ tự tăng dần bằng thuật toán trộn ( Merge Sort ) .
Lời giải
Sắp xếp trộn ( Merge Sort ) là một giải thuật sắp xếp dựa trên giải thuật Chia để trị ( Divide and Javaonquer ). Với độ phức tạp thời hạn trường hợp xấu nhất là Ο ( n log n ) thì đây là một trong những giải thuật đáng được chăm sóc nhất .
Đầu tiên, giải thuật sắp xếp trộn chia mảng thành hai nửa và sau đó tích hợp chúng lại với nhau thành một mảng đã được sắp xếp .
Dưới đây là chương trình Java để giải bài sắp xếp trộn (Merge Sort) trong Java:
package vn.eLib.array;
public class SapXepTron {
public void merging(int arr[], int temp[], int low, int mid, int high) {
int l1,
l2,
i;
l1 = low;
l2 = mid + 1;
for (i = low; l1 <= mid && l2 <= high; i++) {
if (arr[l1] <= arr[l2]) {
temp[i] = arr[l1++];
} else {
temp[i] = arr[l2++];
}
}
while (l1 <= mid) {
temp[i++] = arr[l1++];
}
while (l2 <= high) {
temp[i++] = arr[l2++];
}
for (i = low; i <= high; i++) {
arr[i] = temp[i];
}
}
public void sort(int arr[], int temp[], int low, int high) {
int mid;
if (low < high) {
mid = (low + high) / 2;
sort(arr, temp, low, mid);
sort(arr, temp, mid + 1, high);
merging(arr, temp, low, mid, high);
// hien thi mang
display(arr);
} else {
return;
}
}
public void display(int arr[]) {
int i;
System.out.print("[");
// Duyet qua tat ca phan tu
for (i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.print("]n");
}
public static void main(String[] args) {
// khoi tao mang arr
int arr[] = {
6,
7,
0,
2,
8,
1,
3,
9,
4,
5
};
int temp[] = new int[10];
SapXepTron sapXeptron = new SapXepTron();
System.out.println("Mang du lieu dau vao: ");
sapXeptron.display(arr);
System.out.println("-----------------------------");
sapXeptron.sort(arr, temp, 0, arr.length - 1);
System.out.println("-----------------------------");
System.out.println("nMang sau khi da sap xep: ");
sapXeptron.display(arr);
}
}
Javahạy chương trình Java trên cho hiệu quả như sau :
Trên đây là 5 bài tập về những thuật toán sắp xếp trong Java mà eLib muốn ra mắt đến bạn. Có rất nhiều cách giải và còn rất nhiều dạng bài tập tương quan đến những thuật toán sắp xếp trong Java, bạn hoàn toàn có thể tìm hiểu thêm trên những bài viết của eLib. Chúc những bạn thành công xuất sắc !
Source: https://final-blade.com
Category: Kiến thức Internet
