2019-10-02 09:34·巴黎人线上注册

堆排序的时日复杂度分为八个部分一个是建堆的时候所消耗的日子,一个是打开堆调治的时候所开销的光阴。而堆排序则是调用了建堆和堆调节。

3.算法手续:

堆排序

堆排序节点访谈和操作定义

(1) 先将营造贰个大根堆,此堆为发端的严节区

堆的定义

  堆是一种特有的树形数据结构,每一种结点都有二个值.经常大家所说的堆的数据结构,是指二叉堆.堆的风味是根结点的值最小(或最大),且根结点的三个子树也是三个堆。堆排序是选择排序的一种,能够采取数组的性状火速稳固钦命索引的因素。堆分为大根堆和小根堆,是全然二叉树当父结点的键值总是凌驾或等于任何多个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。

堆操作

堆排序(Heapsort)是支使用堆放树(堆)这种数据结构所设计的一种排序算法,它是挑选排序的一种。堆分为大根堆和小根堆。大根堆的渴求是各个节点的值都不超越其父节点的值。 在数组的非降序排序中,须求使用的正是大根堆,因为依据大根堆的渴求可以,最大的值一定在堆顶。翻开完整代码

堆的囤积

  日常都用数组来代表堆,大家用长度为N+1的数组来表示一个轻重为N的堆,大家不会利用数组的率先个任务,这么做的指标是为着便利定位钦赐地方结点的父节点与子结点的地方,这样我们能够很轻松的精通在叁个堆中,地点K的结点的父节点的任务为K/2,而它的八个子节点的职位则分别为2K和2K+1。

因为建堆的时间复杂度是O(n),调解堆的时刻复杂度是lgn,所以堆排序的时刻复杂度是O(nlgn)。

(2)调节堆:调度堆在营造堆的长河中会用到,何况在堆排序进程中也会用到。利用的思量是相比较节点i和它的男女节点left(i),right(i),选出三者最大(或然最小)者,要是最大(小)值不是节点i而是它的三个男女节点,那边互相节点i和该节点,然后再调用调治堆进程,那是一个递归的进程。调度堆的过程时间复杂度与堆的深度有关联,是lgn的操作,因为是本着深度方向拓宽调治的。

堆排序剖析

  再来回看下推排序的历程
  第一步建堆,建堆是时时四处调度堆的历程,从len/2处发轫调节,一直到首个节点,建堆的进程是线性的过程,从len/2到1处一贯调用调节堆的进度,也正是o(h1)+o(h2)…+o(hlen/2) 个中h表示节点的吃水,len/2代表节点的个数,那是三个求和的长河,结果是线性的O(n)。
  第二步调解堆:调治堆在创设堆的经过中会用到,并且在堆排序进程中也会用到。利用的合计是比较节点i和它的子女节点left(i),right(i),选出三者最大(或然最小)者,假诺最大(小)值不是节点i而是它的三个儿女节点,则交换节点i和该节点,然后再调用调解堆进度,那是贰个递归的历程。调解堆的长河时间复杂度与堆的吃水有涉及,是lgn的操作,因为是本着深度方向扩充调解的。
  第三步堆排序:堆排序是利用方面包车型地铁五个进度来实行的。首先是基于成分营造堆。然后将堆的根节点收取(平时是与最后三个节点实行交流),将眼下len-1个节点继续拓宽堆调治的长河,然后再将根节点收取,那样直白到具备节点都抽出。堆排序进程的时辰复杂度是O(nlogn)。因为建堆的时间复杂度是O(n)(调用贰遍);调治堆的时刻复杂度是lgn,调用了n-1次,所以堆排序的时日复杂度是 O(nlogn)
  堆排序方法对记录数少之又少的文件并不值一提倡,但对n十分大的文本照旧很实惠的。因为其运作时刻首要花费在建伊始堆和调节建新堆时开展的再三“筛选”上,堆排序在最坏的动静下,其时间复杂度也为O(nlogn)。相对于高效排序来讲,那是堆排序的最大优点。另外,堆排序仅需几个笔录大小的供交流用的帮扶存款和储蓄空间

 

