Читайте также:
|
Тема: «Алгоритмы сортировки в массивах данных».
Целью лабораторной работы является освоение навыков:
· объявления в программе массивов различных типов: целого, вещественного, логического, символьного и строкового;
· организация сортировок массивов данных;
· конструкции циклов и работа с числами, символами и строками;
· организация возбуждения исключений в программах.
Задание: Разработать программу, в которой осуществляется сортировка различных типов данных.
Текст Java – программы
import java.util.*;
public class lab5
{
public static void main(String[] args)
{
int mas[][]=new int[7][5];
int mas1[][]=new int [7][5];
int mas2[][]=new int[7][5];
System.out.println("Заполнение массива ‹…’!!!!!!!!!!!!!!!!!!!!!!!!");
for (int i=0; i<7; i++)
{
for (int j=0; j<5; j++)
{
mas[i][j]=((i+4)*(j+2))-25; // случайное заполнение массива
System.out.print(mas[i][j]+ "\t");
}
System.out.println();
}
System.out.println("\n 1.Сформировать массив из первых (или последних) попавшихся отрицательных элементов каждой чётной строки и их индексов в исходной матрице. \n Если отрицательных элементов нет, результат должен быть равен 0.");
for (int i=0; i<7; i++) {
for (int j=0; j<5; j++) {
if (mas[i][j]<0)
if (i%2>0)
{
mas1[i][j]=mas[i][j]; mas2[i][j]=mas1[i][j];
}
}
}
int min=mas1[1][1];
int max=-999;
int sum=1;
int kol=0;
for (int i=0; i<7; i++) {
for (int j=0; j<5; j++) {
System.out.print("["+i+","+j+"]="+mas1[i][j]+" ");
sum=sum+mas1[i][j];
if (mas1[i][j]<0)
kol=kol+1;
if (mas1[i][j]<min)
min=mas[i][j];
if (mas1[i][j]>max)
if (mas1[i][j]<0)
max=mas1[i][j];
}
System.out.println();
}
System.out.println(" 2.Определить сумму отобранных элементов и их количество.");
System.out.println("Сумма отобранных элементов: "+sum+" \nКоличество таких элементов:"+kol);
System.out.println(" 3.Определить минимальное и максимальное значения из отобранных элементов и их координаты \n и поменять строки исходной матрицы, в которых они найдены, если номера строк разные.");
System.out.println("min="+min);
System.out.println("max="+max);
int k2=3,k1=1;
System.out.println("вывод результата");
for (int i=0; i<7; i++){
for (int j=0; j<5; j++)
{
int x=mas1[k1][j]; mas1[k1][j]=mas1[k2][j]; mas1[k2][j]=x;
}
}
for (int i=0; i<7; i++) {
for (int j=0; j<5; j++) {
System.out.print("["+i+","+j+"]="+mas1[i][j]+" ");
}
System.out.println();
}
}
}
Пример: Реализует простой, но эффективный алгоритм сортировки массива чисел.
public class SortNumbers {
/**
* Простой и эффективный способ сортировки больших наборов данных
**/
public static void sort(double[] nums) {
// Цикл по всем элементам массива, в котором производится сортировка.
// Поиск наименьшего элемента и его перемещение на первую позицию.
for(int i = 0; i < nums.length; i++) {
int min = i; // сохранить индекс наименьшего элемента
// поиск наименьшего элемента
for(int j = i; j < nums.length; j++) {
if (nums[j] < nums[min]) min = j;
}
// замена мест наименьшего элемента и i-го.
// элементы между 0 и i остаются отсортированными.
double tmp;
tmp = nums[i];
nums[i] = nums[min];
nums[min] = tmp;
}
}
/** Тестируем программу */
public static void main(String[] args) {
double[] nums = new double[10]; // создание массива для хранения чисел
for(int i = 0; i < nums.length; i++) // генерация случайных чисел
nums[i] = Math.random() * 100;
sort(nums); // сортировка
for(int i = 0; i < nums.length; i++) // вывод
System.out.println(nums[i]);
}
}
Пример: Реализует алгоритм «Решето Эратосфена», вычисляющий наибольшее простое число, не превосходящее заданное значение. Алгоритм находит простые числа путем исключения всех чисел, кратных меньшим простым.
public class Sieve {
public static void main(String[] args) {
// Вычислить все простые числа, не превосходящие заданное значение
// а если аргумент не задан, то не более 100.
int max = 100; // значение по умолчанию
try { max = Integer.parseInt(args[0]); } // анализируется аргумент
catch (Exception e) {} // Игнорируются исключения.
// Создание массива, в котором указано простое число или нет.
boolean[] isprime = new boolean[max+1];
// Предполагаем, что все числа простые.
for(int i = 0; i <= max; i++) isprime[i] = true;
// Но 0 и 1 не простые числа.
isprime[0] = isprime[1] = false;
// Чтобы вычислить простые числа до значения max, нужно убрать
// числа, кратные всем целым, меньшим, чем корень из max.
int n = (int) Math.ceil(Math.sqrt(max)); // используем java.lang.Math класс
// Для каждого целого i от 0 до n:
// Если i простое число, тогда никакое из кратных ему не простое,
// отметить в массиве. Если i не простое, то кратные ему
// уже удалены, следовательно пропустим этот случай.
for(int i = 0; i <= n; i++) {
if (isprime[i]) // Если i простое число,
for(int j = 2*i; j <= max; j = j + i) // цикл по кратным
isprime[j] = false; // они не простые.
}
// находим наибольшее простое:
int largest;
for(largest = max;!isprime[largest]; largest--); // тело цикла
// вывод результата
System.out.println("Наибольшее простое число, не превосходящее "
+ max +" это " + largest);
}
}
Пример: Улучшенная сортировка.
// Классы для сортировки многоязыковых строк
import java.text.Collator;
import java.text.CollationKey;
import java.util.Locale;
/**
* Класс, определяющий набор статических методов сортировки
**/
public class Sorter {
/**
* Интерфейс с методом compare() для сравнения двух объектов.
**/
public static interface Comparer {
/**
* сравнение объектов и их упорядочение:
* если (a > b) возврат значения > 0;
* если (a == b) возврат 0;
* если (a < b) возврат значения < 0.
**/
public int compare(Object a, Object b);
}
/**
* Альтернативный интерфейс для упорядочивания объектов. Если
* класс реализует интерфейс Comparable, то любые 2 экземпляра класса
* можно сравнивать вызовом метода compareTo().
**/
public static interface Comparable {
/**
* объекты сравниваются и упорядочиваются:
* если (this > other), то значение > 0
* если (this == other), то 0
* если (this < other), то значение < 0
**/
public int compareTo(Object other);
}
/**
* Внутренний объект Comparer (созданный безымянным классом)
* сравнивающий две строки ASCII кода.
* Его использует метод sortAscii.
**/
private static Comparer ascii_comparer = new Comparer() {
public int compare(Object a, Object b) {
return ((String)a).compareTo((String)b);
}
};
/**
* Внутренний объект Comparer. Используется для сравнения 2 объектов
* Comparable. Реализован в методе sort()
**/
private static Comparer comparable_comparer = new Comparer() {
public int compare(Object a, Object b) {
return ((Comparable)a).compareTo(b);
}
};
/** Массив строк ASCII сортируются по возрастанию */
public static void sortAscii(String[] a) {
// используется объект ascii_comparer
sort(a, null, 0, a.length-1, true, ascii_comparer);
}
/**
* Массив срок ASCII сортируется по возрастанию или убыванию
* в зависимости от аргумента up
**/
public static void sortAscii(String[] a, int from, int to, boolean up) {
// Note use of the ascii_comparer object
sort(a, null, from, to, up, ascii_comparer);
}
/** Массив строк ASCII сортируют без учета регистра */
public static void sortAsciiIgnoreCase(String[] a) {
sortAsciiIgnoreCase(a, 0, a.length-1, true);
}
/**
* Сортировка ASCII строк без учета регистра
**/
public static void sortAsciiIgnoreCase(String[] a, int from, int to,
boolean up) {
if ((a == null) || (a.length < 2)) return;
// создание вторичного массива строк,
// содержащего строчные символы.
String b[] = new String[a.length];
for(int i = 0; i < a.length; i++) b[i] = a[i].toLowerCase();
// сортировка вторичного массива
// и в соответствии с ним первичного массива.
// Сортировка не зависит от регистра, используется объект ascii_comparer
sort(b, a, from, to, up, ascii_comparer);
}
/**
* сортировка по возрастанию, принятая по умолчанию
**/
public static void sort(String[] a) {
sort(a, 0, a.length-1, true, false, null);
}
/**
* Если ignorecase == true, то различие регистра не воспринимается
**/
public static void sort(String[] a, int from, int to,
boolean up, boolean ignorecase) {
sort(a, from, to, up, ignorecase, null);
}
/**
* сортировка без различия в регистрах
**/
public static void sort(String[] a, int from, int to,
boolean up, boolean ignorecase,
Locale locale) {
// нет данных для сортировки
if ((a == null) || (a.length < 2)) return;
// Объект java.text.Collator позволяет использовать разные таблицы ascii
Collator c;
if (locale == null) c = Collator.getInstance();
else c = Collator.getInstance(locale);
// Учитывать ли регистр при сортировке.
if (ignorecase) c.setStrength(Collator.SECONDARY);
// Объект Collator создает массив объектов CollationKey,
// соответствующий строкам.
CollationKey[] b = new CollationKey[a.length];
for(int i = 0; i < a.length; i++) b[i] = c.getCollationKey(a[i]);
// Объект Comparer для сравнения
Comparer comp = new Comparer() {
public int compare(Object a, Object b) {
return ((CollationKey)a).compareTo((CollationKey)b);
}
};
// сортировка массива объектов CollationKey
sort(b, a, from, to, up, comp);
}
/** массив объектов Comparable сортируется по возрастанию */
public static void sort(Comparable[] a) {
sort(a, null, 0, a.length-1, true);
}
/**
* сортировка массива объектов Comparable по возрастанию и убыванию.
**/
public static void sort(Comparable[] a, int from, int to, boolean up) {
sort(a, null, from, to, up, comparable_comparer);
}
/**
* сортировка массива объектов Comparable по возрастанию и убыванию
**/
public static void sort(Comparable[] a, Object[] b,
int from, int to, boolean up) {
sort(a, b, from, to, up, comparable_comparer);
}
/**
* массив произвольных объектов сортируется по возрастанию
**/
public static void sort(Object[] a, Comparer c) {
sort(a, null, 0, a.length-1, true, c);
}
/**
* сортировка по возрастанию и убыванию
**/
public static void sort(Object[] a, int from, int to, boolean up,
Comparer c)
{
sort(a, null, from, to, up, c);
}
/**
* Процедура sort(), выполняющая сортировку
**/
public static void sort(Object[] a, Object[] b,
int from, int to,
boolean up, Comparer c)
{
// если нет элементов
if ((a == null) || (a.length < 2)) return;
// Основной алгоритм быстрой сортировки
int i = from, j = to;
Object center = a[(from + to) / 2];
do {
if (up) { // по возрастанию
while((i < to)&& (c.compare(center, a[i]) > 0)) i++;
while((j > from)&& (c.compare(center, a[j]) < 0)) j--;
} else { // по убыванию
while((i < to)&& (c.compare(center, a[i]) < 0)) i++;
while((j > from)&& (c.compare(center, a[j]) > 0)) j--;
}
if (i < j) {
Object tmp = a[i]; a[i] = a[j]; a[j] = tmp; // перестановка элементов
if (b!= null) { tmp = b[i]; b[i] = b[j]; b[j] = tmp; } // перестановка
}
if (i <= j) { i++; j--; }
} while(i <= j);
if (from < j) sort(a, b, from, j, up, c); // рекурсивная сортировка
if (i < to) sort(a, b, i, to, up, c);
}
/**
* вложенный класс, определяющий тестовую программу
**/
public static class Test {
/**
* подкласс ComplexNumber с интерфейсом Comparable
* и методом compareTo() для сравнения комплексных чисел.
**/
static class SortableComplexNumber extends ComplexNumber
implements Sorter.Comparable {
public SortableComplexNumber(double x, double y) { super(x, y); }
public int compareTo(Object other) {
return sign(this.magnitude()-((ComplexNumber)other).magnitude());
}
}
/** тестовая программа сортировки комплексных чисел. */
public static void main(String[] args) {
// сравнение по абсолютной величине
SortableComplexNumber[] a = new SortableComplexNumber[5];
for(int i = 0; i < a.length; i++)
a[i] = new SortableComplexNumber(Math.random()*10,
Math.random()*10);
// определение массива SortableComplexNumber и метода compareTo(),
System.out.println("Sorted by magnitude:");
Sorter.sort(a);
for(int i = 0; i < a.length; i++) System.out.println(a[i]);
// сортировка объектом Comparer
System.out.println("отсортированы по абсолютной величине:");
Sorter.sort(a, new Sorter.Comparer() {
public int compare(Object a, Object b) {
ComplexNumber i = (ComplexNumber)a;
ComplexNumber j = (ComplexNumber)b;
return sign((i.real() + i.imaginary()) -
(j.real() + j.imaginary()));
}
});
for(int i = 0; i < a.length; i++) System.out.println(a[i]);
// сортировка Comparer
System.out.println("отсортированы по сумме действительной и мнимой частей:");
Sorter.sort(a, 0, a.length-1, false, new Sorter.Comparer() {
public int compare(Object a, Object b) {
ComplexNumber i = (ComplexNumber) a;
ComplexNumber j = (ComplexNumber) b;
double result = i.real() - j.real();
if (result == 0) result = i.imaginary()-j.imaginary();
return sign(result);
}
});
for(int i = 0; i < a.length; i++) System.out.println(a[i]);
}
/** вспомогательная процедура */
public static int sign(double x) {
if (x > 0) return 1;
else if (x < 0) return -1;
else return 0;
}
}
}
Дата добавления: 2015-09-11; просмотров: 23 | Поможем написать вашу работу | Нарушение авторских прав |