стабильность (стабильность)
Алгоритм сортировки стабилен, то есть, когда есть две равные записи ключей R и S, и R появляется перед S в исходном списке, R также появится перед S в отсортированном списке.
Классификация алгоритмов сортировки
Общие из них включают вставку (сортировка вставкой/сортировка по холму), обмен (сортировка пузырьком/быстрая сортировка), выбор (сортировка выбором), слияние (сортировка слиянием) и т. д.
1. Сортировка вставками
Сортировка вставками (сортировка вставками) работает путем создания упорядоченной последовательности. Для несортированных данных она сканирует отсортированную последовательность сзади вперед, чтобы найти соответствующую позицию и вставить ее. При реализации сортировки вставками обычно используется сортировка на месте (то есть сортировка, использующая только O(1) дополнительного пространства). Поэтому в процессе сканирования сзади вперед необходимо неоднократно и постепенно сдвигать пространство. отсортированы элементы назад, предоставляя место для вставки последнего элемента.
Вообще говоря, сортировка вставкой реализуется в массивах с использованием метода in-place. Конкретный алгоритм описывается следующим образом:
Начиная с первого элемента, элементы можно считать отсортированными.
Получите следующий элемент и просканируйте его сзади вперед в отсортированной последовательности элементов.
Если элемент (отсортированный) больше нового элемента, переместите элемент на следующую позицию.
Повторяйте шаг 3, пока не найдете позицию, в которой отсортированный элемент меньше или равен новому элементу.
После вставки нового элемента в эту позицию.
Повторите шаги 2–5.
Скопируйте код кода следующим образом:
public static void InsertionSort(int[] data) {
for (int index = 1; index < data.length; index++) {
ключ int = данные [индекс];
int позиция = индекс;
// сдвигаем большие значения вправо
while (позиция > 0 && данные[позиция - 1] > ключ) {
данные[позиция] = данные[позиция - 1];
позиция--;
}
данные [позиция] = ключ;
}
}
2. Сортировка холмов
Сортировка Шеллом — это тип сортировки вставками. Это улучшение алгоритма сортировки прямой вставкой. Этот метод еще называют уменьшающей инкрементальной сортировкой, потому что DL. Shell получила свое название в честь предложения, предложенного в 1959 году.
Сортировка Хилла предлагает улучшенный метод, основанный на следующих двух свойствах сортировки вставками:
Сортировка вставками очень эффективна при работе с почти отсортированными данными, то есть может достичь эффективности линейной сортировки.
Но сортировка вставкой обычно неэффективна, поскольку сортировка вставкой может перемещать данные только по одному биту за раз.
Скопируйте код кода следующим образом:
static <E расширяет Comparable<? super E>> voidshellSort(List<E> a) {
интервал ч = 1;
while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) по Кнуту,1973>: 1, 4, 13, 40, 121, . ..
для (; час >= 1; час /= 3)
for (int i = h; i < a.size(); i++)
for (int j = i; j >= h && a.get(j).compareTo(a.get(jh)) < 0; j-=h)
Collections.swap(a, j, jh);
}
3. Пузырьковая сортировка
Пузырьковая сортировка (Bubble Sort, с тайваньского переводится как: Bubble Sort или Bubble Sort) — простой алгоритм сортировки. Он неоднократно проходит через последовательность, подлежащую сортировке, сравнивая два элемента за раз и меняя их местами, если они находятся в неправильном порядке. Работа по посещению массива повторяется до тех пор, пока обмены больше не понадобятся, а это значит, что массив отсортирован. Название этого алгоритма связано с тем, что меньшие элементы будут медленно «всплывать» на вершину массива посредством замены.
Алгоритм пузырьковой сортировки работает следующим образом:
Сравните соседние элементы и, если первый больше второго, поменяйте их местами.
Сделайте то же самое для каждой пары соседних элементов, начиная с первой пары и заканчивая последней парой, после чего последний элемент должен иметь наибольшее число.
Повторите вышеуказанные шаги для всех элементов, кроме последнего.
Продолжайте повторять описанные выше шаги для все меньшего и меньшего количества элементов каждый раз, пока не останется пар чисел для сравнения.
Скопируйте код кода следующим образом:
public static void bubbleSort(int[] data) {
интервал температуры = 0;
for (int i = data.length - 1; i > 0; --i) {
логическое значение isSort = ложь;
for (int j = 0; j < i; ++j) {
если (данные[j + 1] <данные[j]) {
температура = данные [j];
данные[j] = данные[j + 1];
данные [j + 1] = температура;
isSort = правда;
}
}
// Если обмен происходит во внутреннем цикле, продолжаем сравнение. Если во внутреннем цикле обмен не происходит, считается, что он отсортирован;
если (!isSort)
перерыв;
}
}
4. Быстрая сортировка
Быстрая сортировка — это усовершенствованная версия пузырьковой сортировки. Предложен CAR Hoare в 1962 году. Его основная идея состоит в том, чтобы разделить данные, подлежащие сортировке, на две независимые части посредством одной сортировки. Все данные в одной части меньше, чем все данные в другой части, а затем использовать этот метод для быстрого разделения двух частей данных. Сортировка: весь процесс сортировки может выполняться рекурсивно, так что все данные становятся упорядоченной последовательностью.
Быстрая сортировка использует стратегию «разделяй и властвуй», чтобы разделить список на два подсписка.
Шаги:
Выбор элемента из последовательности называется «поворотом».
Измените порядок массива так, чтобы все элементы, меньшие базового значения, располагались перед базовым значением, а все элементы, превышающие базовое значение, располагались позади базового значения (одно и то же число может идти в любую сторону). После выхода из этого раздела база оказывается в середине последовательности. Это называется операцией разделения.
Рекурсивно отсортируйте подмассив элементов меньше базового значения и подмассив элементов больше базового значения.
Скопируйте код кода следующим образом:
/*
* более эффективные инструменты для быстрой сортировки <br />.
* используйте левое, центральное и правое медианное значение (@see #median()) для опорной точки и
* более эффективный внутренний цикл ядра алгоритма.
*/
общественный класс Быстрая сортировка {
общественный статический окончательный интервал CUTOFF = 11;
/**
* алгоритм быстрой сортировки <br />.
*
* @param представляет собой массив сопоставимых элементов <br />.
*/
public static <T расширяет Comparable<? super T>> void Quicksort(T[] arr) {
QuickSort(arr, 0, arr.length - 1);
}
/**
* получить медиану левого, центрального и правого <br />.
* упорядочите их и скройте ось, поместив ее в конец массива <br />.
*
* @param представляет собой массив сопоставимых элементов <br />.
* @param оставил самый левый индекс подмассива <br />.
* @param right — самый правый индекс подмассива.<br />
* @return Т
*/
public static <T расширяет Comparable<? super T>> T median(T[] arr, int left, int right) {
int center = (влево + вправо)/2;
если (arr[left].compareTo(arr[center]) > 0)
swapRef(arr, влево, по центру);
если (arr[left].compareTo(arr[right]) > 0)
swapRef(arr, влево, вправо);
если (arr[center].compareTo(arr[right]) > 0)
swapRef(arr, центр, вправо);
swapRef(arr, центр, вправо - 1);
вернуть arr[право - 1];
}
/**
* внутренний метод сортировки массива с помощью алгоритма быстрой сортировки <br />.
*
* @param представляет собой массив сопоставимых элементов <br />.
* @param оставил крайний левый индекс подмассива <br />.
* @param right — самый правый индекс подмассива <br />.
*/
Private static <T расширяет Comparable<? super T>> void QuickSort(T[] arr, int left, int right) {
if (слева + CUTOFF <= справа) {
// находим опорную точку
T ось = медиана (приобретение, влево, вправо);
// начинаем разбиение
int я = влево, j = вправо - 1;
для (;;) {
while (arr[++i].compareTo(pivot) <0);
while (arr[--j].compareTo(pivot) > 0);
если (я < j)
swapRef(arr, я, j);
еще
перерыв;
}
// меняем ссылку на сводную коллекцию обратно в небольшую коллекцию.
swapRef(arr, я, вправо - 1);
QuickSort(arr, left, i - 1); // сортируем небольшую коллекцию.
QuickSort(arr, i + 1, right); // сортируем большую коллекцию.
} еще {
// если общее число меньше CUTOFF, мы используем сортировку вставкой
// вместо этого (потому что это намного эффективнее).
Sort(arr, вставка слева, справа);
}
}
/**
* метод замены ссылок в массиве.<br />
*
* @param представляет собой массив объектов <br />.
* @param idx1 индекс первого элемента <br />.
* @param idx2 индекс второго элемента <br />.
*/
public static <T> void swapRef(T[] arr, int idx1, int idx2) {
Т tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
/**
* метод сортировки подмассива от начала до конца с помощью сортировки вставками
* алгоритм <br />
*
* @param представляет собой массив сопоставимых элементов <br />.
* @param начать начальную позицию <br />.
* @param end — конечная позиция <br />.
*/
public static <T расширяет Comparable<? super T>> void InsertionSort(T[] arr, int start, int end) {
интервал я;
for (int j = start + 1; j <= end; j++) {
Т tmp = arr[j];
for (i = j; i > start && tmp.compareTo(arr[i - 1]) < 0; i--) {
arr[i] = arr[i - 1];
}
arr[i] = tmp;
}
}
Private static void printArray(Integer[] c) {
for (int i = 0; i <c.length; i++)
System.out.print(c[i] + ",");
Система.out.println();
}
public static void main(String[] args) {
Целое число [] данные = {10, 4, 9, 23, 1, 45, 27, 5, 2};
System.out.println("bubbleSort...");
printArray (данные);
быстрая сортировка (данные);
printArray (данные);
}
}
5. Сортировка выбором
Сортировка выбором — это простой и интуитивно понятный алгоритм сортировки. Вот как это работает. Сначала найдите самый маленький (большой) элемент в неотсортированной последовательности и сохраните его в начале отсортированной последовательности. Затем продолжайте искать самый маленький (большой) элемент среди оставшихся неотсортированных элементов, а затем поместите его в конец. отсортированная последовательность. И так до тех пор, пока все элементы не будут отсортированы.
Поскольку каждый процесс определения элементов имеет подпроцесс выбора минимального значения, люди называют это сортировкой выбора.
Например, в последовательности 5 8 5 2 9 мы знаем, что первый элемент 5 будет заменен на 2 при первом проходе. Тогда относительный порядок двух пятерок в исходной последовательности будет нарушен, поэтому сортировка выбором будет такой. не стабильный алгоритм сортировки.
Скопируйте код кода следующим образом:
public static void selectSort(int[] data) {
интервал мининдекс = 0;
интервал температуры = 0;
for (int i = 0; i < data.length; i++) {
minIndex = i; //Минимальный индекс массива данных неупорядоченной области
for (int j = i + 1; j < data.length; j++) { // Находим наименьшие данные в неупорядоченной области и сохраняем индекс массива
если (данные[j] <данные[minIndex]) {
мининдекс = j;
}
}
if (minIndex != i) { // Если минимальная позиция неупорядоченной области не является первыми данными по умолчанию, замените ее.
температура = данные [я];
данные[i] = данные[minIndex];
данные [minIndex] = температура;
}
}
}
6. Сортировка слиянием
Сортировка слиянием — это эффективный алгоритм сортировки, основанный на операциях слияния. Этот алгоритм представляет собой очень типичное приложение, использующее метод «разделяй и властвуй» (Divide and Conquer).
Процесс операции слияния выглядит следующим образом:
Подайте заявку на пространство, чтобы его размер был суммой двух отсортированных последовательностей. Это пространство используется для хранения объединенной последовательности.
Установите два указателя, начальные позиции — это начальные позиции двух отсортированных последовательностей.
Сравните элементы, на которые указывают два указателя, выберите относительно небольшой элемент и поместите его в пространство слияния, а затем переместите указатель на следующую позицию.
Повторяйте шаг 3, пока указатель не достигнет конца последовательности.
Копирует все оставшиеся элементы другой последовательности непосредственно в конец объединенной последовательности.
Скопируйте код кода следующим образом:
public static int[] mergeSort(int[] arr) {//Сортировка слиянием — рекурсия
if (длина массива == 1) {
возврат обр;
}
int half = длина аранж./2;
int[] arr1 = новый int[половина];
int[] arr2 = новый int[arr.length - half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, half, arr2, 0, arr2.length);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
вернуть mergeSortSub(arr1, arr2);
}
Private static int[] mergeSortSub(int[] arr1, int[] arr2) {//Подпрограмма сортировки слиянием
int[] result = new int[arr1.length + arr2.length];
интервал я = 0;
интервал j = 0;
интервал к = 0;
в то время как (истина) {
если (arr1[i] < arr2[j]) {
результат[к] = arr1[i];
if (++i > arr1.length - 1) {
перерыв;
}
} еще {
результат[к] = arr2[j];
if (++j > arr2.length - 1) {
перерыв;
}
}
к++;
}
for (; i < arr1.length; i++) {
результат[++k] = arr1[i];
}
for (; j < arr2.length; j++) {
результат[++k] = arr2[j];
}
вернуть результат;
}
Полный код (кроме QuickSort)
Скопируйте код кода следующим образом:
пакет com.clzhang.sample.thinking;
импортировать java.util.*;
/**
* Java-реализация нескольких распространенных алгоритмов сортировки.
* @author acer
*
*/
общественный класс CommonSort {
/**
* Конкретный алгоритм сортировки вставками описан следующим образом:
* 1. Начиная с первого элемента, элемент можно считать отсортированным.
* 2. Выньте следующий элемент и просканируйте его сзади вперед в отсортированной последовательности элементов.
* 3. Если элемент (отсортированный) больше нового элемента, переместите элемент на следующую позицию.
* 4. Повторяйте шаг 3, пока не найдете позицию, в которой отсортированный элемент меньше или равен новому элементу.
* 5. После вставки нового элемента в эту позицию
* 6. Повторите шаги 2–5.
*/
public static void InsertionSort(int[] data) {
for (int index = 1; index < data.length; index++) {
ключ int = данные [индекс];
int позиция = индекс;
// сдвигаем большие значения вправо
while (позиция > 0 && данные[позиция - 1] > ключ) {
данные[позиция] = данные[позиция - 1];
позиция--;
}
данные [позиция] = ключ;
}
}
/**
* Сортировка по холму: идеи реализации алгоритма, подходящего для большого количества операций сортировки, можно найти в Википедии;
*/
static <E расширяет Comparable<? super E>> voidshellSort(List<E> a) {
интервал ч = 1;
while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) по Кнуту,1973>: 1, 4, 13, 40, 121, . ..
для (; час >= 1; час /= 3)
for (int i = h; i < a.size(); i++)
for (int j = i; j >= h && a.get(j).compareTo(a.get(jh)) < 0; j-=h)
Collections.swap(a, j, jh);
}
/**
* Алгоритм пузырьковой сортировки работает следующим образом:
* 1. Сравните соседние элементы. Если первый больше второго, поменяйте их оба местами.
* 2. Проделайте ту же работу для каждой пары соседних элементов, от первой пары в начале до последней пары в конце. На этом этапе последний элемент должен быть наибольшим числом.
* 3. Повторите описанные выше действия для всех элементов, кроме последнего.
* 4. Продолжайте повторять описанные выше шаги для все меньшего и меньшего количества элементов каждый раз, пока не останется пар чисел для сравнения. [1]
*/
public static void bubbleSort(int[] data) {
интервал температуры = 0;
for (int i = data.length - 1; i > 0; --i) {
логическое значение isSort = ложь;
for (int j = 0; j < i; ++j) {
если (данные[j + 1] <данные[j]) {
температура = данные [j];
данные[j] = данные[j + 1];
данные [j + 1] = температура;
isSort = правда;
}
}
// Если обмен происходит во внутреннем цикле, продолжаем сравнение. Если во внутреннем цикле обмен не происходит, считается, что он отсортирован;
если (!isSort)
перерыв;
}
}
/**
* Основная идея сортировки выбором заключается в следующем:
* 1. Если в процессе обхода массива i представляет текущий порядковый номер, который необходимо отсортировать, необходимо найти минимальное значение среди оставшихся [i+1...n-1].
* 2.Затем замените найденное минимальное значение на значение, указанное i.
* Поскольку каждый процесс определения элементов имеет подпроцесс выбора минимального значения, люди называют это сортировкой выбора.
* данные @param
*/
public static void selectSort(int[] data) {
интервал мининдекс = 0;
интервал температуры = 0;
for (int я = 0; я <data.length; я++) {
minIndex = i; //Минимальный индекс массива данных неупорядоченной области
for (int j = i + 1; j < data.length; j++) { // Находим наименьшие данные в неупорядоченной области и сохраняем индекс массива
если (данные[j] <данные[minIndex]) {
мининдекс = j;
}
}
if (minIndex != i) { // Если минимальная позиция неупорядоченной области не является первыми данными по умолчанию, замените ее.
температура = данные [я];
данные[i] = данные[minIndex];
данные [minIndex] = температура;
}
}
}
/**
* Процесс операции слияния выглядит следующим образом:
* 1. Подайте заявку на пространство, чтобы его размер был суммой двух отсортированных последовательностей. Это пространство используется для хранения объединенной последовательности.
* 2. Установите два указателя, начальные позиции — это начальные позиции двух отсортированных последовательностей.
* 3. Сравните элементы, на которые указывают два указателя, выберите относительно небольшой элемент и поместите его в пространство слияния, а затем переместите указатель в следующую позицию.
* 4. Повторяйте шаг 3, пока указатель не достигнет конца последовательности.
* 5. Скопируйте все оставшиеся элементы другой последовательности непосредственно в конец объединенной последовательности.
*/
public static int[] mergeSort(int[] arr) {//Сортировка слиянием — рекурсия
if (длина массива == 1) {
возврат обр;
}
int half = длина аранжировки / 2;
int[] arr1 = новый int[половина];
int[] arr2 = новый int[arr.length - half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr, half, arr2, 0, arr2.length);
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
вернуть mergeSortSub(arr1, arr2);
}
Private static int[] mergeSortSub(int[] arr1, int[] arr2) {//Подпрограмма сортировки слиянием
int[] result = new int[arr1.length + arr2.length];
интервал я = 0;
интервал j = 0;
интервал к = 0;
в то время как (истина) {
если (arr1[i] < arr2[j]) {
результат[к] = arr1[i];
if (++i > arr1.length - 1) {
перерыв;
}
} еще {
результат [к] = arr2 [j];
if (++j > arr2.length - 1) {
перерыв;
}
}
к++;
}
for (; i < arr1.length; i++) {
результат[++k] = arr1[i];
}
for (; j < arr2.length; j++) {
результат[++k] = arr2[j];
}
вернуть результат;
}
Private static void printArray(int[] c) {
for (int i = 0; i <c.length; i++)
System.out.print(c[i] + ",");
Система.out.println();
}
public static void main(String []args){
данные int[] = {10,4,9,23,1,45,27,5,2};
System.out.println("bubbleSort...");
int[] a = data.clone();
PrintArray (а);
пузырьковая сортировка (а);
PrintArray (а);
System.out.println("selectSort...");
int[] b = data.clone();
PrintArray (б);
выберитеСортировка (б);
PrintArray (б);
System.out.println("insertionSort...");
int[] c = data.clone();
PrintArray (с);
вставкаСортировка (с);
PrintArray (с);
System.out.println("shellSort...");
List<Integer> list = новый ArrayList<Integer>();
for(int i=0;i<data.length;i++)
list.add(данные [я]);
System.out.println(список);
ShellSort (список);
System.out.println(список);
System.out.println("mergeSort...");
int[] d = data.clone();
PrintArray (д);
printArray(mergeSort(d));
}
}