堆节点的拜望

平安:不平稳的一种排序算法

堆排序的兑现

  大家能够动用根结点为最大(或相当小)的性质,来完成堆排序,每趟抽取根结点后,对余下的数目再次布局堆,一向到最后三个要素,所以大家须要消除四个问题
  1.一旦将三个系列创设成堆
  2.输出堆顶成分之后,若是将盈余的成分塑变成四个新堆
  大家需求先创建一个堆,而建堆的主旨内容是调解堆,使二叉树知足堆的概念,调堆的进度应该从最终一个非叶子节点早先,借使有数组A = {2, 3, 8, 5, 7, 1, 6, 4, 9}
调堆的进度应该从最终一个非叶子节点开首依照,大家通晓最终一个非叶子结点为N/2向下取整,假如数组下标从1初阶末了贰个非叶子结点为 A[4]=5,分别与左孩子和右孩子不小小,要是为最小则不用调治,不然和纤维的叶子结点进行置换,大家驾驭地点K的结点的父节点的职位为K/2,而它的三个子节点的地方则分级为2K和2K+1 七个叶子结点分别为 A[8]=4,A[9]=9, 由于A[8]<A[4]<A[9] 所以A[4]和A[8]  建堆的经过如下图

科技世界 1

  堆创造好以往,就能够实行第二步操作了,堆排序是一种选拔排序,排序开端,首先输出堆顶成分,将堆顶成分和结尾三个要素交流,那样,第n个任务(即最终七个职位)作为有序区,前n-1个职位仍是无序区,对无序区进行调治,获得堆之后,再调换堆顶和终极多个要素,那样有序区长度变为2。。。不断拓宽此操作,将盈余的成分重新调度为堆,然后输出堆顶成分到有序区。每一遍沟通都形成冬季区-1,有序区+1。不断重复此进度直到有序村长度拉长为n-1,排序达成。

代码如下

        /// <summary>
        /// 构建堆
        /// </summary>
        /// <param name="array"></param>
        /// <param name="hLen"></param>
        void BuildHeap(int[] array, int hLen)
        {
            int i;
            int begin = hLen / 2 - 1 ;  //最后一个非叶子节点
            for (i = begin; i >= 0; i--)
            {
                AdjustHeap(array, hLen, i);
            }
        }

        /// <summary>
        /// 排序
        /// </summary>
        /// <param name="array"></param>
        void HeapSort(int[] array)
        {
            int hLen = array.Length;
            int temp;
            BuildHeap(array, hLen);      //建堆
            while (hLen > 1)
            {
                temp = array[hLen - 1];    //交换堆的第一个元素和堆的最后一个元素
                array[hLen - 1] = array[0];
                array[0] = temp;
                hLen--;        //堆的大小减一
                AdjustHeap(array, hLen, 0);  //调堆
            }
        }

        /// <summary>
        /// 调整堆
        /// </summary>
        /// <param name="array"></param>
        /// <param name="hLen">堆的长度</param>
        /// <param name="i">需要调整的节点</param>
        void AdjustHeap(int[] array, int hLen, int i)
        {
            int left = 2 * i + 1;  //节点i的左孩子
            int right = left + 1; //节点i的右孩子节点
            int min = i;
            int temp;
            while (left < hLen || right < hLen)
            {
                if (left < hLen && array[min] > array[left])
                {
                    min = left;
                }
                if (right < hLen && array[min] > array[right])
                {
                    min = right;
                }
                if (i != min) //最小结点发生变化 进行交换
                {
                    temp = array[min];
                    array[min] = array[i];
                    array[i] = temp;
                    i = min;          //调整交换后的节点 
                    left = 2 * i +1 ;
                    right = left + 1;
                }
                else
                {
                    break;
                }
            }
        }

堆能够分成大根堆和小根堆,这里用最大堆的景况来定义操作:

科技世界 2

