算法系列15天速成 第二天 七大经典排序【中】

//找到该父节点左孩子节点
                child = 2 * parent + 1;
            }
            //最后将temp值赋给较大的子节点，以形成两值交换
            list[parent] = temp;
        }

///<summary>
/// 堆排序
///</summary>
///<param>待排序的集合</param>
///<param>前K大</param>
///<returns></returns>
        public static List<int> HeapSort(List<int> list, int top)
        {
            List<int> topNode = new List<int>();

//list.Count/2-1:就是堆中非叶子节点的个数
            for (int i = list.Count / 2 - 1; i >= 0; i--)
            {
                HeapAdjust(list, i, list.Count);
            }

//最后输出堆元素（求前K大）
            for (int i = list.Count - 1; i >= list.Count - top; i--)
            {
                //堆顶与当前堆的第i个元素进行值对调
                int temp = list[0];
                list[0] = list[i];
                list[i] = temp;

//最大值加入集合
                topNode.Add(temp);

//因为顺序被打乱，必须重新构造堆
                HeapAdjust(list, 0, i);
            }
            return topNode;
        }
    }
}

求前K大的输出结果：

最后堆排序赶紧拉着直接选择排序一路小跑了，因为求前K大问题已经不是他原本来的目的。

ps： 直接选择排序的时间复杂度为：O(n^2)

堆排序的时间复杂度：O(NlogN)

（编辑：焦作站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!