Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Топ:
Оснащения врачебно-сестринской бригады.
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Интересное:
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Дисциплины:
2020-11-03 | 194 |
5.00
из
|
Заказать работу |
|
|
изобретенный Д. Уилльямсом, является улучшением традиционных сортировок с помощью дерева.
Пирамидой (кучей) называется двоичное дерево такое, что
a[i] ≤ a[2i+1];
a[i] ≤ a[2i+2].
a[0] — минимальный элемент пирамиды.
Общая идея пирамидальной сортировки заключается в том, что сначала строится пирамида из элементов исходного массива, а затем осуществляется сортировка элементов.
1) static Int32 add2pyramid(Int32[] arr, Int32 i, Int32 N)
{
Int32 imax;
Int32 buf;
if ((2 * i + 2) < N)
{
if (arr[2 * i + 1] < arr[2 * i + 2]) imax = 2 * i + 2;
else imax = 2 * i + 1;
}
else imax = 2 * i + 1;
if (imax >= N) return i;
if (arr[i] < arr[imax])
{
buf = arr[i];
arr[i] = arr[imax];
arr[imax] = buf;
if (imax < N / 2) i = imax;
}
return i;
}
static void Pyramid_Sort(Int32[] arr, Int32 len)
{
//step 1: building the pyramid
for (Int32 i = len / 2 - 1; i >= 0; --i)
{
long prev_i = i;
i = add2pyramid(arr, i, len);
if (prev_i!= i) ++i;
}
//step 2: sorting
Int32 buf;
for (Int32 k = len - 1; k > 0; --k)
{
buf = arr[0];
arr[0] = arr[k];
arr[k] = buf;
Int32 i = 0, prev_i = -1;
while (i!= prev_i)
{
prev_i = i;
i = add2pyramid(arr, i, k);
}
}
}
static void Main(string[] args)
{
Int32[] arr = new Int32[100];
//заполняем массив случайными числами
Random rd = new Random();
for(Int32 i = 0; i < arr.Length; ++i) {
arr[i] = rd.Next(1, 101);
}
System.Console.WriteLine("The array before sorting:");
foreach (Int32 x in arr)
{
System.Console.Write(x + " ");
}
//сортировка
Pyramid_Sort(arr, arr.Length);
System.Console.WriteLine("\n\nThe array after sorting:");
foreach (Int32 x in arr)
{
System.Console.Write(x + " ");
}
System.Console.WriteLine("\n\nPress the <Enter> key");
System.Console.ReadLine();
}
2) public class Heap<T>
{
private T[] _array; //массив сортируемых элементов
private int heapsize;//число необработанных элементов
private IComparer<T> _comparer;
public Heap(T[] a, IComparer<T> comparer){
_array = a;
heapsize = a.Length;
_comparer = comparer;
}
public void HeapSort(){
build_max_heap();//Построение пирамиды
for(int i = _array.Length - 1; i > 0; i--){
T temp = _array[0];//Переместим текущий максимальный элемент из нулевой позиции в хвост массива
_array[0] = _array[i];
|
_array[i] = temp;
heapsize--;//Уменьшим число необработанных элементов
max_heapify(0);//Восстановление свойства пирамиды
}
}
private int parent (int i) { return (i-1)/2; }//Индекс родительского узла
private int left (int i) { return 2*i+1; }//Индекс левого потомка
private int right (int i) { return 2*i+2; }//Индекс правого потомка
//Метод переупорядочивает элементы пирамиды при условии,
//что элемент с индексом i меньше хотя бы одного из своих потомков, нарушая тем самым свойство невозрастающей пирамиды
private void max_heapify(int i){
int l = left(i);
int r = right(i);
int lagest = i;
if (l<heapsize && _comparer.Compare(_array[l], _array[i])>0)
lagest = l;
if (r<heapsize && _comparer.Compare(_array[r], _array[lagest])>0)
lagest = r;
if (lagest!= i)
{
T temp = _array[i];
_array[i] = _array[lagest];
_array[lagest] = temp;
max_heapify(lagest);
}
}
//метод строит невозрастающую пирамиду
private void build_max_heap(){
int i = (_array.Length-1)/2;
while(i>=0){
max_heapify(i);
i--;
}
}
}
public class IntComparer: IComparer<int>
{
public int Compare(int x, int y) {return x-y;}
}
public static void Main (string[] args)
{
int[] arr = Console.ReadLine().Split(' ').Select(s=>int.Parse(s)).ToArray();//вводим элементы массива через пробел
IntComparer myComparer = new IntComparer();//Класс, реализующий сравнение
Heap<int> heap = new Heap<int>(arr, myComparer);
heap.HeapSort();
}
Алгоритм плавной сортировки (Smooth Sort).
Был изобретен Э. В. Дейкстрой в 1981 году и является развитием идеи Heap Sort (пирамидальной сортировки).
Реализован на языке программирования C#. Консольное приложение.
Пример кода из программы приведен ниже.
|
|
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!