基本思想:堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的,每次都取堆顶的元素,将其放在序列最后面,然后将剩余的元素重新调整为最小(大)堆,依次类推,最终得到排序的序列。

堆排序分为大顶堆和小顶堆排序。大顶堆:堆对应一棵完全二叉树,且所有非叶结点的值均不小于其子女的值,根结点(堆顶元素)的值是最大的。而小顶堆正好相反,小顶堆:堆对应一棵完全二叉树,且所有非叶结点的值均不大于其子女的值,根结点(堆顶元素)的值是最小的。

C#算法实现:

/// <summary>
        /// 堆排序
        /// 堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的
        /// 每次都取堆顶的元素,将其放在序列最后面,然后将剩余的元素重新调整为最小堆,依次类推,最终得到排序的序列。
        /// </summary>
        /// <param name="arr"></param>
        /// <param name="length"></param>
        private static void HeapSort(int[] arr, int length)
        {
            CreateHeap(arr, length);
            //从最后的节点进行调整
            for (int i = length - 1; i > 0; i--)
            {
                //交换堆顶和最后一个节点的元素
                Swap(ref arr[0], ref arr[i]);
                //每次交换进行调整
                AdjustHeap(arr, 0, i - 1);
            }
        }

        /// <summary>
        /// 建堆方法:对初始序列建堆的过程,就是一个反复进行筛选的过程。
        /// 1)n 个结点的完全二叉树,则最后一个结点是第n/2个结点的子树。
        /// 2)筛选从第n/2个结点为根的子树开始,该子树成为堆。
        /// 3)之后向前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点。
        /// 完全二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。
        /// </summary>
        private static void CreateHeap(int[] arr, int length)
        {
            for (int i = length / 2 - 1; i >= 0; i--)
            {
                AdjustHeap(arr, i, length - 1);
            }
        }

        private static void AdjustHeap(int[] arr, int start, int length)
        {
            int root = start;
            int child = root * 2 + 1;
            while (child <= length)
            {
                //若子节点指标在范围内才做比较
                if (child + 1 <= length && arr[child] < arr[child + 1])
                {
                    //先比较两个子节点大小,选择最大的
                    child++;
                }
                //如果父节点大於子节点代表调整完毕,直接跳出函数
                if (arr[root] > arr[child])
                {
                    return;
                }
                else
                { 
                    //否则交换父子内容再继续子节点和孙节点比较
                    Swap(ref arr[root], ref arr[child]);
                    root = child;
                    child = root * 2 + 1;
                }
            }
        }

C#算法实现, List版本:

/// <summary>
        /// 归并排序 List版本
        /// 将两个(或两个以上)有序表合并成一个新的有序表
        /// </summary>
        public static List<int> MergeSort(List<int> list)
        {
            int count = list.Count;
            if (count <= 1)
            {
                return list;
            }
            int mid = count / 2;
            List<int> left = new List<int>();//定义左侧List
            List<int> right = new List<int>();//定义右侧List

            //以下两个循环把list分为左右两个List
            for (int i = 0; i < mid; i++)
            {
                left.Add(list[i]);
            }
            for (int j = mid; j < count; j++)
            {
                right.Add(list[j]);
            }
            left = MergeSort(left);
            right = MergeSort(right);
            return Merge(left, right);
        }
        /// <summary>
        /// 合并两个已经排好序的List
        /// </summary>
        /// <param name="left">左侧List</param>
        /// <param name="right">右侧List</param>
        /// <returns></returns>
        static List<int> Merge(List<int> left, List<int> right)
        {
            List<int> temp = new List<int>();
            while (left.Count > 0 && right.Count > 0)
            {
                if (left[0] <= right[0])
                {
                    temp.Add(left[0]);
                    left.RemoveAt(0);
                }
                else
                {
                    temp.Add(right[0]);
                    right.RemoveAt(0);
                }
            }
            if (left.Count > 0)
            {
                for (int i = 0; i < left.Count; i++)
                {
                    temp.Add(left[i]);
                }
            }
            if (right.Count > 0)
            {
                for (int i = 0; i < right.Count; i++)
                {
                    temp.Add(right[i]);
                }
            }
            return temp;
        }