В этом примере мы обсудим алгоритм сортировки кучи на C# он делит свои входные данные на сортированную и несортированную область, и он итеративно сжимает несортированную область, извлекая самый большой элемент и перемещая его в сортированную область.
Сначала он удаляет самый верхний элемент (самый большой) и заменяет его самым правым. Самый верхний элемент хранится в массиве и восстанавливает кучу, это выполняется до тех пор, пока в куче не останется больше элементов.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace heapsort { /* * C# Program to Heap Sort */ using System; class Heapsort { int[] r = { 2, 5, 1, 10, 6, 9, 3, 7, 4, 8 }; public void Hsort() { int i, t; for (i = 5; i >= 0; i--) { Adjust(i, 9); } for (i = 8; i >= 0; i--) { t = r[i + 1]; r[i + 1] = r[0]; r[0] = t; Adjust(0, i); } } private void Adjust(int i, int n) { int t, j; try { t = r[i]; j = 2 * i; while (j <= n) { if (j < n && r[j] < r[j + 1]) j++; if (t >= r[j]) break; r[j / 2] = r[j]; j *= 2; } r[j / 2] = t; } catch (IndexOutOfRangeException e) { Console.WriteLine("Массив выходит за границы ", e); } } public void Print() { for (int i = 0; i < 10; i++) { Console.WriteLine("{0}", r[i]); } } public static void Main() { Heapsort obj = new Heapsort(); Console.WriteLine("Элементы перед сортировкой : "); obj.Print(); obj.Hsort(); Console.WriteLine("Элементы после сортировки : "); obj.Print(); Console.Read(); } } } |
Вывод:
Элементы перед сортировкой :
2
5
1
10
6
9
3
7
4
8
Элементы после сортировки :
1
2
3
4
5
6
7
8
9
10