импортировать java.util.Random;
/**
* Сортировка тестового класса
*
* Классификация алгоритмов сортировки следующая: 1. Сортировка вставкой (сортировка прямой вставкой, сортировка половинной вставкой, сортировка Хилла 2. Сортировка обменом (пузырьковая сортировка, быстрая сортировка);
* 3. Сортировка выбором (сортировка прямым выбором, сортировка кучей). 4. Сортировка слиянием. 5. Поразрядная сортировка;
*
* Что касается выбора метода сортировки: (1) Если n мало (например, n≤50), можно использовать сортировку прямой вставкой или прямым выбором.
* Когда размер записи небольшой, сортировка прямой вставкой лучше; в противном случае, поскольку количество записей, перемещаемых прямым выбором, меньше, чем при прямой вставке, сортировка прямым выбором лучше.
* (2) Если исходное состояние файла в основном в порядке (имеется в виду положительный порядок), следует использовать прямую вставку, пузырьковую или случайную быструю сортировку;
* (3) Если n велико, следует использовать метод сортировки с временной сложностью O(nlgn): быстрая сортировка, пирамидальная сортировка или сортировка слиянием.
*
*/
общественный класс Сортировка {
/**
* Метод инициализации тестового массива
*
* @return инициализированный массив
*/
общественный int[] createArray() {
Случайный случайный = новый случайный();
массив int[] = новый int[10];
для (int я = 0; я <10; я++) {
array[i] = random.nextInt(100) - random.nextInt(100); // Генерируем два случайных числа и вычитаем их, чтобы убедиться, что в сгенерированных числах есть отрицательные числа.
}
System.out.println("==========исходная последовательность==========");
PrintArray (массив);
возвращаемый массив;
}
/**
* Вывести элементы массива на консоль
*
* @param источник
*/
public void printArray(int[] data) {
для (int i: данные) {
System.out.print(i + " ");
}
Система.out.println();
}
/**
* Поменяйте позиции двух указанных элементов массива
*
* данные @param
* @парам х
* @param y
*/
частный недействительный своп (int [] данные, int x, int y) {
интервал темп = данные [х];
данные[х] = данные[y];
данные [y] = температура;
}
/**
* Пузырьковая сортировка ---- тип обменной сортировки.
* Метод: сравнить два соседних элемента и при необходимости поменять их местами. После завершения каждого цикла самый большой элемент занимает последнее место (например, сортировка от меньшего к большему). Следующий цикл будет выполнять аналогичные операции с другими числами.
* Производительность: количество сравнений O(n^2),n^2/2 количество обменов O(n^2),n^2/4;
*
* данные @param
* Массив для сортировки
* @param Тип сортировки
* Тип сортировки
* @возвращаться
*/
public void bubbleSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // Положительная сортировка, от меньшего к большему
// Количество раундов сравнения
for (int i = 1; i < data.length; i++) {
// Сравниваем два соседних числа, и большее число всплывает вверх.
for (int j = 0; j < data.length - i; j++) {
если (данные[j] > данные[j + 1]) {
// Меняем местами два соседних числа
своп (данные, j, j + 1);
}
}
}
} else if (sortType.equals("desc")) { // Сортируем в обратном порядке, от большего к меньшему
// Количество раундов сравнения
for (int i = 1; i < data.length; i++) {
// Сравниваем два соседних числа, и большее число всплывает вверх.
for (int j = 0; j < data.length - i; j++) {
если (данные[j] <данные[j + 1]) {
// Меняем местами два соседних числа
своп (данные, j, j + 1);
}
}
}
} еще {
System.out.println("Введен неправильный тип сортировки!");
}
printArray(data);//Выводим значение массива после пузырьковой сортировки
}
/**
* Метод сортировки прямым выбором ---- тип сортировки выбором.
* Метод: на каждом проходе из элементов данных, подлежащих сортировке, выбирается наименьший (или наибольший) элемент, и порядок помещается в конец отсортированного массива до тех пор, пока все элементы данных, подлежащие сортировке, не будут упорядочены.
* Производительность: количество сравнений O(n^2),n^2/2.
* Количество обменов O(n),n
* Количество обменов намного меньше, чем при пузырьковой сортировке. Поскольку обмен требует больше процессорного времени, чем сравнение, сортировка выбором выполняется быстрее, чем пузырьковая сортировка.
* Но когда N относительно велико, время процессора, необходимое для сравнения, доминирует, поэтому производительность в это время мало чем отличается от производительности пузырьковой сортировки, но, несомненно, быстрее.
*
* данные @param
* Массив для сортировки
* @param Тип сортировки
* Тип сортировки
* @возвращаться
*
*/
public void selectSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // Положительная сортировка, от меньшего к большему
внутренний индекс;
for (int i = 1; i < data.length; i++) {
индекс = 0;
for (int j = 1; j <= data.length - i; j++) {
если (данные[j] > данные[индекс]) {
индекс = j;
}
}
//Обменяем два числа в позиции data.length-i и индексе (максимальное значение)
swap(данные, data.length - я, индекс);
}
} else if (sortType.equals("desc")) { // Сортируем в обратном порядке, от большего к меньшему
внутренний индекс;
for (int i = 1; i < data.length; i++) {
индекс = 0;
for (int j = 1; j <= data.length - i; j++) {
если (данные[j] <данные[индекс]) {
индекс = j;
}
}
//Обменяем два числа в позиции data.length-i и индексе (максимальное значение)
swap(данные, data.length - я, индекс);
}
} еще {
System.out.println("Введен неверный тип сортировки!");
}
printArray(data);//Выводим значение массива после сортировки прямым выбором
}
/**
*
* Сортировка вставкой
*
* Метод: Вставить запись в отсортированный упорядоченный список (возможно, пустой список), тем самым получив новый упорядоченный список с количеством записей, увеличенным на 1.
* Производительность: количество сравнений O(n^2),n^2/4
* Количество копий O(n),n^2/4
* Число сравнений среднее между первыми двумя, а копирование требует меньше процессорного времени, чем замена, поэтому производительность более чем вдвое выше, чем при пузырьковой сортировке, и быстрее, чем при сортировке выбором.
*
* данные @param
* Массив для сортировки
* @param Тип сортировки
* Тип сортировки
*/
public void InsertSort (int [] данные, String sortType) {
if (sortType.equals("asc")) { // Положительная сортировка, от меньшего к большему
// Количество раундов сравнения
for (int i = 1; i < data.length; i++) {
// Убедитесь, что первые числа i+1 отсортированы
for (int j = 0; j < i; j++) {
если (данные[j] > данные[i]) {
// Меняем местами два числа в позициях j и i
своп (данные, я, j);
}
}
}
} else if (sortType.equals("desc")) { // Сортируем в обратном порядке, от большего к меньшему
// Количество раундов сравнения
for (int i = 1; i < data.length; i++) {
// Убедитесь, что первые числа i+1 отсортированы
for (int j = 0; j < i; j++) {
если (данные[j] <данные[i]) {
// Меняем местами два числа в позициях j и i
своп (данные, я, j);
}
}
}
} еще {
System.out.println("Введен неправильный тип сортировки!");
}
printArray(data);//Выводим значение массива после сортировки вставками
}
/**
*
* Метод обращения массива
*
* данные @param
* исходный массив
*/
public voidverse(int[] data) {
длина int = data.length;
int temp = 0;//временная переменная
for (int i = 0; i < length/2; i++) {
температура = данные [я];
данные[i] = данные[длина - 1 - я];
данные [длина - 1 - я] = темп;
}
printArray(data);//Выводим значение в преобразованный массив
}
/**
*
* Быстрая сортировка
*
* Быстрая сортировка использует стратегию «разделяй и властвуй», чтобы разделить последовательность (список) на две подпоследовательности (подсписки).
*
*Шаги:
* 1. Выберите элемент из последовательности, называемый «поворот»,
* 2. Измените порядок последовательности так, чтобы все элементы, меньшие базового значения, располагались перед базовым, а все элементы, превышающие базовое значение, располагались за базовым (одно и то же число можно разместить с обеих сторон). После этого разделения база данных находится в своем конечном положении. Это называется операцией разделения.
* 3. Рекурсивно отсортировать подмассив элементов, меньших базового значения, и подмассив элементов, превышающих базовое значение.
*
* Нижний случай рекурсии — это когда размер массива равен нулю или единице, то есть он всегда отсортирован. Несмотря на то, что он продолжает рекурсивно работать, этот алгоритм всегда завершится, поскольку на каждой итерации (итерации) он будет перемещать хотя бы один элемент в его конечное положение.
*
* данные @param
* Массив для сортировки
* @param низкий
* @param высокий
* @see SortTest#qsort(int[], int, int)
* @see SortTest#qsort_desc(int[], int, int)
*
*/
public void QuickSort (int [] данные, String sortType) {
if (sortType.equals("asc")) { // Положительная сортировка, от меньшего к большему
qsort_asc(данные, 0, data.length - 1);
} else if (sortType.equals("desc")) { // Сортируем в обратном порядке, от большего к меньшему
qsort_desc(данные, 0, data.length - 1);
} еще {
System.out.println("Введен неверный тип сортировки!");
}
}
/**
*
* Конкретная реализация быстрой сортировки, сортировка в правильном порядке
*
* данные @param
* @param низкий
* @param высокий
*/
Private void qsort_asc(int data[], int low, int high) {
интервал я, j, х;
if (low < high) { // Это условие используется для завершения рекурсии
я = низкий;
j = высокий;
х = данные [я];
в то время как (я < j) {
while (i < j && data[j] > x) {
j-- // Находим первое число меньше x справа налево
}
если (я < j) {
данные [я] = данные [j];
я++;
}
while (i < j && data[i] < x) {
i++; // Находим первое число, большее x, слева направо
}
если (я < j) {
данные[j] = данные[i];
дж--;
}
}
данные [я] = х;
qsort_asc (данные, низкий, я - 1);
qsort_asc (данные, я + 1, высокий);
}
}
/**
*
* Специальная реализация быстрой сортировки, сортировка в обратном порядке.
*
* данные @param
* @param низкий
* @param высокий
*
*/
Private void qsort_desc(int data[], int low, int high) {
интервал я, j, х;
if (low < high) { // Это условие используется для завершения рекурсии
я = низкий;
j = высокий;
х = данные [я];
в то время как (я < j) {
while (i < j && data[j] < x) {
j-- // Находим первое число меньше x справа налево
}
если (я < j) {
данные [я] = данные [j];
я++;
}
while (i < j && data[i] > x) {
i++; // Находим первое число, большее x, слева направо
}
если (я < j) {
данные[j] = данные[i];
дж--;
}
}
данные [я] = х;
qsort_desc (данные, низкий, я - 1);
qsort_desc (данные, я + 1, высокий);
}
}
/**
*
* Бинарный поиск позиции определенного целого числа в целочисленном массиве (рекурсивный)
*
* Линейный список поиска должен быть упорядоченным списком.
*
* @paramdataset
* @paramdata
* @parambeginIndex
* @paramendIndex
* @returnindex
*
*/
public intbinarySearch(набор данных int[], int data, int BeginIndex,int endIndex) {
int MidIndex = (beginIndex + endIndex) >>> 1 // Эквивалентно середине = (низкий + высокий)
///2, но эффективность будет выше
if (данные <набор данных[beginIndex] || данные > набор данных[endIndex] || BeginIndex > endIndex)
вернуть -1;
если (данные <набор данных[midIndex]) {
вернуть бинарныйSearch (набор данных, данные, BeginIndex, MidIndex - 1);
} Еще если (данные > набор данных[midIndex]) {
вернуть двоичныйПоиск (набор данных, данные, MidIndex + 1, endIndex);
} еще {
вернуть средний индекс;
}
}
/**
*
* Бинарный поиск позиции определенного целого числа в целочисленном массиве (нерекурсивный)
*
* Линейный список поиска должен быть упорядоченным списком.
*
* @paramdataset
* @paramdata
* @returnindex
*
*/
public intbinarySearch(набор данных int[], int data) {
интервал началаИндекс = 0;
int endIndex = dataset.length - 1;
интервал мидИндекс = -1;
if (данные <набор данных[beginIndex] || данные > набор данных[endIndex] || BeginIndex > endIndex)
вернуть -1;
в то время как (beginIndex <= endIndex) {
MidIndex = (beginIndex + endIndex) >>> 1 // Эквивалентно MidIndex =;
// (индекс начала +
//endIndex)/2, но эффективность будет выше
если (данные <набор данных[midIndex]) {
конечныйИндекс = среднийИндекс - 1;
} Еще если (данные > набор данных[midIndex]) {
началоИндекс = среднийИндекс + 1;
} еще {
вернуть средний индекс;
}
}
вернуть -1;
}
public static void main(String[] args) {
Сортировка sortTest = новая сортировка();
int[] array = sortTest.createArray();
System.out.println("==========После пузырьковой сортировки (положительный порядок)==========");
sortTest.bubbleSort(массив, "по возрастанию");
System.out.println("==========После пузырьковой сортировки (обратный порядок)==========");
sortTest.bubbleSort(массив, "дескриптор");
массив = sortTest.createArray();
System.out.println("==========После обращения массива==========");
sortTest.reverse(массив);
массив = sortTest.createArray();
System.out.println("==========После сортировки выбором (положительный порядок)==========");
sortTest.selectSort(массив, "по возрастанию");
System.out.println("==========После сортировки выбора (обратный порядок)==========");
sortTest.selectSort(массив, «дескриптор»);
массив = sortTest.createArray();
System.out.println("==========После сортировки вставкой (положительная последовательность)==========");
sortTest.insertSort(массив, "по возрастанию");
System.out.println("==========После сортировки вставкой (обратный порядок)==========");
sortTest.insertSort(массив, "дескриптор");
массив = sortTest.createArray();
System.out.println("==========После быстрой сортировки (положительный порядок)==========");
sortTest.quickSort(массив, "по возрастанию");
sortTest.printArray(массив);
System.out.println("==========После быстрой сортировки (обратный порядок)==========");
sortTest.quickSort(массив, "дескриптор");
sortTest.printArray(массив);
System.out.println("==========Двоичный поиск в массиве==========");
System.out.println("Число, которое вы ищете, находится по адресу" + sortTest.binarySearch(array, 74)
+ "мест. (индекс рассчитывается от 0)");
}
}