Алгоритм поиска и сортировки C # Sharp: сортировка кучи

Алгоритм поиска и сортировки C # Sharp: упражнение 5 с решением

Напишите программу на C # Sharp для сортировки списка элементов, используя сортировку Heap.

В информатике, heapsort (изобретенный JWJ Williams в 1964 году) является алгоритмом сортировки на основе сравнения. Heapsort можно рассматривать как улучшенную сортировку выбора: подобно этому алгоритму, он делит свои входные данные на отсортированную и несортированную области и интерактивно сжимает несортированную область, выделяя самый большой элемент и перемещая его в отсортированную область. Улучшение состоит в использовании структуры данных кучи, а не линейного поиска времени, чтобы найти максимум. Хотя на некоторых машинах он работает несколько медленнее, чем хорошо реализованная быстрая сортировка, он обладает преимуществом более благоприятного времени выполнения O (n log n) в худшем случае. Heapsort - это алгоритм на месте, но он не является стабильным.

Запуск алгоритма heapsort, сортирующий массив случайно переставленных значений. На первом этапе алгоритма элементы массива переупорядочиваются в соответствии со свойством кучи. Перед фактической сортировкой кратко показана древовидная структура кучи для иллюстрации.

Анимационные кредиты: RolandH

Пример решения : -

C # острый код:

using System;
namespace Heap_sort
{
	public class MainClass
	{
		public static void Main (string[] args)
		{
			int[] mykeys = new int[] {2, 5, -4, 11, 0, 18, 22, 67, 51, 6};
			//double[] mykeys = new double[] {2.22, 0.5, 2.7, -1.0, 11.2};
		    //string[] mykeys = new string[] {"Red", "White", "Black", "Green", "Orange"};
              
			Console.WriteLine("\nOriginal Array Elements :");  
			printArray (mykeys);
			heapSort (mykeys);
           
		    Console.WriteLine("\n\nSorted Array Elements :");
			printArray (mykeys);
            Console.WriteLine("\n");
		}
		private static void heapSort<T> (T[] array) where T : IComparable<T>
		{
			int heapSize = array.Length;
			buildMaxHeap (array);
			for (int i = heapSize-1; i >= 1; i--)
			{
				swap (array, i, 0);
				heapSize--;
				sink (array, heapSize, 0);
			}
		}
		private static void buildMaxHeap<T> (T[] array) where T : IComparable<T>
		{
			int heapSize = array.Length;
			for (int i = (heapSize/2) - 1; i >= 0; i--)
			{
				sink (array, heapSize, i);
			}
		}
		private static void sink<T> (T[] array, int heapSize, int toSinkPos) where T : IComparable<T>
		{
			if (getLeftKidPos (toSinkPos) >= heapSize)
			{
				// No left kid => no kid at all
				return;
			}
			int largestKidPos;
			bool leftIsLargest;
			if (getRightKidPos (toSinkPos) >= heapSize || array [getRightKidPos (toSinkPos)].CompareTo (array [getLeftKidPos (toSinkPos)]) < 0)
			{
				largestKidPos = getLeftKidPos (toSinkPos);
				leftIsLargest = true;
			} else
			{
				largestKidPos = getRightKidPos (toSinkPos);
				leftIsLargest = false;
			}
			
			if (array [largestKidPos].CompareTo (array [toSinkPos]) > 0)
			{
				swap (array, toSinkPos, largestKidPos);
				if (leftIsLargest)
				{
					sink (array, heapSize, getLeftKidPos (toSinkPos));
				} else
				{
					sink (array, heapSize, getRightKidPos (toSinkPos));
				}
			}
		}
		private static void swap<T> (T[] array, int pos0, int pos1)
		{
			T tmpVal = array [pos0];
			array [pos0] = array [pos1];
			array [pos1] = tmpVal;
		}
		private static int getLeftKidPos (int parentPos)
		{
			return (2 * (parentPos + 1)) - 1;
		}
		private static int getRightKidPos (int parentPos)
		{
			return 2 * (parentPos + 1);
		}
		private static void printArray<T> (T[] array)
		{
							
			foreach (T t in array)
			{
			    Console.Write(' '+t.ToString()+' ');
			}
		}
	}
}

Пример вывода:

 Оригинальные элементы массива:                                                                                     
 2 5 -4 11 0 18 22 67 51 6                                                                           
                                                                                                              
Сортированные элементы массива:                                                                                       
 -4 0 2 5 6 11 18 22 51 67  

Блок - схема:

C # Sharp Практика онлайн:

Внесите свой код и комментарии через Disqus.

Предыдущий: Написать программу на C # Sharp для сортировки списка элементов с использованием сортировки Counting
Далее: Напишите программу на C # Sharp для сортировки списка элементов, используя сортировку Insertion.