|
package vn.viettuts.baitap.array;
import java.util.Scanner;
/**
* Chương trình sắp xếp mảng theo thứ tự tăng dần,
* sau đó chèn phần tử k vào mà vẫn đảm bảo mảng là 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: ");
for (int i = 0; i < n; i++) {
System.out.printf("a[%d] = ", i);
arr[i] = scanner.nextInt();
}
System.out.print("Nhập phần tử k = ");
int k = scanner.nextInt();
// sắp xếp dãy số theo thứ tự tăng dần
sortASC(arr);
System.out.print("Sắp xếp mảng tăng dần: ");
show(arr);
System.out.printf(" Chèn phần tử %d vào mảng.", k);
arr = insert(arr, k);
System.out.print(" Mảng sau khi chè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
*/
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;
}
}
}
}
/**
* chèn phần tử vào mảng số nguyên tăng dần
* sau khi chèn mảng vẫn duy trì thứ tự tăng dần
*
* @param arr: mảng số nguyên tăng dần
* @param k: phần tử chèn vào mảng arr
*/
public static int [] insert(int [] arr, int k) {
int arrIndex = arr.length - 1;
int tempIndex = arr.length;
int [] tempArr = new int [tempIndex + 1];
boolean inserted = false;
for (int i = tempIndex; i >= 0; i--) {
if (arrIndex > -1 && arr[arrIndex] > k) {
tempArr[i] = arr[arrIndex--];
} else {
if (!inserted) {
tempArr[i] = k;
inserted = true;
} else {
tempArr[i] = arr[arrIndex--];
}
}
}
return tempArr;
}
/**
* in các phần tử của mảng ra màn hình
*
* @param arr: mảng các số nguyên
*/
public static void show(int [] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
|
