精华内容
下载资源
问答
  • 堆排序算法(图解详细流程)

    万次阅读 多人点赞 2018-08-04 11:21:17
    堆排序的时间复杂度O(N*logN),额外空间复杂度O(1),是一个不稳定性的排序 目录 一 准备知识 1.1 大根堆和小根堆 二 堆排序基本步骤 2.1 构造堆 2.2固定最大值再构造堆 三 总结 四代码 一 准备知识 堆的...

    堆排序的时间复杂度O(N*logN),额外空间复杂度O(1),是一个不稳定性的排序

    目录

    一 准备知识

    1.1  大根堆和小根堆

    二 堆排序基本步骤

    2.1 构造堆

    2.2 固定最大值再构造堆

    三 总结

    四 代码

     


    一 准备知识

    的结构可以分为大根堆和小根堆,是一个完全二叉树,而堆排序是根据的这种数据结构设计的一种排序,下面先来看看什么是大根堆和小根堆

    1.1  大根堆和小根堆

    性质:每个结点的值都大于其左孩子和右孩子结点的值,称之为大根堆;每个结点的值都小于其左孩子和右孩子结点的值,称之为小根堆。如下图

     我们对上面的图中每个数都进行了标记,上面的结构映射成数组就变成了下面这个样子

    还有一个基本概念:查找数组中某个数的父结点和左右孩子结点,比如已知索引为i的数,那么

    1.父结点索引:(i-1)/2(这里计算机中的除以2,省略掉小数)

    2.左孩子索引:2*i+1

    3.右孩子索引:2*i+2

    所以上面两个数组可以脑补成堆结构,因为他们满足堆的定义性质:

    大根堆:arr(i)>arr(2*i+1) && arr(i)>arr(2*i+2)

    小根堆:arr(i)<arr(2*i+1) && arr(i)<arr(2*i+2)

    二 堆排序基本步骤

    基本思想:

    1.首先将待排序的数组构造成一个大根堆,此时,整个数组的最大值就是堆结构的顶端

    2.将顶端的数与末尾的数交换,此时,末尾的数为最大值,剩余待排序数组个数为n-1

    3.将剩余的n-1个数再构造成大根堆,再将顶端数与n-1位置的数交换,如此反复执行,便能得到有序数组

    2.1 构造堆

    将无序数组构造成一个大根堆(升序用大根堆,降序就用小根堆)

    假设存在以下数组

    主要思路:第一次保证0~0位置大根堆结构(废话),第二次保证0~1位置大根堆结构,第三次保证0~2位置大根堆结构...直到保证0~n-1位置大根堆结构(每次新插入的数据都与其父结点进行比较,如果插入的数比父结点大,则与父结点交换,否则一直向上交换,直到小于等于父结点,或者来到了顶端)

    插入6的时候,6大于他的父结点3,即arr(1)>arr(0),则交换;此时,保证了0~1位置是大根堆结构,如下图:

                                         (友情提示:待交换的数为蓝色,交换后的数为绿色)

     插入8的时候,8大于其父结点6,即arr(2)>arr(0),则交换;此时,保证了0~2位置是大根堆结构,如下图

    插入5的时候,5大于其父结点3,则交换,交换之后,5又发现比8小,所以不交换;此时,保证了0~3位置大根堆结构,如下图 

    插入7的时候,7大于其父结点5,则交换,交换之后,7又发现比8小,所以不交换;此时整个数组已经是大根堆结构 

     

    2.2 固定最大值再构造堆

    此时,我们已经得到一个大根堆,下面将顶端的数与最后一位数交换,然后将剩余的数再构造成一个大根堆

                                        (友情提示:黑色的为固定好的数字,不再参与排序) 

     此时最大数8已经来到末尾,则固定不动,后面只需要对顶端的数据进行操作即可,拿顶端的数与其左右孩子较大的数进行比较,如果顶端的数大于其左右孩子较大的数,则停止,如果顶端的数小于其左右孩子较大的数,则交换,然后继续与下面的孩子进行比较

    下图中,5的左右孩子中,左孩子7比右孩子6大,则5与7进行比较,发现5<7,则交换;交换后,发现5已经大于他的左孩子,说明剩余的数已经构成大根堆,后面就是重复固定最大值,然后构造大根堆

    如下图:顶端数7与末尾数3进行交换,固定好7,

    剩余的数开始构造大根堆 ,然后顶端数与末尾数交换,固定最大值再构造大根堆,重复执行上面的操作,最终会得到有序数组

     

    三 总结

    到这里,大家应该对堆排序都有了自己的见解,我们对上面的流程总结下:

    1、首先将无需数组构造成一个大根堆(新插入的数据与其父结点比较)

    2、固定一个最大值,将剩余的数重新构造成一个大根堆,重复这样的过程

    四 代码

    代码中主要两个方法:

    1、将待排序数组构造成一个大根堆(元素上升)

    2、固定一个最大值,将剩余的数再构造成一个大根堆(元素下降)

        //堆排序
        public static void heapSort(int[] arr) {
            //构造大根堆
            heapInsert(arr);
            int size = arr.length;
            while (size > 1) {
                //固定最大值
                swap(arr, 0, size - 1);
                size--;
                //构造大根堆
                heapify(arr, 0, size);
    
            }
    
        }
    
        //构造大根堆(通过新插入的数上升)
        public static void heapInsert(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                //当前插入的索引
                int currentIndex = i;
                //父结点索引
                int fatherIndex = (currentIndex - 1) / 2;
                //如果当前插入的值大于其父结点的值,则交换值,并且将索引指向父结点
                //然后继续和上面的父结点值比较,直到不大于父结点,则退出循环
                while (arr[currentIndex] > arr[fatherIndex]) {
                    //交换当前结点与父结点的值
                    swap(arr, currentIndex, fatherIndex);
                    //将当前索引指向父索引
                    currentIndex = fatherIndex;
                    //重新计算当前索引的父索引
                    fatherIndex = (currentIndex - 1) / 2;
                }
            }
        }
        //将剩余的数构造成大根堆(通过顶端的数下降)
        public static void heapify(int[] arr, int index, int size) {
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            while (left < size) {
                int largestIndex;
                //判断孩子中较大的值的索引(要确保右孩子在size范围之内)
                if (arr[left] < arr[right] && right < size) {
                    largestIndex = right;
                } else {
                    largestIndex = left;
                }
                //比较父结点的值与孩子中较大的值,并确定最大值的索引
                if (arr[index] > arr[largestIndex]) {
                    largestIndex = index;
                }
                //如果父结点索引是最大值的索引,那已经是大根堆了,则退出循环
                if (index == largestIndex) {
                    break;
                }
                //父结点不是最大值,与孩子中较大的值交换
                swap(arr, largestIndex, index);
                //将索引指向孩子中较大的值的索引
                index = largestIndex;
                //重新计算交换之后的孩子的索引
                left = 2 * index + 1;
                right = 2 * index + 2;
            }
    
        }
        //交换数组中两个元素的值
        public static void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

                                                                  友情提示:手机观看,可以左右滑动 

     

     

     

    展开全文
  • 堆排序算法

    2021-06-01 10:05:55
      堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的...  例如: 使用堆排序算法将数组 { 4,2,

      堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:

    • 大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;
    • 小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列。

      算法: 把未排序的数据一个一个放入堆里,然后再一个一个取出来。

      步骤: 1. 将待排序的数组调整为最大堆;
          2. 把堆首(最大值)和堆尾互换;
          3. 将堆的尺寸缩小1,再重新调整为最大堆,目的是把新的数组顶端数据调整到相应位置;
          4. 回到步骤 2,直到堆的尺寸为 1。

      例如: 使用堆排序算法将数组 { 4,2,8,0,5,7,1,3,6,9 } 进行升序排序。

    在这里插入图片描述
      实现代码如下所示。

    #include <iostream>
    using namespace std;
    #include <algorithm>
    
    // 最大堆调整
    void MaxHeapify(int arr[], int start, int end) 
    {
    	// 建立父结点指标和子结点指标
    	int Parent = start;
    	int Child = Parent * 2 + 1;
    	while (Child <= end)  // 若子结点指标在范围内才做比较
    	{
    		if (Child + 1 <= end && arr[Child] < arr[Child + 1]) // 先比较两个子结点指标大小,选择最大的
    			Child++;
    		if (arr[Parent] > arr[Child]) // 如果父结点大于子结点代表调整完毕,直接跳出函数
    			return;
    		else { // 否则交换父子内容再继续子结点和孙结点比较
    			swap(arr[Parent], arr[Child]);
    			Parent = Child;
    			Child = Parent * 2 + 1;
    		}
    	}
    }
    
    void HeapSort(int arr[], int len) 
    {
    	// 初始化,i从最后一个父结点开始调整
    	for (int i = len / 2 - 1; i >= 0; i--)
    		MaxHeapify(arr, i, len - 1);
    	// 先将第一个元素和已经排好的元素前一位做交换,再重新调整(刚调整的元素之前的元素),直到排序完毕
    	for (int i = len - 1; i > 0; i--) 
    	{
    		swap(arr[0], arr[i]);
    		MaxHeapify(arr, 0, i - 1);
    	}
    }
    
    int main() 
    {
    	int arr[] = { 4,2,8,0,5,7,1,3,6,9 };
    	int len = (int) sizeof(arr) / sizeof(*arr);
    	HeapSort(arr, len);
    	for (int i = 0; i < len; i++)
    		cout << arr[i] << ' ';
    	cout << endl;
    	system("pause");
    	return 0;
    }
    

    排序前:
    4 2 8 0 5 7 1 3 6 9
    排序后:
    0 1 2 3 4 5 6 7 8 9

      堆排序算法的详细过程如下图所示。

    在这里插入图片描述
      时间复杂度: 堆排序的时间复杂度为O(nlogn)Ο(nlogn)

      空间复杂度: O(1)O(1)

      稳定性: 由于在排序的过程中,用最大堆的结构排序,排序前后两个相同元素的位置会发生变化,所以堆排序是不稳定的排序,如下图所示。

    在这里插入图片描述

    展开全文
  • 算法 - 堆排序(C#)

    万次阅读 多人点赞 2019-02-01 15:34:50
    * 堆排序是一种选择排序,时间复杂度为O(nlog&lt;sub&gt;2&lt;/sub&gt;n)。 * * 堆排序的特点是: * 排序过程中,将待排序数组看成是一棵完全二叉树的顺序存储结构, * 利用完全二叉树中父...

    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请点击http://www.captainbed.net 

    /*
     * 堆排序是一种选择排序,时间复杂度为O(nlog<sub>2</sub>n)。
     * 
     * 堆排序的特点是:
     * 在排序过程中,将待排序数组看成是一棵完全二叉树的顺序存储结构,
     * 利用完全二叉树中父结点和子结点之间的内在关系,在当前无序区中选择关键字最大(或最小)的记录。
     *
     * 基本思想
     * 1.将待排序数组调整为一个大根堆。大根堆的堆顶元素就是这个堆中最大的元素。
     * 2.将大根堆的堆顶元素和无序区最后一个元素交换,并将无序区最后一个位置列入有序区,然后将新的无序区调整为大根堆。
     * 3.重复操作,直到无序区消失为止。
     * 初始时,整个数组为无序区。每一次交换,都是将大根堆的堆顶元素换入有序区,以保证有序区是有序的。
     */
    
    namespace HeapSort
    {
        using System;
    
        /// <summary>
        /// The program.
        /// </summary>
        public static class Program
        {
            /// <summary>
            /// 程序入口点。
            /// </summary>
            public static void Main()
            {
                int[] a = {1, 14, 6, 2, 8, 66, 9, 3, 0, 10, 5, 34, 76, 809, 4, 7};
    
                Console.WriteLine("Before Heap Sort:");
                foreach (int i in a)
                {
                    Console.Write(i + " ");
                }
    
                Console.WriteLine("\r\n");
    
                Console.WriteLine("In Heap Sort:");
                HeapSort(a);
                Console.WriteLine("");
    
                Console.WriteLine("After Heap Sort:");
                foreach (int i in a)
                {
                    Console.Write(i + " ");
                }
            }
    
            /// <summary>
            /// 堆排序方法。
            /// </summary>
            /// <param name="a">
            /// 待排序数组。
            /// </param>
            private static void HeapSort(int[] a)
            {
                // 建立大根堆。
                BuildMaxHeap(a);
                Console.WriteLine("Build max heap:");
                foreach (int i in a)
                {
                    // 打印大根堆。
                    Console.Write(i + " ");
                }
    
                Console.WriteLine("\r\nMax heap in each heap sort iteration:");
                for (int i = a.Length - 1; i > 0; i--)
                {
                    // 将堆顶元素和无序区的最后一个元素交换。
                    Swap(ref a[0], ref a[i]);
    
                    // 将新的无序区调整为大根堆。
                    MaxHeaping(a, 0, i);
    
                    // 打印每一次堆排序迭代后的大根堆。
                    for (int j = 0; j < i; j++)
                    {
                        Console.Write(a[j] + " ");
                    }
    
                    Console.WriteLine(string.Empty);
                }
            }
    
            /// <summary>
            /// 由底向上建堆。
            /// 由完全二叉树的性质可知,叶子结点是从index=a.Length/2开始,
            /// 所以从index=(a.Length/2)-1结点开始由底向上进行大根堆的调整。
            /// </summary>
            /// <param name="a">
            /// 待排序数组。
            /// </param>
            private static void BuildMaxHeap(int[] a)
            {
                for (int i = (a.Length / 2) - 1; i >= 0; i--)
                {
                    MaxHeaping(a, i, a.Length);
                }
            }
    
            /// <summary>
            /// 将指定的结点调整为堆。
            /// </summary>
            /// <param name="a">
            /// 待排序数组。
            /// </param>
            /// <param name="i">
            /// 需要调整的结点。
            /// </param>
            /// <param name="heapSize">
            /// 堆的大小,也指数组中无序区的长度。
            /// </param>
            private static void MaxHeaping(int[] a, int i, int heapSize)
            {
                // 左子结点。
                int left = (2 * i) + 1;
    
                // 右子结点。
                int right = 2 * (i + 1);
    
                // 临时变量,存放大的结点值。
                int large = i;
    
                // 比较左子结点。
                if (left < heapSize && a[left] > a[large])
                {
                    large = left;
                }
    
                // 比较右子结点。
                if (right < heapSize && a[right] > a[large])
                {
                    large = right;
                }
    
                // 如有子结点大于自身就交换,使大的元素上移;并且把该大的元素调整为堆以保证堆的性质。
                if (i != large)
                {
                    Swap(ref a[i], ref a[large]);
                    MaxHeaping(a, large, heapSize);
                }
            }
    
            /// <summary>
            /// 交换两个整数的值。
            /// </summary>
            /// <param name="a">整数a。</param>
            /// <param name="b">整数b。</param>
            private static void Swap(ref int a, ref int b)
            {
                int tmp = a;
                a = b;
                b = tmp;
            }
        }
    }
    
    // Output:
    /*
    Before Heap Sort:
    1 14 6 2 8 66 9 3 0 10 5 34 76 809 4 7
    
    In Heap Sort:
    Build max heap:
    809 14 76 7 10 66 9 3 0 8 5 34 1 6 4 2
    Max heap in each heap sort iteration:
    76 14 66 7 10 34 9 3 0 8 5 2 1 6 4
    66 14 34 7 10 4 9 3 0 8 5 2 1 6
    34 14 9 7 10 4 6 3 0 8 5 2 1
    14 10 9 7 8 4 6 3 0 1 5 2
    10 8 9 7 5 4 6 3 0 1 2
    9 8 6 7 5 4 2 3 0 1
    8 7 6 3 5 4 2 1 0
    7 5 6 3 0 4 2 1
    6 5 4 3 0 1 2
    5 3 4 2 0 1
    4 3 1 2 0
    3 2 1 0
    2 0 1
    1 0
    0
    
    After Heap Sort:
    0 1 2 3 4 5 6 7 8 9 10 14 34 66 76 809
    */

     

    展开全文
  • 堆排序(Heapsort)是利用二叉堆的概念来排序的选择排序算法,分为两种: 升序排序:利用最大堆进行排序 降序排序:利用最小堆进行排序 2.算法原理 给定一个最大堆如下图所示,以该最大堆进行演示堆排序 首先,...
    十大经典排序算法

    一、什么是堆排序

    1.概念

    堆排序(Heapsort)是利用二叉堆的概念来排序的选择排序算法,分为两种:

    • 升序排序:利用最大堆进行排序
    • 降序排序:利用最小堆进行排序

    2.算法原理

    给定一个最大堆如下图所示,以该最大堆进行演示堆排序
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pA3T0B2E-1593593813254)(./堆1.png)]
    首先,删除堆顶元素10(即最大的元素),并将最后的元素3补充到堆顶,删除的元素10,放置于原来最后的元素3的位置
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xhj6pvKP-1593593813256)(./堆2.png)]
    根据二叉堆的自我调整,第二大的元素9会成为二叉堆新的堆顶
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dqQ6As6S-1593593813258)(./堆3.png)]
    删除元素9,元素8成为最大堆堆顶
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RGnf46zw-1593593813260)(./堆4.png)]
    删除元素8,元素7成为最大堆堆顶
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0j119X1X-1593593813262)(./堆5.png)]
    依次删除最大元素,直至所有元素全部删除
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QpnvGNu3-1593593813264)(./堆6.png)]
    此时,被删除的元素组成了一个从小到大排序的序列
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4UVRJMQr-1593593813265)(./堆7.png)]

    3.算法实现

    // 下沉调整
    // 最大堆
    function downAdjust(arr, parentIndex, length) {
        // 缓存父节点的值,用于最后进行赋值,而不需要每一步进行交换
        let temp = arr[parentIndex];
        // 孩子节点下标,暂时定为左孩子节点下标
        let childIndex = 2 * parentIndex + 1;
    
        while (childIndex < length) {
            // 当存在右孩子节点,且右孩子节点的值小于左孩子节点的值,childIndex记录为右孩子节点的下标
            // childIndex实际记录的是最小的孩子节点的下标
            if (childIndex + 1 < length && arr[childIndex + 1] > arr[childIndex]) {
                childIndex++;
            }
    
            // 如果父节点的值比孩子节点的值都小,则调整结束
            if (temp >= arr[childIndex]) {
                break;
            }
    
            // 将最小的孩子节点的值赋值给父节点
            arr[parentIndex] = arr[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * parentIndex + 1;
        }
        arr[parentIndex] = temp;
    }
    
    // 堆排序
    function sort(arr) {
        // 把无序数组构建成二叉堆
        for (let i = parseInt(arr.length / 2) - 1; i >= 0; i--) {
            downAdjust(arr, i, arr.length);
        }
        console.log(arr);
    
        // 循环删除堆顶元素,移到集合尾部,调节堆产生新的堆顶
        for (let i = arr.length - 1; i > 0; i--) {
            // 最后一个元素与第一个元素交换
            [arr[0], arr[i]] = [arr[i], arr[0]];
            downAdjust(arr, 0, i);
        }
    }
    
    let arr = [10, 9, 8, 5, 6, 7, 1, 4, 2, 3];
    sort(arr);
    console.log(arr);
    

    三、堆排序算法特点

    1.时间复杂度

    下沉调整的时间复杂度等同于堆的高度O(logn),构建二叉堆执行下沉调整次数是n/2,循环删除进行下沉调整次数是n-1,时间复杂度约为O(nlogn)

    2.空间复杂度

    堆排序算法排序过程中需要一个临时变量进行两两交换,所需要的额外空间为1,因此空间复杂度为O(1)

    3.稳定性

    堆排序算法在排序过程中,相同元素的前后顺序有可能发生改变,所以堆排序是一种不稳定排序算法


    另外推荐一个开发者小工具网站,个人觉得里面的Json格式化功能很强大,报错很详细

    https://tinyutil.com/

    还可以输入表达式进行内容选取,对于复杂json非常多层级的内容展现非常用用处
    在这里插入图片描述

    展开全文
  • 堆排序算法之初始堆建立总结

    万次阅读 多人点赞 2016-12-01 23:52:52
    堆排序算法之初始堆建立总结@(算法学习)关于堆的插入和删除有过一篇思考,但是关于初始堆的构建,没有总结。简单说就下面几个要点(以大顶堆为例): 首先根据序列构建一个完全二叉树 完全二叉树的基础上,从最后...
  • 排序算法堆排序

    万次阅读 2020-07-04 17:53:11
    堆排序是利用堆这种数据结构而设计的一种排序算法堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。 堆排序可以认为是对选择排序算法中寻找最小(大)元素的优化。 一般升序...
  • 堆排序算法——C/C++

    万次阅读 多人点赞 2019-06-13 00:34:07
    堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 2、实现原理 要实现从小到大的...
  • 堆排序算法详解

    万次阅读 多人点赞 2018-10-14 16:45:41
    一、堆排序算法原理和动态图解  将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根节点。将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新...
  • 十大经典排序算法-堆排序,计数排序,桶排序,基数排序 1-堆排序 算法思想: 算法图解: 示例代码: 这里插入代码片 复杂度分析: 2-计数排序 算法思想: 算法图解: 示例代码: 这里插入代码片 复杂度分析: 3-桶排序 ...
  • 排序算法:堆排序算法实现及分析

    万次阅读 热门讨论 2018-02-23 20:48:53
    堆排序介绍堆排序(Heap Sort)就来利用堆(假设利用大顶堆)进行排序的方法。它的基本思想是,将待排序的序列构成一个大顶堆。此时,整个序列的最大值就是堆顶的根结点。将它移走(其实就是将其与堆数组的末尾元素...
  • 堆排序算法知识点总结

    千次阅读 2016-04-18 23:16:12
    1. 在用堆排序算法排序时,如果要进行增序排序,则需要采用“大根堆”,减序排列则要采用“小根堆”。堆排序的方法:首先,将当前的数组调整为堆,也就是建立堆。然后把根与最后的元素交换,重新调整堆,然后再把调整...
  • 八大排序算法 一、直接插入 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度 二、希尔排序 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度 三、简单选择 - 1.基本思路 - 2.代码实现 - 3.时间复杂度...
  • 算法-详解堆排序算法

    千次阅读 2017-07-07 01:39:17
    堆排序是利用堆的性质进行的一种选择排序。时间复杂度: 时间复杂度:O(nlogn) 空间复杂度:O(1)(就地排序,用于堆化(又称筛选)的辅助空间) 性能: 由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录...
  • 排序算法——堆排序

    千次阅读 2019-07-22 14:48:18
    介绍堆排序之前我们首先应该弄清楚堆排序可以解决什么问题,答案是显而易见的:排序。说得通俗点儿就是对一组无序的数字进行调整,使其按照从大到小或者从小大到的顺序有序排列。既然知道了堆排序的作用了,那么有...
  • 堆排序(Heap sort)是指利用堆(最大堆、最小堆)这种数据结构所设计的一种排序算法。堆是一个完全二叉树的结构,并同时满足如下性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 一、算法基本...
  • 八大排序算法

    万次阅读 多人点赞 2012-07-23 16:45:18
    概述 排序有内部排序和外部排序,...当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分...
  • C++实现堆排序算法

    千次阅读 2018-10-30 07:21:49
    1.实现堆排序算法  C++实现一个堆排序。 2.实现思想 ① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区  ② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换, 由此得到新的...
  • 排序算法之堆和堆排序

    千次阅读 2013-11-03 00:03:01
    堆和堆排序思想,以及堆排序算法实现过程。
  • 堆排序算法及C语言实现

    千次阅读 2014-11-02 11:17:11
    堆排序算法及C语言实现
  • 排序算法-堆排序

    千次阅读 2015-06-22 21:29:11
    堆排序算法是建立堆这种数据结构的基础上,其实堆听着很高端,其实很简单,就是一个二叉树,但是又特殊条件,就是其父节点比孩子节点都大(或都小)的堆称为最大堆(最小堆),瞬间感觉很简单了,最简单的保存方法...
  • C++:堆排序算法详解

    千次阅读 2018-06-07 21:28:57
    图解排序算法(三)之堆排序预备知识堆排序 堆排序是利用堆这种数据结构而设计的一种排序算法堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。首先简单了解下堆结构。堆 堆...
  • 排序算法6——堆排序

    千次阅读 2017-02-18 22:48:41
    堆排序简介 二叉堆简介 堆排序 总结堆排序简介堆排序可以看作是简单选择排序的一种的改进方法,平均复杂度为 \(O(n\log n)\),因此应用场合较多。其原理同简单选择排序相似:将数据分为已排序和未排序的两部分,并且...
  • 精通八大排序算法系列:二、堆排序算法

    万次阅读 热门讨论 2011-02-21 21:46:00
    精通八大排序算法系列:二、堆排序算法作者:July 、二零一一年二月二十日本文参考:Introduction To Algorithms,second edition。-------------------此精通排序算法系列,前一节,已讲过了快速排序算法,据我所知...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 183,097
精华内容 73,238
关键字:

在用堆排序算法排序时