Я пытался отсортировать свой теперь комбинированный массив от наименьшего к наибольшему
Последние несколько дней я самостоятельно практиковался в том, как сортировать массивы Java. Я хочу отсортировать теперь объединенный массив от наименьшего к наибольшему. Я борюсь и нуждаюсь в руководстве. Может кто-нибудь объяснить мне, что я делаю неправильно? Я хочу учиться на своих нынешних ошибках.
КОД:
public static void main(String[] args) {
// merge these arrays: ([0,3,4,31],[4,6,30])
// process below is to create an array to fit the lengths of arr3 and 4
int[] arr3 = { 0, 3, 4, 31 };
int[] arr4 = { 4, 6, 30 };
int[] arr5 = new int[arr3.length + arr4.length];
// this loop gets the first indices of arr3
for (int i = 0; i < arr3.length; i++) {
arr5[i] = arr3[i];
}
// this array concat elements of arr4
for (int k = 0; k < arr4.length; k++) {
arr5[arr3.length + k] = arr4[k]; //
}
int small = 0;
int large = arr5.length - 1;
for (int f = 0; f < arr5.length; f++) {
if (arr5[f] < arr5[small]) {
arr5[small] = arr5[f];
small++;
} else {
arr5[large] = arr5[f];
large--;
}
}
// prints out the new array
System.out.println(Arrays.toString(arr5));
}
}
Вывод, который я пытаюсь получить в консоли вывода:
[0,3,4,4,6,30,31]
Что я получаю вместо этого:
[0, 3, 4, 31, 4, 3, 0]
Ответы 2
Если два массива, которые вы хотите объединить, всегда уже отсортированы, вы можете использовать один цикл с двумя переменными, хранящими текущие индексы в каждом массиве и каждый раз сравнивая соответствующие значения, чтобы найти меньшее.
int idx = 0, idx2 = 0;
for(int i = 0; i < arr5.length; i++){
if (idx2 == arr4.length || idx < arr3.length && arr3[idx] < arr4[idx2]){
arr5[i] = arr3[idx++];
} else {
arr5[i] = arr4[idx2++];
}
}
Demo
В противном случае самым простым решением будет использование пузырьковой сортировки (если вы не можете использовать java.util.Arrays.sort).
for(int i = 0; i < arr5.length; i++){
for(int j = 1; j < arr5.length; j++){
if (arr5[j] < arr5[j-1]){
final int temp = arr5[j];
arr5[j] = arr5[j-1];
arr5[j-1] = temp;
}
}
}
В среднем лучшие алгоритмы сортировки имеют временную сложность O(n log n), где находится ваш основной цикл:
for (int f = 0; f < arr5.length; f++) {
if (arr5[f] < arr5[small]) {
arr5[small] = arr5[f];
small++;
} else {
arr5[large] = arr5[f];
large--;
}
}
Имеет сложность O(n), что означает, что чего-то не хватает. Наиболее простой сортировкой является пузырьковая сортировка:
for(int i=0; i < arr5.length; i++){
for(int j=1; j < arr5.length -i ; j++){
if (arr5[j-1] > arr5[j]){
//swap elements
int temp = arr5[j-1];
arr5[j-1] = arr5[j];
arr5[j] = temp;
}
}
}
Который имеет сложность O(n^2). Этот алгоритм является отправной точкой для вас; взгляните на здесь более подробное объяснение, включая иллюстрации.