Microsoft Word кл программирование на Java 2020 Зорина docx


Реализация алгоритмов сортировок в Java программах



Pdf көрінісі
бет33/65
Дата17.10.2023
өлшемі3,23 Mb.
#117230
түріРеферат
1   ...   29   30   31   32   33   34   35   36   ...   65
Байланысты:
Лекции

Реализация алгоритмов сортировок в Java программах. 
Сортировка является процесс упорядочивания списка элементов (организация 
в определенном порядке). Процесс сортировки основан на упорядочивании 
конкретных значений, например: 

сортировка списка результатов экзаменов баллов в порядке возрастания 
результата; 

сортировка списка людей в алфавитном порядке по фамилии. 
Есть много алгоритмов для сортировки списка элементов, которые различаются 
по эффективности. Мы рассмотрим два конкретных алгоритма: 

сортировка выбором; 

сортировка вставками. 
Сортировка выбором. 
Подход – сортировка выбором: 
– 
выбрать значение и поместить его на его окончательное место в списке; 
– 
повторить для всех остальных значений элементов; 
Более детально: 


66 
– 
найти наименьшее значение в списке элементов; 
– 
поменять его со значением в первого элемента; 
– 
найти следующее наименьшее значение в списке; 
– 
поменять его со значением второго элемента; 
– 
повторять, пока все значения не будут находятся на своих местах. 
Пример приведен на рисунке 5.4: 
Рисунок 5.4 – Алгоритм сортировки выбором
Каждый раз, наименьшее оставшееся значение найдено, то происходит обмен с 
элементом на "следующей" позиции. 
Обработка алгоритма выбора сортировки включает в себя обмен значениями 
двух элементов. Для выполнения операции обмена требуется три оператора 
присваивания и переменная для временного хранения значения: 
temp = first; 
first = second; 
second = temp; 
Методу сортировки все-равно, что именно он будет сортировать, ему только 
необходимо иметь возможность вызвать метод 
compareTo()
. Это обеспечивается 
использованием интерфейса 
Comparable 
как типа параметра. Кроме того, таким 
образом каждый класс “для себя” решает, что означает для одного объекта, быть 
меньше, чем другой. 
public class Contact implements Comparable{ 
private String firstName, lastName, phone; 
public Contact (String first, String last, String 
telephone) { 
firstName = first; 
lastName = last; 


67 
phone = telephone; 

public String toString () { return lastName + ", " + 
firstName + "\t" + phone;} 
public boolean equals (Object other) { 
return 
(lastName.equals(((Contact)other).getLastName()) && 
firstName.equals(((Contact)other).getFirstName())); 

public String getFirstName () {return firstName; } 
public String getLastName () {return lastName;} 
public int compareTo (Object other) 

int result; 
String otherFirst = 
((Contact)other).getFirstName(); 
String otherLast = ((Contact)other).getLastName(); 
if (lastName.equals(otherLast)) 
result = firstName.compareTo(otherFirst); 
else 
result = lastName.compareTo(otherLast); 
return result; 




Достарыңызбен бөлісу:
1   ...   29   30   31   32   33   34   35   36   ...   65




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет