Java: руководство для начинающих
Шрифт:
Результат выполнения данной программы выглядит следующим образом: Inside static block. Inside Constructor Square root of 2 is 1.4142135623730951 Square root of 3 is 1.7320508075688772
Как видите, статический блок выполняется еще до того, как будет создан какой-нибудь объект.
Пример для опробования 6.3. Быстрая сортировка
В главе 5 был рассмотрен простой способ так называемой пузырьковой сортировки, а кроме него, вкратце упоминались и более совершенные способы сортировки. В этом проекте предстоит реализовать один из самых лучших способов: быструю сортировку. Алгоритм быстрой сортировки был разработан Ч. Хоаром и назван его именем. На сегодняшний день это самый лучший универсальный алгоритм сортировки. Он не был продемонстрирован в главе 5 лишь потому, что реализовать быструю сортировку лучше всего с помощью рекурсии. В данном проекте
Быстрая сортировка опирается на принцип разделения. Сначала выбирается опорное значение (так называемый компаранд), и массив разделяется на две части. Все элементы, которые больше или равны разделяемому компаранду, помещаются в одну часть массива, а те элементы, которые меньше компаранда, — в другую часть. Затем процесс рекурсивно повторяется для каждой оставшейся части до тех пор, пока массив не окажется отсортированным. Допустим, имеется массив, содержащий последовательность символов f edacb, а в качестве компаранда выбран символ d. На первом проходе массив будет частично упорядочен следующим образом: Исходные данные f e d a с b Проход 1 b с a d e f
Этот процесс повторяется для каждой части: Ьса и def. Как видите, процесс рекурсивен по своей сути, поэтому рекурсивный способ лучше всего подходит для реализации быстрой сортировки.
Компаранд можно выбрать двумя способами: случайно либо вычислив среднее значение части элементов массива. Эффективность сортировки окажется оптимальной в том случае, когда компаранд выбран как раз посредине диапазона значений элементов, содержащихся в массиве, но зачастую выбрать такое значение непросто. Если же выбрать компаранд случайным образом, то вполне возможно, что он окажется на краю диапазона. Но и в этом случае алгоритм быстрой сортировки будет действовать правильно. В том варианте быстрой сортировки, который реализуется в данном проекте, в качестве компаранда выбирается элемент, находящийся посередине массива.
Последовательность действий
Создайте новый файл QSDemo. j ava.
Создайте сначала класс Quicksort, код которого приведен ниже. // Пример для опробования 6.3. Простая версия класса Quicksort, // реализующего быструю сортировку, class Quicksort { // организовать вызов конкретного метода быстрой сортировки static void qsort(char items[]) { qs(items, 0, items.length-1); } // Рекурсивная версия метода быстрой сортировки символов, private static void qs(char items[], int left, int right) { int i, j; char x, y; i = left; j = right; x = items[(left+right)/2]; do { while((items[i] < x) && (i < right)) i++; while((x < items[j]) && (j > left)) j—; if(i <= j) { у = items[i]; items[i] = items[j]; items[j] = y; i++; j—; } } while (i <= j); if(left < j) qs(items, left, j); if(i < right) qs(items, i, right); } }
Для упрощения интерфейса в классе Quicksort предоставляется метод qsort , из которого вызывается метод qs , фактически выполняющий сортировку. Такой подход позволяет выполнять сортировку, передавая методу лишь имя массива и не осуществляя первоначальное разделение. А поскольку метод qs используется только в классе, он определяется как private.
Для того чтобы воспользоваться классом Quicksort, достаточно вызвать метод Quicksort. qsort . Этот метод определен как static, и поэтому для его вызова достаточно указать имя класса, а создавать объект не обязательно. По завершении работы этого метода массив будет отсортирован. Данная версия программы работает только с символьными массивами, но вы можете адаптировать ее для сортировки массивов любого типа.
Ниже приведен весь исходный код программы, демонстрирующей применение класса Quicksort. // Пример для опробования 6.3. Простая версия класса Quicksort, // реализующего быструю сортировку, class Quicksort { // организовать вызов конкретного метода быстрой сортировки static void qsort(char items[]) { qs(items, 0, items.length-1); } // Рекурсивная версия метода быстрой сортировки символов, private static void qs(char items[], int left, int right) { int i, j; char x, y; i = left; j = right; x = items[(left+right)/2]; do { while((items[i] < x) && (i < right)) i++; while((x < items[j]) && (j > left)) j—; if(i <= j) { у = items[i]; items[i] = items[j]; items[j] = y; i++; j—; } } while (i <= j); if(left < j) qs(items, left, j); if(i < right) qs(items, i, right); } } class QSDemo { public static void main(String args[]) { char a [ ] = { 'd\ 'x', 'a', 'r', 'p\ 'j', 'i' }; int i; System.out.print("Original array: "); for(i=0; i < a.length; i++) System.out.print(a[i]) ; System.out.println; // отсортировать массив Quicksort.qsort(a); System.out.print("Sorted array: "); for(i=0; i < a.length; i++) System.out.print(a[i]); } } Вложенные и внутренние классы
В Java определены вложенные классы. Вложенным называется такой класс, который объявляется в другом классе. Вложенные классы не относятся к базовым языковым средствам Java. Они даже не поддерживались до появления версии Java 1.1, хотя с тех пор часто применяются в реальных программах, и поэтому о них нужно знать.
Вложенный класс не может существовать независимо от объемлющего класса, потому что последний ограничивает область его действия. Если вложенный класс объявлен в пределах области действия объемлющего класса, он становится членом последнего. Имеется также возможность объявить вложенный класс, который станет локальным в пределах блока.
Существуют два типа вложенных классов. Одни вложенные классы объявляются с помощью модификатора доступа static, а другие — без него. В этой книге будет рассматриваться только нестатический вариант вложенных классов. Классы такого типа называются внутренними. Внутренний класс имеет доступ ко всем переменным и методам внешнего (т.е. объемлющего) класса и может обращаться к ним непосредственно, как и все остальные нестатические члены внешнего класса. Иногда внутренний класс используется для предоставления услуг объемлющему классу. Ниже приведен пример применения внутреннего класса для вычисления различных значений в объемлющем его классе. // Применение внутреннего класса, class Outer { int nums[]; Outer(int n[]) { nums = n; } void Analyze { Inner inOb = new Inner; System.out.println("Minimum: 11 + inOb.minO); System.out.println("Maximum: " + inOb.maxO); System.out.println("Average : " + inOb.avgO); } // Внутренний класс. class Inner { int min { int m = nums[0]; for (int i=l; i < nums.length; i++) if(nums[i] < m) m = nums[i]; return m; } int max { int m = nums[0]; for (int i=l; i < r^urns. length; i++) if(nums[i] > m) m = nums[i]; return m; } int avg { int a = 0; for(int i=0; i < nums.length; i++) a += nums[i]; return a / nums.length; } } } class NestedClassDemo { public static void main(String args[]) { int x[] = { 3, 2, 1, 5, 6, 9, 7, 8 }; Outer outOb = new Outer(x); outOb.Analyze; } }
Результат выполнения данной программы выглядит следующим образом: Minimum: 1 Maximum: 9 Average: 5
В данном примере внутренний класс Inner обрабатывает массив nums, являющийся членом класса Outer. Как упоминалось выше, вложенный класс имеет доступ к членам объемлющего класса, и поэтому он может непосредственно обращаться к массиву nums. А вот обратное не справедливо. Так, например, метод analyze не может непосредственно вызвать метод min , не создав объект типа Inner.
Как упоминалось выше, класс можно вложить в области действия блока. В итоге получается локальный класс, недоступный за пределами блока. В следующем примере программы класс ShowBits, созданный в примере для опробования 5.3, преобразуется таким образом, чтобы стать локальным. // Применение класса ShowBits в качестве локального, public static void main(String args[]) { class LocalClassDemo { // Внутренний вариант класса ShowBits. // Локальный класс, вложенный в метод. class ShowBits { int numbits; ShowBits(int n) { numbits = n; } void show(long val) { long mask = 1; // сдвинуть влево для установки единицы в нужной позиции mask <<= numbits-1; int spacer = 0; for(; mask != 0; mask >»= 1) { if((val & mask) != 0) System.out.print("1"); else System, out .pri-nt ("0") ; spacer++; if((spacer % 8) ==0) { System.out.print(" "); spacer = 0; } } System.out.println ; } } for(byte b = 0; b < 10; b++) { ShowBits byteval = new ShowBits(8); System.out.print(b + " in binary: "); byteval.show(b); } } }
Выполнение этой программы дает следующий результат: 0 in binary: 00000000 1 in binary: 00000001 2 in binary: 00000010 3 in binary: 00000011 4 in binary: 00000100 5 in binary: 00000101 6 in binary: 00000110 7 in binary: 00000111 8 in binary: 00001000 9 in binary: 00001001
В данном примере класс ShowBits недоступен за пределами метода main , а следовательно, попытка получить доступ к нему из любого метода, кроме main , приведет к ошибке.
И последнее замечание: внутренний класс может быть безымянным. Экземпляр безымянного, или анонимного, внутреннего класса создается при объявлении класса с помощью оператора new. Безымянные внутренние классы будут подробнее рассмотрены в главе 15. Аргументы переменной длины