我们一起聊聊C#堆排序算法

前言

堆排序是一种高效的排序算法，基于二叉堆数据结构实现。它具有稳定性、时间复杂度为O(nlogn)和空间复杂度为O(1)的特点。RD828资讯网——每日最新资讯28at.com

堆排序实现原理

1. 构建最大堆：将待排序数组构建成一个最大堆，即满足父节点大于等于子节点的特性。
2. 将堆顶元素与最后一个元素交换：将最大堆的堆顶元素与堆中的最后一个元素交换位置，将最大元素放到了数组的末尾。
3. 重新调整堆：对剩余的n-1个元素进行堆调整，即将堆顶元素下沉，重新形成最大堆。
4. 重复步骤2和3，直到堆中的所有元素都被排列好。

堆排序代码实现

public static void HeapSort(int[] array)        {            int arrayLength = array.Length;            //构建最大堆            for (int i = arrayLength / 2 - 1; i >= 0; i--)                Heapify(array, arrayLength, i);            //依次取出堆顶元素，并重新调整堆            for (int i = arrayLength - 1; i >= 0; i--)            {                //将堆顶元素与当前最后一个元素交换                int temp = array[0];                array[0] = array[i];                array[i] = temp;                //重新调整堆                Heapify(array, i, 0);            }        }        private static void Heapify(int[] arr, int n, int i)        {            int largest = i; //假设父节点最大            int left = 2 * i + 1; //左子节点            int right = 2 * i + 2; //右子节点            //如果左子节点大于父节点，则更新最大值            if (left < n && arr[left] > arr[largest])                largest = left;            //如果右子节点大于父节点和左子节点，则更新最大值            if (right < n && arr[right] > arr[largest])                largest = right;            //如果最大值不是当前父节点，则交换父节点和最大值，并继续向下调整堆            if (largest != i)            {                int swap = arr[i];                arr[i] = arr[largest];                arr[largest] = swap;                Heapify(arr, n, largest);            }        }        public static void HeapSortRun()        {            int[] array = { 19, 27, 46, 48, 50, 2, 4, 44, 47, 36, 38, 15, 26, 5, 3, 99, 888, 0, -1 };            Console.WriteLine("排序前数组：" + string.Join(", ", array));            HeapSort(array);            Console.WriteLine("排序后数组：" + string.Join(", ", array));        }

运行结果

图片RD828资讯网——每日最新资讯28at.com

总结

堆排序是一种高效的排序算法，通过构建最大堆和反复调整堆的操作，实现对数组的排序。其时间复杂度为O(nlogn)，并且具有较好的稳定性和空间效率。但是由于其涉及大量的元素交换操作，所以在实际应用中，可能不如快速排序等算法效率高。RD828资讯网——每日最新资讯28at.com

本文链接：http://www.28at.com/showinfo-26-12710-0.html我们一起聊聊C#堆排序算法

声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com

上一篇： 两万字 + 十张图剖析Spring依赖注入和SpEL表达式

下一篇： 再使用System.out.println()打印收拾东西回家