Сортировка интерполяции - Interpolation sort

Не путать с Поиск интерполяции.

Сортировка интерполяции своего рода ведро. Для присвоения данных сегменту используется формула интерполяции. Общая формула интерполяции:

Интерполяция = ЦЕЛОЕ (((Массив [i] - мин.) / (Макс. - мин.)) * (Размер массива -1))

Алгоритм

Сортировка интерполяцией

Учебный класс	Алгоритм сортировки
Структура данных	Множество
Худший случай спектакль	${\displaystyle O(n^{2})}$
Лучший случай спектакль	${\displaystyle O(n)}$
Средний спектакль	${\displaystyle O(n+k)}$
Худший случай космическая сложность	${\displaystyle O(n*3)}$

Сортировка интерполяции (или сортировка гистограммы).^[1]Это алгоритм сортировки, который использует интерполяция формула для разброса данных разделяй и властвуй. Интерполяционная сортировка также является вариантом ведро сортировка алгоритм.^[2] Метод интерполяционной сортировки использует массив длин сегментов записи, соответствующих исходному числовому столбцу. Используя массив поддерживаемой длины, рекурсивный алгоритм можно предотвратить от изменения сложности пространства на ${\displaystyle O(n^{2})}$ из-за стекирования памяти. Запись сегментации массива длины может с помощью вторичной функции динамически объявлять и удалять пространство памяти множество. Сложность пространства, необходимая для управления рекурсивной программой, равна ${\displaystyle O(3n)}$. Содержит двумерный массив динамически выделяемой памяти и массив длин записей. Однако сложность выполнения все еще может поддерживаться как эффективный метод сортировки ${\displaystyle O(n+k)}$.^[3]Множество динамически выделяемой памяти может быть реализовано с помощью связанный список, куча, очередь, ассоциативный массив, древовидная структура и т. д. Объект массива, например JavaScript применимо. Разница в структура данных связано со скоростью доступа к данным и, следовательно, со временем, необходимым для сортировка.Когда значения в упорядоченном массиве равномерно распределены примерно арифметическая прогрессия, линейное время упорядочивания интерполяционной сортировки равно ${\displaystyle O(n)}$.^[4]

Алгоритм интерполяционной сортировки

1. Задайте массив длины сегмента для записи длины несортированного сегмента. Инициализируйте исходную длину массива.
2. [Основная сортировка] Если массив длины сегмента очищен и сортировка завершена. Выполните [функцию разделения], если она не очищена.
3. [Функция разделения] Выполнить «Разделить путем извлечения длины сегмента из конца массива длины сегмента. Найдите максимальное и минимальное значения в ведре. Если максимальное значение равно минимальному значению, сортировка завершается до остановки Divide.
4. Настройте двумерный массив как все пустые корзины. Разделите на ковш в соответствии с числом интерполяции.
5. После разделения на ведра, вдавите длину ведра в массив длины ковша. И поместите элементы обратно в исходный массив один за другим из всех непустых корзин.
6. Вернитесь в [Основная сортировка].

Алгоритм сортировки гистограммы

Определение NIST: эффективное трехпроходное уточнение алгоритма сортировки по сегментам.^[5]

1. Первый проход подсчитывает количество элементов для каждой корзины во вспомогательном массиве, а затем составляет промежуточную сумму, так что каждая вспомогательная запись представляет собой количество предыдущих элементов.
2. Второй проход помещает каждый элемент в его собственное ведро в соответствии с дополнительной записью для ключа этого элемента.
3. Последний проход сортирует каждую корзину.

Упражняться

Реализация интерполяционной сортировки

Код JavaScript:

Множество.прототип.interpolationSort = функция(){  вар разделить размер = новый Множество();  вар конец = это.длина;  разделить размер[0] = конец;  пока (разделить размер.длина > 0){разделять(это);}   // Повторяем деление функции на ArrayList  функция разделять(А){    вар размер = разделить размер.поп();    вар Начните = конец - размер;    вар мин = А[Начните];    вар Максимум = А[Начните];    за (вар я = Начните + 1; я < конец; я++){      если (А[я] < мин){мин = А[я];}      еще{ если (А[я] > Максимум){Максимум = А[я];} }    }    если (мин == Максимум){конец = конец - размер;}    еще{      вар п = 0;      вар ведро = новый Множество(размер);      за (вар я = 0; я < размер; я++){ведро[я] = новый Множество();}      за (вар я = Начните; я < конец; я++){        п = Математика.этаж(((А[я] - мин ) / (Максимум - мин ) ) * (размер - 1 ));        ведро[п].толкать(А[я]);      }      за (вар я = 0; я < размер; я++){        если (ведро[я].длина > 0){          за (вар j = 0; j < ведро[я].длина; j++){А[Начните++] = ведро[я][j];}          разделить размер.толкать(ведро[я].длина);        }      }    }  }};

Рекурсивный метод интерполяционной сортировки

Сложность пространства в наихудшем случае: ${\displaystyle O(n^{2})}$

Множество.прототип.interpolationSort= функция(){// - Дата редактирования: 31.08.2019 - //  вар Начните = 0;  вар размер = это.длина;  вар мин = это[0];  вар Максимум = это[0];   за (вар я = 1; я < размер; я++) {    если (это[я] < мин) {мин = это[я];}    еще{ если (это[я] > Максимум) {Максимум = это[я];} }  }  если (мин != Максимум){    вар ведро = новый Множество(размер);    за (вар я = 0; я < размер; я++){ведро[я] = новый Множество();}    вар интерполяция = 0;    за (вар я = 0; я < размер; я++){      интерполяция = Математика.этаж(((это[я] - мин) / (Максимум - мин)) * (размер - 1));      ведро[интерполяция].толкать(это[я]);    }    за (вар я = 0; я < размер; я++){      если (ведро[я].длина > 1){ведро[я].interpolationSort();} // Рекурсия      за (вар j = 0; j < ведро[я].длина; j++){это[Начните++] = ведро[я][j];}    }  }};

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

Множество.прототип.histogramSort = функция(){// - Дата редактирования: 14.11.2019 - //  вар конец = это.длина;  вар sortedArray = новый Множество(конец);  вар интерполяция = новый Множество(конец);  вар hitCount = новый Множество(конец);  вар разделить размер = новый Множество();  разделить размер[0] = конец;  пока (разделить размер.длина > 0){раздавать(это);}   // Повторяем функцию распределения в массив  функция раздавать(А) {    вар размер = разделить размер.поп();    вар Начните = конец - размер;    вар мин = А[Начните];    вар Максимум = А[Начните];    за (вар я = Начните + 1; я < конец; я++) {      если (А[я] < мин) { мин = А[я]; }      еще {если (А[я] > Максимум) { Максимум = А[я]; } }    }    если (мин == Максимум) { конец = конец - размер; }    еще {      за (вар я = Начните; я < конец; я++) { hitCount[я] = 0; }      за (вар я = Начните; я < конец; я++) {        интерполяция[я] = Начните + Математика.этаж(((А[я] - мин ) / (Максимум - мин ) ) * (размер - 1 ));        hitCount[интерполяция[я]]++;      }      за (вар я = Начните; я < конец; я++) {        если (hitCount[я] > 0) { разделить размер.толкать(hitCount[я]); }      }      hitCount[конец-1] = конец - hitCount[конец-1];      за (вар я = конец-1; я > Начните; я--) {        hitCount[я-1] = hitCount[я] - hitCount[я-1];      }      за (вар я = Начните; я < конец; я++) {        sortedArray[hitCount[интерполяция[я]]] = А[я];        hitCount[интерполяция[я]]++;      }      за (вар я = Начните; я < конец; я++) { А[я] = sortedArray[я]; }    }  }};

Вариант

Сортировка тегов интерполяции

Сортировка тегов Interpolaion

Учебный класс	Алгоритм сортировки
Структура данных	Множество
Худший случай спектакль	${\displaystyle O(n^{2})}$
Лучший случай спектакль	${\displaystyle O(n)}$
Средний спектакль	${\displaystyle O(n+k)}$
Худший случай космическая сложность	${\displaystyle O(2n+(n)bits)}$

Сортировка по тегам интерполяции - это вариант сортировки с интерполяцией. Применяя метод сортировки и разделения сегментов, данные массива распределяются на ограниченное количество сегментов по математической формуле интерполяции, а затем сегмент рекурсивно исходная программа обработки до завершения сортировки.

Сортировка по тегам интерполяции - это метод рекурсивной сортировки для сортировки с интерполяцией. Чтобы избежать переполнения стека из-за рекурсии, происходит сбой памяти. Вместо этого используйте массив тегов логического типа для работы рекурсивной функции по освобождению памяти. Требуемый дополнительный объем памяти близок к ${\displaystyle 2n+(n)bits}$. Содержит двумерный массив динамически выделяемой памяти и массив тегов логического типа. Стек, очередь, ассоциативный массив и древовидная структура могут быть реализованы как корзины.

Поскольку объект массива JavaScript подходит для этого метода сортировки, разница в структуре данных связана со скоростью доступа к данным и, следовательно, со временем, необходимым для сортировки. Линейное время Θ (n) используется, когда значения в массиве для сортировки равномерно распределены. Алгоритм сортировки по ведру не ограничивает сортировку нижним пределом ${\displaystyle O(nlogn)}$. Средняя сложность сортировки тегов интерполяции составляет ${\displaystyle O(n+k)}$.^[6]

Алгоритм сортировки тегов интерполяции

1. Установите массив тегов равным исходному размеру массива и инициализируйте ложным значением.
2. [Основная сортировка] Определяет, все ли сегменты исходного массива отсортированы. Если сортировка не завершена, выполняется [Функция разделения].
3. [Функция разделения] Найдите максимальное и минимальное значения в корзине. Если максимальное значение равно минимальному значению, сортировка завершается и деление прекращается.
4. Настройте двумерный массив как все пустые корзины. Разделите на ковш в соответствии с числом интерполяции.
5. После разделения на сегмент отметьте начальное положение сегмента как истинное значение в массиве тегов. И поместите элементы обратно в исходный массив один за другим из всех непустых корзин.
6. Вернитесь в [Основная сортировка].

Упражняться

Код JavaScript:

Множество.прототип.InterpolaionTagSort = функция(){// Кит Чен соглашается с «Лицензией Wikipedia CC BY-SA 3.0». Дата подписи: 21.06.2019 //  вар конец = это.длина;   если (конец > 1) {     вар Начните = 0 ;     вар Тег = новый Множество(конец);          // Шаг алгоритма-1     за (вар я = 0; я < конец; я++) { Тег[ я ] = ложный; }     Разделять(это);   }   пока (конец > 1) {                     // Шаг алгоритма-2     пока (Тег[--Начните] == ложный) { } // Находим начало следующего сегмента    Разделять(это);   }   функция Разделять(А) {       вар мин = А[Начните];     вар Максимум = А[Начните];    за (вар я = Начните + 1; я < конец; я++) {       если (А[я] < мин) { мин = А[я]; }       еще { если (А[я] > Максимум) { Максимум = А[я]; } } }    если ( мин == Максимум) { конец = Начните; }    // Шаг алгоритма 3 Start to be the next bucket end    еще {                                                вар интерполяция = 0;       вар размер = конец - Начните;       вар Ведро = новый Множество( размер );    // Шаг алгоритма-4       за (вар я = 0; я < размер; я++) { Ведро[я] = новый Множество(); }        за (вар я = Начните; я < конец; я++) {           интерполяция = Математика.этаж (((А[я] - мин) / (Максимум - мин)) * (размер - 1));         Ведро[интерполяция].толкать(А[я]);       }       за (вар я = 0; я < размер; я++) {        если (Ведро[я].длина > 0) {    // Шаг алгоритма-5           Тег[Начните] = истинный;           за (вар j = 0; j < Ведро[я].длина; j++) { А[Начните++] = Ведро[я][j]; }         }       }      }  }// Шаг алгоритма-6 };

Сортировка тегов Interpolaion на месте

Сортировка тегов Interpolaion на месте

Учебный класс	Алгоритм сортировки
Структура данных	Множество
Худший случай спектакль	${\displaystyle O(n)}$
Лучший случай спектакль	${\displaystyle O(n)}$
Средний спектакль	${\displaystyle O(n)}$
Худший случай космическая сложность	${\displaystyle O(n)bits}$

Сортировка тегов интерполяции на месте - это алгоритм на месте интерполяционной сортировки. Сортировка тегов интерполяции на месте может обеспечить сортировку только за N раз подкачки, поддерживая N битовых тегов; однако сортируемый массив должен быть непрерывной целочисленной последовательностью, а не повторяться, или серия должна быть полностью равномерно распределена, чтобы приблизить количество арифметическая прогрессия.

Данные факторного столбца не должны повторяться. Например, сортировка 0 ~ 100 может быть отсортирована за один шаг. Количество обменов: ${\displaystyle O(n)}$, временная сложность расчета составляет: ${\displaystyle O(n)}$, а наихудшая космическая сложность - ${\displaystyle O(n)bits}$. Если характеристики серии соответствуют условным требованиям данного метода сортировки: « множество представляет собой непрерывное целое число или не повторяющуюся арифметическую прогрессию », то сортировка тегов интерполяции на месте будет отличным методом сортировки, который работает очень быстро и экономит место в памяти.

Алгоритм сортировки тегов интерполяции на месте

Сортировка тегов интерполяции на месте сортирует неповторяющиеся последовательные целочисленные серии, только один массив тегов логического типа данных с той же длиной, что и исходный массив, массив вычисляет интерполяцию данных с самого начала, а интерполяция указывает на новую позицию массива. Position, позиция, которая была заменена, помечается как истинная в соответствующей позиции массива тегов и увеличивается до тех пор, пока не будет отсортирован конец массива.

Алгоритм процесса:

1. Установите равное количество массивов тегов для инициализации ложными значениями.
2. Посетите массив, когда tag [i] имеет значение false, вычислите позицию, соответствующую интерполяции = p.
3. Поменяйте местами a [i] и [p], пусть tag [p] = true.
4. Массив тура завершен, и сортировка завершена.

Упражняться

Код JavaScript:

Множество.прототип.InPlaceTagSort = функция(){ // Дата редактирования: 2019/07/02  вар п = это.длина;  вар Тег = новый Множество( п );  за ( я = 0; я < п; я++ ){ Тег[ я ] = ложный; }  вар мин = это[ 0 ];  вар Максимум = это[ 0 ];  за ( я = 1; я < п; я++ ){ если ( это[ я ] < мин ){ мин = это[ я ]; }  еще{ если (это[ я ] > Максимум){ Максимум = это[ я ]; } } }   вар п = 0;  вар темп = 0;  за ( я = 0; я < п; я++ ){    пока ( Тег[ я ] == ложный ){       п = Математика.этаж((( это[ я ] - мин ) / ( Максимум - мин )) * ( п - 1 ));      темп = это[ я ];      это[ я ] = это[ п ];       это[ п ] = темп;      Тег[ п ] = истинный;     }   } };needSortArray.InPlaceTagSort();

Происхождение сортировки по месту, выполняемой в ${\displaystyle O(n)}$ время

В «Математическом анализе алгоритмов» (Information Processing '71, North Holland Publ. '72) Дональд Кнут заметил, что «... исследование вычислительной сложности - интересный способ отточить наши инструменты для решения более рутинных задач, с которыми мы сталкиваемся изо дня в день. день." ^[7]

Знаменитый американский ученый-компьютерщик Дональд Кнут в математическом анализе алгоритмов указал, что: «Что касается проблемы сортировки, Кнут указывает, что эффективная по времени перестановка на месте по своей сути связана с проблемой поиска лидеров цикла, и перестановки на месте могут быть легко выполнены в ${\displaystyle O(n)}$ time, если бы нам разрешили манипулировать n дополнительными битами «тега», определяющими, какая часть перестановки была выполнена в любой момент. Без таких битов тегов, заключает он, «кажется разумным предположить, что каждый алгоритм потребует перестановки на месте по крайней мере ${\displaystyle O(nlogn)}$ шагов в среднем ". ^[7]

Сортировка тегов интерполяции на месте - это один из алгоритмов сортировки, который Дональд Кнут профессор сказал: «манипулируйте n дополнительными« тегами »... поиск лидеров цикла, и перестановки на месте могут быть легко выполнены в ${\displaystyle O(n)}$ время".

Подобный метод сортировки

1. Flashsort
2. Proxmap сортировка
3. Американский флаг сортировка

Сортировка ведра, смешивающая другие методы сортировки и рекурсивный алгоритм

Сортировку по ведру можно комбинировать с другими методами сортировки для завершения сортировки. Если он сортируется с помощью сортировки по корзине и сортировки вставкой, это также довольно эффективный метод сортировки. Но когда в ряду появляется большое отклонение от значения: например, когда максимальное значение ряда больше, чем в N раз следующее наибольшее значение. После обработки серии столбцов все элементы, кроме максимального значения, попадают в одну корзину. Второй метод сортировки использует сортировку вставкой. Может привести к снижению сложности выполнения ${\displaystyle O(n^{2})}$. Это потеряло смысл и высокую скорость использования сортировки по ведру.

Сортировка с интерполяцией - это способ рекурсивного использования сортировки по корзине. После выполнения рекурсии по-прежнему используйте сортировку по корзине для распределения ряда. Это поможет избежать описанной выше ситуации. Если вы хотите, чтобы сложность выполнения сортировки рекурсивной интерполяцией упала в ${\displaystyle O(n^{2})}$, необходимо представить факториал усиление во всей серии. На самом деле, вероятность того, что произойдет серия специальных распределений, очень мала.

Рекомендации

1. Алгоритм NIST. "интерполяционная сортировка". Определение: см. Сортировку гистограммы.
2. en.wikipedia. «Сортировка гистограммы». Другой вариант сортировки по сегментам, известный как сортировка по гистограмме или сортировка с подсчетом, добавляет начальный проход, который подсчитывает количество элементов, которые попадут в каждую корзину, используя массив счетчиков. Используя эту информацию, значения массива могут быть организованы в последовательность сегментов на месте посредством последовательности обменов, не оставляя места для хранения сегментов.
3. ж.википедия. «桶 排序 （Сортировка по ведру）» (на китайском языке). 平均 時間 複雜 度 （Средняя производительность）${\displaystyle O(n+k)}$
4. Википедия. "Сортировка по корзине" Средний случай ". en.wikipedia. Обратите внимание, что если k выбирается равным ${\displaystyle k=n}$ , затем выполняется сортировка по сегментам ${\displaystyle O(n)}$ среднее время при равномерно распределенном входе.
5. Алгоритм NIST. "histogramSort sort". Определение: эффективное трехпроходное уточнение алгоритма сортировки по ведру.
6. ж.википедия. «桶 排序 （Сортировка по ведру）» (на китайском языке). 平均 時間 複雜 度 （Средняя производительность）${\displaystyle O(n+k)}$
7. Карл-Дитрих Нойберт (1998). «Алгоритм FlashSort». Получено 2007-11-06.

внешняя ссылка

• interpolationSort.html
• histogramSort.html
• Алгоритм FlashSort
• Математический анализ алгоритмов
• http://www.drdobbs.com/database/the-flashsort1-algorithm/184410496
• 排序 遞 迴 方式 演算法 Рекурсивный метод сегментной сортировки. Кит Чен 2012/09/16
• 標簽 排序 演算法 Алгоритм сортировки тегов интерполяции. Кит Чен 2013/03/24
• интерполяционная сортировка (доступна версия на Паскале)
• Платформа для тестирования сортировки массивов JavaScript w3schools