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

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

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

Алгоритм [ править ]

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

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

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

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

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

Алгоритм сортировки гистограммы [ править ]

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

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

Практика [ править ]

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

Код JavaScript:

Массив . прототип . interpolationSort  =  функция () {  вар  divideSize  =  новый  массив ();  var  end  =  this . длина ;  DivideSize [ 0 ]  =  конец ; в  то время как  ( divideSize . Длина  >  0 ) { деление ( это );}  // Функция повтора делят на ArrayList  функции  разрыва ( A ) {  вар  размера =  divSize . pop ();  var  start  =  end  -  размер ;  var  min  =  A [ начало ];  var  max  =  A [ начало ];  for  ( var  i  =  start  +  1 ;  i  <  end ;  i ++ ) {  if  ( A [ i ]  <  min ) { min  =  A [ i ];} else {  if  ( A [ i ]  >  max ) { max  =  A [ i ];}  }  }  if  ( min  ==  max ) { end  =  end  -  size ;}  else {  var  p  =  0 ;  var  bucket  =  новый  массив ( размер );  для  ( var  я  =  0 ;  я  <  размер ; i ++ ) { bucket [ i ]  =  new  Array ();}  для  ( var  i  =  start ;  i  <  end ;  i ++ ) {  p  =  Math . этаж ((( A [ i ]  -  min  )  /  ( max  -  min  )  )  *  ( размер  -  1  ));  ведро [ п ]. толкать (A [ i ]);  }  for  ( var  i  =  0 ;  i  <  size ;  i ++ ) {  if  ( bucket [ i ]. length  >  0 ) {  for  ( var  j  =  0 ;  j  <  bucket [ i ]. length ;  j ++ ) { A [ start ++ ]  =  bucket [ i ] [j ];}  divSize . толкать ( ведро [ i ]. длина );  }  }  }  } };

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

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

Массив . прототип . interpolationSort =  function () { // - Дата редактирования: 31.08.2019 - //  var  start  =  0 ;  var  size  =  this . длина ;  var  min  =  это [ 0 ];  var  max  =  это [ 0 ];  for  ( var  i  =  1 ;  i  <  size ;  i ++ )  {  if  (this [ i ]  <  min )  { min  =  this [ i ];}  else {  if  ( this [ i ]  >  max )  { max  =  this [ i ];}  }  }  if  ( min  ! =  max ) {  var  bucket  =  new  Массив ( размер );  для  ( var  i  =  0 ;  i  < размер ;  i ++ ) { bucket [ i ]  =  new  Array ();}  var  interpolation  =  0 ;  for  ( var  i  =  0 ;  i  <  size ;  i ++ ) {  интерполяция  =  Math . этаж ((( this [ i ]  -  min )  /  ( max  -  min ))  *  ( size  -  1));  ведро [ интерполяция ]. push ( this [ i ]);  }  for  ( var  i  =  0 ;  i  <  size ;  i ++ ) {  if  ( bucket [ i ]. length  >  1 ) { bucket [ i ]. interpolationSort ();}  // Рекурсия  для  ( var  j  =  0 ;  j  <  bucket [i ]. длина ;  j ++ ) { this [ start ++ ]  =  bucket [ i ] [ j ];}  }  } };

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

Массив . прототип . histogramSort  =  function () { // - Дата редактирования: 2019/11/14 - //  var  end  =  this . длина ;  var  sortedArray  =  новый  массив ( конец );  var  interpolation  =  новый  массив ( конец );  var  hitCount  =  новый  массив ( конец );  var  DiviveSize  =  новый  массив ();  DivineSize [0 ]  =  конец ;  while  ( DivideSize . length  >  0 ) { distribute ( this );}  // Повторить функцию distribute to Array  function  distribute ( A )  {  var  size  =  diverSize . pop ();  var  start  =  end  -  размер ;  var  min  =  A [ начало ];  var  max  =  A [ начало];  для  ( var  я  =  начало  +  1 ;  я  <  конец ;  я ++ )  {  если  ( А [ я ]  <  мин )  {  мин  =  А [ я ];  }  else  { если  ( A [ i ]  >  max )  {  max  =  A [ i ];  }  }  }  if  ( min ==  max )  {  end  =  end  -  размер ;  }  else  {  для  ( var  i  =  start ;  i  <  end ;  i ++ )  {  hitCount [ i ]  =  0 ;  }  for  ( var  i  =  start ;  i  <  end ;  i ++ )  {  interpolation [ i ]  =  start +  Математика . этаж ((( A [ i ]  -  min  )  /  ( max  -  min  )  )  *  ( размер  -  1  ));  hitCount [ интерполяция [ я ]] ++ ;  }  for  ( var  i  =  start ;  i  <  end ;  i ++ )  {  if  ( hitCount [ i ]  >  0)  {  divSize . push ( hitCount [ i ]);  }  }  hitCount [ конец - 1 ]  =  конец  -  hitCount [ конец - 1 ];  for  ( var  i  =  end - 1 ;  i  >  start ;  i - )  {  hitCount [ i - 1 ]  =  hitCount [ i ]  - hitCount [ i - 1 ];  }  для  ( var  i  =  start ;  i  <  end ;  i ++ )  {  sortedArray [ hitCount [ интерполяция [ i ]]]  =  A [ i ];  hitCount [ интерполяция [ я ]] ++ ;  }  for  ( var  i  =  start ;  i  <  end ; i ++ )  {  A [ i ]  =  sortedArray [ i ];  }  }  } };

Вариант [ править ]

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

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

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

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

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

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

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

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

Практика [ править ]

Код JavaScript:

Массив . прототип . InterpolaionTagSort  =  function () { // Кит Чен соглашается с «Лицензией Wikipedia CC BY-SA 3.0». Дата подписи: 21.06.2019 //  var  end  =  this . длина ;  если  ( конец  >  1 )  {  var  start  =  0  ;  var  Tag  =  новый  массив ( конец );  // Шаг 1 алгоритма  для  ( var  i  =  0 ;  i  <  end;  i ++ )  {  Tag [  i  ]  =  false ;  }  Divide ( это );  }  while  ( end  >  1 )  {  // Шаг алгоритма 2  while  ( Tag [ - start ]  ==  false )  {  }  // Находим начало следующего сегмента  Divide ( this );  } функция  Divide ( A )  {  var  min  =  A [ начало ];  var  max  =  A [ начало ];  для  ( var  я  =  начало  +  1 ;  я  <  конец ;  я ++ )  {  если  ( А [ я ]  <  мин )  {  мин  =  А [ я ];  }  else  {  если ( A [ i ]  >  max )  {  max  =  A [ i ];  }  }  }  если  (  мин  ==  макс )  {  конец  =  начало ;  }  // Шаг алгоритма-3 Начало следующего сегмента  else  {  var  interpolation  =  0 ;  var  size  =  end  -  начало ;  var  Bucket  =  новый  массив (  размер  ); // Шаг 4 алгоритма  для  ( var  i  =  0 ;  i  <  size ;  i ++ )  {  Bucket [ i ]  =  new  Array ();  }  for  ( var  i  =  start ;  i  <  end ;  i ++ )  {  интерполяция  =  Math . этаж  ((( A [ i ]  -  min )  /  (макс  -  мин ))  *  ( размер  -  1 ));  Ковш [ интерполяция ]. push ( A [ i ]);  }  for  ( var  i  =  0 ;  i  <  size ;  i ++ )  {  if  ( Bucket [ i ]. length  >  0 )  {  //  Тег 5-го шага алгоритма [ start ]  =  true ; для  ( var  j  =  0 ;  j  <  Bucket [ i ]. length ;  j ++ )  {  A [ start ++ ]  =  Bucket [ i ] [ j ];  }  }  }  }  } // Шаг алгоритма-6 };

Сортировка тегов интерполяции на месте [ править ]

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

Учебный класс	Алгоритм сортировки
Структура данных	Множество
Пессимистический производительность	${\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  =  function () {  // Дата редактирования: 2019/07/02  var  n  =  this . длина ;  var  Tag  =  новый  массив (  n  );  for  (  i  =  0 ;  i  <  n ;  i ++  ) {  Tag [  i  ]  =  false ;  }  var  min  =  это [  0  ];  вар макс  =  это [  0  ];  для  (  я  =  1 ;  я  <  п ;  я ++  ) {  если  (  это [  я  ]  <  мин  ) {  мин  =  это [  я  ];  }  else {  если  ( это [  я  ]  >  макс ) {  макс  =  это [  я  ];  }  }  }  var  p  = 0 ;  var  temp  =  0 ;  for  (  i  =  0 ;  i  <  n ;  i ++  ) {  while  (  Tag [  i  ]  ==  false  ) {  p  =  Math . этаж (((  this [  i  ]  -  min  )  /  (  max  -  min  ))  *  (  n  -  1  ));  temp  =  это [ i  ];  this [  i  ]  =  this [  p  ];  this [  p  ]  =  temp ;  Тег [  p  ]  =  true ;  }  }  }; needSortArray . InPlaceTagSort ();

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

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

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

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

Подобный метод сортировки [ править ]

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

Сортировка корзин, сочетающая другие методы сортировки и рекурсивный алгоритм [ править ]

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

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

Ссылки [ править ]

Внешние ссылки [ править ]

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