恰巧在地点也提起到了,建堆是三个线性进程,从len/2-0向来调用堆调度的历程,也正是o(h1)+o(h2)+…+o(hlen/2)这里的h表示节点深度,len/2代表节点深度,对于求和进程,结果为线性的O(n)

(2) 再将堆顶(根节点)与最后一个要素调换,由此赢得新的严节区array[1..n-1]和有序区array[n]。

科技世界 3

4.算法解析:

运行结果:

2.算法合计:

[30, 50, 57, 77, 62, 78, 94, 80, 84]
[30, 50, 57, 62, 77, 78, 80, 84, 94]
[107, 115, 207, 919, 128, 651, 534, 546, 217, 295, 54, 202, 498, 620, 174, 897, 873, 112, 873, 729, 588, 669, 994, 773, 462, 550, 347, 597, 440, 426, 271, 677, 323, 302, 604, 154, 589, 871, 235, 305, 502, 743, 575, 53, 130, 686, 726, 959, 980, 884, 542, 246, 292, 226, 608, 357, 229, 168, 415, 671, 972, 142, 472, 375, 522, 486, 241, 368, 839, 841, 137, 545, 427, 601, 476, 229, 757, 601, 136, 506, 394, 975, 162, 163, 26, 776, 886, 82, 37, 248, 47, 246, 23, 895, 623, 373, 147, 109, 553, 176, 204, 530, 927, 656, 153, 487, 743, 113, 20, 334, 554, 850, 510, 423, 373, 207, 795, 403, 499, 509, 531, 256, 920, 313, 694, 322, 100, 825, 578, 954, 526, 92, 820, 9, 931, 303, 408, 132, 833, 194, 902, 766, 14, 140, 729, 328, 636, 316, 536, 232, 687, 425, 811, 432, 955, 715, 339, 861, 736, 411, 901, 609, 353, 97, 330, 896, 852, 1000, 828, 5, 879, 41, 642, 719, 35, 621, 742, 285, 715, 987, 246, 641, 636, 993, 368, 140, 319, 647, 555, 436, 479, 85, 669, 899, 556, 71, 237, 189, 211, 106, 623, 164, 371, 137, 730, 679, 491, 981, 372, 483, 50, 676, 125, 868, 903, 33, 555, 710, 199, 835, 458, 311, 384, 81, 784, 338, 3, 665, 934, 362, 122, 816, 2, 439, 869, 94, 806, 760, 309, 372, 360, 61, 756, 995, 642, 652, 176, 85, 735, 894, 745, 654, 734, 699, 933, 59, 168, 311, 313, 758, 753, 122, 195, 902, 527, 305, 106, 281, 321, 681, 323, 858, 877, 278, 966, 706, 947, 648, 893, 247, 882, 931, 859, 675, 243, 129, 424, 475, 478, 946, 720, 881, 737, 470, 252, 921, 382, 659, 441, 854, 553, 134, 116, 183, 285, 353, 285, 840, 80, 661, 353, 556, 916, 861, 901, 496, 888, 686, 70, 600, 998, 457, 707, 980, 572, 950, 111, 3, 320, 620, 181, 796, 731, 892, 629, 106, 539, 58, 173, 126, 922, 381, 129, 859, 63, 633, 723, 628, 661, 128, 582, 893, 479, 379, 831, 863, 245, 49, 735, 419, 713, 887, 833, 399, 26, 698, 280, 839, 220, 604, 764, 782, 974, 912, 939, 604, 26, 229, 130, 949, 99, 671, 481, 885, 907, 116, 621, 546, 201, 21, 213, 242, 172, 899, 627, 996, 933, 957, 168, 386, 788, 643, 200, 646, 32, 496, 722, 375, 271, 553, 542, 370, 904, 393, 74, 42, 948, 428, 155, 311, 486, 708, 936, 819, 201, 763, 927, 596, 26, 902, 467, 31, 631, 540, 472, 909, 809, 832, 88, 240, 934, 598, 531, 337, 839, 552, 183, 694, 611, 693, 518, 397, 897, 526, 849, 15, 776, 438, 133, 771, 412, 174, 619, 245, 711, 423, 383, 556, 604, 310, 139, 879, 995, 870, 173, 98, 174, 441, 627, 712, 637, 470, 350, 509, 261, 648, 443, 152, 690, 486, 901, 52, 425, 45, 684, 243, 94, 655, 679, 534, 31, 778, 405, 316, 8, 640, 236, 903, 526, 579, 43, 595, 884, 225, 188, 483, 909, 890, 846, 794, 682, 649, 569, 1000, 840, 292, 614, 986, 305, 800, 763, 563, 266, 134, 202, 156, 231, 896, 174, 696, 914, 235, 302, 358, 538, 595, 770, 462, 13, 960, 768, 106, 119, 370, 602, 807, 622, 770, 359, 768, 209, 314, 195, 590, 527, 275, 775, 785, 271, 557, 680, 756, 399, 426, 730, 57, 905, 643, 852, 406, 932, 204, 757, 348, 655, 812, 891, 887, 214, 171, 296, 279, 81, 383, 668, 271, 335, 345, 541, 997, 659, 671, 732, 525, 811, 612, 704, 23, 1000, 511, 731, 505, 818, 815, 766, 689, 978, 721, 987, 546, 824, 753, 277, 838, 16, 382, 910, 332, 301, 727, 851, 395, 310, 649, 432, 864, 894, 756, 400, 116, 31, 990, 232, 611, 75, 969, 600, 823, 58, 236, 378, 489, 222, 269, 382, 745, 984, 278, 530, 994, 493, 182, 681, 822, 664, 241, 126, 502, 167, 546, 710, 956, 647, 454, 776, 525, 46, 537, 550, 374, 497, 787, 577, 540, 538, 552, 187, 862, 392, 266, 269, 885, 563, 430, 13, 853, 936, 566, 366, 236, 962, 877, 15, 812, 231, 929, 123, 484, 331, 237, 310, 835, 643, 55, 85, 345, 341, 86, 742, 852, 309, 489, 414, 295, 288, 464, 513, 573, 322, 785, 697, 988, 425, 376, 677, 56, 833, 482, 61, 611, 701, 709, 420, 682, 74, 690, 800, 962, 828, 722, 194, 524, 692, 516, 576, 854, 942, 682, 265, 710, 826, 648, 769, 843, 424, 387, 91, 256, 352, 378, 649, 660, 479, 208, 75, 570, 394, 372, 736, 701, 464, 430, 704, 395, 425, 377, 724, 349, 204, 281, 317, 711, 337, 953, 599, 615, 93, 395, 926, 78, 447, 649, 893, 928, 63, 763, 978, 920, 426, 370, 524, 312, 820, 885, 667, 298, 18, 170, 657, 698, 483, 532, 891, 486, 263, 480, 648, 898, 923, 288, 51, 786, 733, 782, 116, 471, 440, 703, 600, 983, 479, 19, 983, 145, 88, 781, 899, 565, 258, 862, 374, 4, 634, 560, 691, 875, 735, 622, 646, 291, 782, 562, 249, 640, 263, 62, 638, 510, 237, 653, 990, 926, 805, 717, 32, 513, 502, 217, 273, 905, 266, 554, 922, 950, 538, 322, 347, 230, 687, 359, 452, 360, 211, 755, 44, 898, 611, 431, 610, 450, 526, 771, 933, 179, 132, 326, 884, 966, 870, 957, 523, 381, 917, 368, 845, 714, 588, 357, 230, 436, 924, 865, 341, 139, 239, 971, 433, 452, 794, 737, 814, 368, 655, 442, 870, 691, 564, 384, 480, 235, 322, 485, 867, 404, 597, 955, 83, 432, 352, 183, 45, 486, 210, 270, 264, 213, 722, 283, 582, 1, 521, 804, 846, 261, 540, 494, 260, 168, 758, 873, 543, 409, 313, 397, 386, 730, 692, 420, 299, 26, 489, 838, 278, 415, 376, 896, 416, 936, 569, 945, 485, 672, 969, 997, 929, 981, 582, 59, 534, 547]
[1, 2, 3, 3, 4, 5, 8, 9, 13, 13, 14, 15, 15, 16, 18, 19, 20, 21, 23, 23, 26, 26, 26, 26, 26, 31, 31, 31, 32, 32, 33, 35, 37, 41, 42, 43, 44, 45, 45, 46, 47, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 58, 59, 59, 61, 61, 62, 63, 63, 70, 71, 74, 74, 75, 75, 78, 80, 81, 81, 82, 83, 85, 85, 85, 86, 88, 88, 91, 92, 93, 94, 94, 97, 98, 99, 100, 106, 106, 106, 106, 107, 109, 111, 112, 113, 115, 116, 116, 116, 116, 119, 122, 122, 123, 125, 126, 126, 128, 128, 129, 129, 130, 130, 132, 132, 133, 134, 134, 136, 137, 137, 139, 139, 140, 140, 142, 145, 147, 152, 153, 154, 155, 156, 162, 163, 164, 167, 168, 168, 168, 168, 170, 171, 172, 173, 173, 174, 174, 174, 174, 176, 176, 179, 181, 182, 183, 183, 183, 187, 188, 189, 194, 194, 195, 195, 199, 200, 201, 201, 202, 202, 204, 204, 204, 207, 207, 208, 209, 210, 211, 211, 213, 213, 214, 217, 217, 220, 222, 225, 226, 229, 229, 229, 230, 230, 231, 231, 232, 232, 235, 235, 235, 236, 236, 236, 237, 237, 237, 239, 240, 241, 241, 242, 243, 243, 245, 245, 246, 246, 246, 247, 248, 249, 252, 256, 256, 258, 260, 261, 261, 263, 263, 264, 265, 266, 266, 266, 269, 269, 270, 271, 271, 271, 271, 273, 275, 277, 278, 278, 278, 279, 280, 281, 281, 283, 285, 285, 285, 288, 288, 291, 292, 292, 295, 295, 296, 298, 299, 301, 302, 302, 303, 305, 305, 305, 309, 309, 310, 310, 310, 311, 311, 311, 312, 313, 313, 313, 314, 316, 316, 317, 319, 320, 321, 322, 322, 322, 322, 323, 323, 326, 328, 330, 331, 332, 334, 335, 337, 337, 338, 339, 341, 341, 345, 345, 347, 347, 348, 349, 350, 352, 352, 353, 353, 353, 357, 357, 358, 359, 359, 360, 360, 362, 366, 368, 368, 368, 368, 370, 370, 370, 371, 372, 372, 372, 373, 373, 374, 374, 375, 375, 376, 376, 377, 378, 378, 379, 381, 381, 382, 382, 382, 383, 383, 384, 384, 386, 386, 387, 392, 393, 394, 394, 395, 395, 395, 397, 397, 399, 399, 400, 403, 404, 405, 406, 408, 409, 411, 412, 414, 415, 415, 416, 419, 420, 420, 423, 423, 424, 424, 425, 425, 425, 425, 426, 426, 426, 427, 428, 430, 430, 431, 432, 432, 432, 433, 436, 436, 438, 439, 440, 440, 441, 441, 442, 443, 447, 450, 452, 452, 454, 457, 458, 462, 462, 464, 464, 467, 470, 470, 471, 472, 472, 475, 476, 478, 479, 479, 479, 479, 480, 480, 481, 482, 483, 483, 483, 484, 485, 485, 486, 486, 486, 486, 486, 487, 489, 489, 489, 491, 493, 494, 496, 496, 497, 498, 499, 502, 502, 502, 505, 506, 509, 509, 510, 510, 511, 513, 513, 516, 518, 521, 522, 523, 524, 524, 525, 525, 526, 526, 526, 526, 527, 527, 530, 530, 531, 531, 532, 534, 534, 534, 536, 537, 538, 538, 538, 539, 540, 540, 540, 541, 542, 542, 543, 545, 546, 546, 546, 546, 547, 550, 550, 552, 552, 553, 553, 553, 554, 554, 555, 555, 556, 556, 556, 557, 560, 562, 563, 563, 564, 565, 566, 569, 569, 570, 572, 573, 575, 576, 577, 578, 579, 582, 582, 582, 588, 588, 589, 590, 595, 595, 596, 597, 597, 598, 599, 600, 600, 600, 601, 601, 602, 604, 604, 604, 604, 608, 609, 610, 611, 611, 611, 611, 612, 614, 615, 619, 620, 620, 621, 621, 622, 622, 623, 623, 627, 627, 628, 629, 631, 633, 634, 636, 636, 637, 638, 640, 640, 641, 642, 642, 643, 643, 643, 646, 646, 647, 647, 648, 648, 648, 648, 649, 649, 649, 649, 651, 652, 653, 654, 655, 655, 655, 656, 657, 659, 659, 660, 661, 661, 664, 665, 667, 668, 669, 669, 671, 671, 671, 672, 675, 676, 677, 677, 679, 679, 680, 681, 681, 682, 682, 682, 684, 686, 686, 687, 687, 689, 690, 690, 691, 691, 692, 692, 693, 694, 694, 696, 697, 698, 698, 699, 701, 701, 703, 704, 704, 706, 707, 708, 709, 710, 710, 710, 711, 711, 712, 713, 714, 715, 715, 717, 719, 720, 721, 722, 722, 722, 723, 724, 726, 727, 729, 729, 730, 730, 730, 731, 731, 732, 733, 734, 735, 735, 735, 736, 736, 737, 737, 742, 742, 743, 743, 745, 745, 753, 753, 755, 756, 756, 756, 757, 757, 758, 758, 760, 763, 763, 763, 764, 766, 766, 768, 768, 769, 770, 770, 771, 771, 773, 775, 776, 776, 776, 778, 781, 782, 782, 782, 784, 785, 785, 786, 787, 788, 794, 794, 795, 796, 800, 800, 804, 805, 806, 807, 809, 811, 811, 812, 812, 814, 815, 816, 818, 819, 820, 820, 822, 823, 824, 825, 826, 828, 828, 831, 832, 833, 833, 833, 835, 835, 838, 838, 839, 839, 839, 840, 840, 841, 843, 845, 846, 846, 849, 850, 851, 852, 852, 852, 853, 854, 854, 858, 859, 859, 861, 861, 862, 862, 863, 864, 865, 867, 868, 869, 870, 870, 870, 871, 873, 873, 873, 875, 877, 877, 879, 879, 881, 882, 884, 884, 884, 885, 885, 885, 886, 887, 887, 888, 890, 891, 891, 892, 893, 893, 893, 894, 894, 895, 896, 896, 896, 897, 897, 898, 898, 899, 899, 899, 901, 901, 901, 902, 902, 902, 903, 903, 904, 905, 905, 907, 909, 909, 910, 912, 914, 916, 917, 919, 920, 920, 921, 922, 922, 923, 924, 926, 926, 927, 927, 928, 929, 929, 931, 931, 932, 933, 933, 933, 934, 934, 936, 936, 936, 939, 942, 945, 946, 947, 948, 949, 950, 950, 953, 954, 955, 955, 956, 957, 957, 959, 960, 962, 962, 966, 966, 969, 969, 971, 972, 974, 975, 978, 978, 980, 980, 981, 981, 983, 983, 984, 986, 987, 987, 988, 990, 990, 993, 994, 994, 995, 995, 996, 997, 997, 998, 1000, 1000, 1000]

(1)建堆,建堆是持续调度堆的经过,从len/2处开头调度,一向到第一个节点,此处len是堆瓜月素的个数。建堆的进程是线性的进度,从len/2到0处平昔调用调度堆的进度,相当于o(h1)+o(h2)…+o(hlen/2) 其中h表示节点的深度,len/2代表节点的个数,那是三个求和的历程,结果是线性的O(n)。