Java: руководство для начинающих (ЛП)

В алгоритме пузырьковой сортировки соседние элементы массива сравниваются и меняются, если требуется, местами. При этом малые значения сдвигаются к одному краю массива, а большие значения — к другому. Этот процесс напоминает всплывание пузырьков воздуха на разные уровни в емкости с жидкостью, откуда и произошло название данного алгоритма. Пузырьковая сортировка предполагает обработку массива в несколько проходов. Элементы, взаимное расположение которых отличается от требуемого, меняются местами. Число проходов должно быть таким, чтобы все элементы непременно встали на свои места. Максимальное количество проходов должно быть на один меньше, чем число элементов в массиве. Ниже приведен исходный код, составляющий основу алгоритма пузырьковой сортировки. Сортируемый массив называется nums. // Это пример реализации алгоритма пузырьковой сортировки. for(a=l; а < size; а++) for(b=size-l; b >= a; b—) { if(nums[b-l] > nums[b]) { // если требуемый порядок следования // не соблюдается, поменять элементы местами t = nums[b—1]; nums[b-l] = nums[b]; nums[b] = t; } } Как видите, в приведенном выше фрагменте кода используются два цикла for. Во внутреннем цикле сравниваются соседние элементы массива и выявляются элементы, находящиеся не на своих местах. Если обнаружен элемент, положение которого отличается от требуемого, то два соседних элемента меняются местами. На каждом проходе наименьший элемент передвигается на один шаг в нужное положение. Внешний цикл обеспечивает повторение описанного выше процесса до тех пор, пока сортировка массива не будет завершена.

Ниже приведен весь исходный код программы из файла Bubble. j ava. /* Пример для опробования 5.1. Демонстрация алгоритма пузырьковой сортировки. */ class Bubble { public static void main(String args[]) { int nums[] = { 99, -10, 100123, 18, -978, 5623, 463, -9,, 287, 49 }; int a, b, t; int size; size = 10; // Количество элементов для сортировки // отобразить исходный массив System.out.print("Original array is:"); for(int i=0; i < size; i++) System.out.print(" " + nums[i]); System.out.println; // реализовать алгоритм пузырьковой сортировки for(a=l; а < size; а++) for(b=size-l; b >= a; b—) { if(nums[b-l] > nums[b]) { // если требуемый порядок // следования не соблюдается, поменять элементы местами t = nums[b-l]; nums[b-l] = nums[b]; nums[b] = t; } } // отобразить отсортированный массив System, out .print ("Sorted array is: "); for(int i=0; i < size; i++) System.out.print(" " + nums[i]); System.out.println; } }

Ниже приведен результат выполнения данной программы. Original array is: 99 -10 100123 18 -978 5623 463 -9 287 49 Sorted array is: -978 -10 -9' 18 49 99 287 463 5623 100123

Как упоминалось выше, пузырьковая сортировка отлично подходит для обработки мелких массивов, но при большом числе элементов массива она становится неэффективной. Более универсальным является алгоритм быстрой сортировки, но для его эффективной реализации необходимы языковые средства Java, которые рассматриваются далее в этой книге. Многомерные массивы

Несмотря на то что одномерные массивы употребляются чаще всего, в программировании, безусловно, применяются и многомерные (двух-, трехмерные и т.д.) массивы. В Java многомерные массивы представляют собой массивы массивов. Двумерные массивы

Среди многомерных массивов наиболее простыми являются двумерные массивы. Двумерный массив, по существу, представляет собой ряд одномерных массивов. Для того чтобы объявить двумерный целочисленный табличный массив table размерами 10x20, следует написать такое выражение: int tablet][] = new int[10][20];

Обратите особое внимание на объявление этого массива. В отличие от некоторых других языков программирования, где размеры массива разделяются запятыми, в Java они заключаются в отдельные квадратные скобки. Так, для обращения к элементу массива table по индексам 3 и 5 следует указать table [ 3 ] [ 5 ].

В следующем примере двумерный массив заполняется числами от 1 до 12: // Демонстрация двумерного массива, class TwoD { public static void main(String args[]) { int t, i; int table [][] = new int[3][4]; for(t=0; t < 3; ++t) { for(i=0; i < 4; ++i) { table[t][i] = (t*4)+i+l; System.out.print(table[t][i] + " "); } System.out.println ; } } }

В данном примере элемент table [0] [0] будет содержать значение 1, элемент table [0] [ 1 ] — значение 2, элемент table [0] [2] — значение 3 и так далее, а элемент table [2 ] [ 3 ] — значение 12. Структура данного массива наглядно показана на рис. 5.1. Нерегулярные массивы