注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ksnowlv的博客

积土成丘,集腋成裘,坚持再坚持!

 
 
 

日志

 
 

堆排序+  

2013-09-04 20:35:01|  分类: 算法与数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

//

//  HeapSort.h

//  HeapSortTest

//

//  Created by lv wei on 13-9-4.

//  Copyright (c) 2013 lv wei. All rights reserved.

//


#ifndef __HeapSortTest__HeapSort__

#define __HeapSortTest__HeapSort__


#include <iostream>


using namespace std;


void Swap(int* p, int* q);

void ShowArray(const int* pArray,const int aLength);


void MinHeapAdjust(int pArray[], int i, int length);


void MaxHeapAdjust(int pArray[], int i, int length);


// 堆排序算法

void MinHeapSort(int array[],int length);

void MaxHeapSort(int array[],int length);



#endif /* defined(__HeapSortTest__HeapSort__) */


//

//  HeapSort.cpp

//  HeapSortTest

//

//  Created by lv wei on 13-9-4.

//  Copyright (c) 2013 lv wei. All rights reserved.

//


#include "HeapSort.h"



void Swap(int* p, int* q)

{

    int temp = *p;

    *p = *q;

    *q = temp;

}


void ShowArray(const int* pArray,const int aLength)

{

    for (int i = 0; i < aLength;++i)

    {

        cout<<pArray[i]<<"->";

    }

    cout<<endl;

}


void MinHeapAdjust(int pArray[], int i, int length)

{

    int temp = pArray[i];

    int child = 2*i + 1;

    

    while(child < length )

    {

        if (child + 1 < length && pArray[child] < pArray[child + 1])

        {

            ++child;

        }

        

        if (temp >= pArray[child])

        {

            break;

        }

        else

        {

            

            pArray[i] = pArray[child];

            i = child;

            child = 2 * i + 1;

        }

    }

    

    pArray[i] = temp;

}


void MaxHeapAdjust(int pArray[], int i, int length)

{

    int temp = pArray[i];

    int child = 2*i + 1;

    

    while(child < length )

    {

        if (child + 1 < length && pArray[child] > pArray[child + 1])

        {

            ++child;

        }

        

        if (temp < pArray[child])

        {

            break;

        }

        else

        {

            

            pArray[i] = pArray[child];

            i = child;

            child = 2 * i + 1;

        }

    }

    

    pArray[i] = temp;

}



// 堆排序算法

void MinHeapSort(int array[],int length)

{

    ShowArray(array, length);

    // 调整序列的前半部分元素,调整完之后第一个元素是序列的最大的元素

    //length/2-1是第一个非叶节点,此处"/"为整除.

    //创建堆,初始化堆

    cout<<"init min heap"<<endl;

    for (int i = length/2  - 1; i >= 0; --i)

    {

        MinHeapAdjust(array, i, length);

        ShowArray(array, length);

    }

    

     cout<<"adjust min heap"<<endl;

    //调整堆

    // 从最后一个元素开始对序列进行调整,不断的缩小调整的范围直到第一个元素

    for (int i = length - 1; i > 0; --i)

    {

        // 把第一个元素和当前的最后一个元素交换,

        // 保证当前的最后一个位置的元素都是在现在的这个序列之中最大的

        Swap(&array[0], &array[i]);

        // 不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值

        MinHeapAdjust(array, 0, i-1);

        ShowArray(array, length);

    }

}


// 堆排序算法

void MaxHeapSort(int array[],int length)

{

    ShowArray(array, length);

    // 调整序列的前半部分元素,调整完之后第一个元素是序列的最大的元素

    //length/2-1是第一个非叶节点,此处"/"为整除.

    //创建堆,初始化堆

    cout<<"init max heap"<<endl;

    for (int i = length/2  - 1; i >= 0; --i)

    {

        MaxHeapAdjust(array, i, length);

        ShowArray(array, length);

    }

    

    cout<<"adjust max heap"<<endl;

    //调整堆

    // 从最后一个元素开始对序列进行调整,不断的缩小调整的范围直到第一个元素

    for (int i = length - 1; i > 0; --i)

    {

        // 把第一个元素和当前的最后一个元素交换,

        // 保证当前的最后一个位置的元素都是在现在的这个序列之中最大的

        Swap(&array[0], &array[i]);

        // 不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值

        MaxHeapAdjust(array, 0, i-1);

        ShowArray(array, length);

    }

}



调用代码如下:

//

//  HeapSortTestViewController.m

//  HeapSortTest

//

//  Created by lv wei on 13-9-4.

//  Copyright (c) 2013 lv wei. All rights reserved.

//


#import "HeapSortTestViewController.h"

#include "HeapSort.h"


@interface HeapSortTestViewController ()


@end


@implementation HeapSortTestViewController


- (void)viewDidLoad

{

    [super viewDidLoad];

// Do any additional setup after loading the view, typically from a nib.

    [self testHeapSort];

}


- (void)didReceiveMemoryWarning

{

    [super didReceiveMemoryWarning];

    // Dispose of any resources that can be recreated.

}


- (void)testHeapSort

{

    const int KHeapSize = 13;

    int array[KHeapSize] = {19, 1, 10, 14, 16, 4, 7, 9, 3, 2, 8, 5, 11};

    int* resArray = new int[KHeapSize];

    

    for (int i = 0; i < KHeapSize; ++i) {

        resArray[i] = array[i];

    }

  

    cout<<"min heap sort "<<endl;

    

    MinHeapSort(resArray, KHeapSize);

    cout<<"max heap sort res"<<endl;

    ShowArray(resArray,KHeapSize);


    cout<<"max heap sort"<<endl;

    for (int i = 0; i < KHeapSize; ++i) {

        resArray[i] = array[i];

    }

    

    MaxHeapSort(resArray, KHeapSize);

    cout<<"max heap sort res"<<endl;

    ShowArray(resArray,KHeapSize);

    

    delete []resArray;

}


@end



日志输出如下:

min heap sort 

19->1->10->14->16->4->7->9->3->2->8->5->11->

init min heap

19->1->10->14->16->11->7->9->3->2->8->5->4->

19->1->10->14->16->11->7->9->3->2->8->5->4->

19->1->10->14->16->11->7->9->3->2->8->5->4->

19->1->11->14->16->10->7->9->3->2->8->5->4->

19->16->11->14->8->10->7->9->3->2->1->5->4->

19->16->11->14->8->10->7->9->3->2->1->5->4->

adjust min heap

16->14->11->9->8->10->7->4->3->2->1->5->19->

14->9->11->5->8->10->7->4->3->2->1->16->19->

11->9->10->5->8->1->7->4->3->2->14->16->19->

10->9->7->5->8->1->2->4->3->11->14->16->19->

9->8->7->5->3->1->2->4->10->11->14->16->19->

8->5->7->4->3->1->2->9->10->11->14->16->19->

7->5->2->4->3->1->8->9->10->11->14->16->19->

5->4->2->1->3->7->8->9->10->11->14->16->19->

4->3->2->1->5->7->8->9->10->11->14->16->19->

3->1->2->4->5->7->8->9->10->11->14->16->19->

2->1->3->4->5->7->8->9->10->11->14->16->19->

1->2->3->4->5->7->8->9->10->11->14->16->19->

max heap sort res

1->2->3->4->5->7->8->9->10->11->14->16->19->

max heap sort

19->1->10->14->16->4->7->9->3->2->8->5->11->

init max heap

19->1->10->14->16->4->7->9->3->2->8->5->11->

19->1->10->14->2->4->7->9->3->16->8->5->11->

19->1->10->3->2->4->7->9->14->16->8->5->11->

19->1->4->3->2->5->7->9->14->16->8->10->11->

19->1->4->3->2->5->7->9->14->16->8->10->11->

1->2->4->3->8->5->7->9->14->16->19->10->11->

adjust max heap

2->3->4->9->8->5->7->11->14->16->19->10->1->

3->8->4->9->10->5->7->11->14->16->19->2->1->

4->8->5->9->10->19->7->11->14->16->3->2->1->

5->8->7->9->10->19->16->11->14->4->3->2->1->

7->8->14->9->10->19->16->11->5->4->3->2->1->

8->9->14->11->10->19->16->7->5->4->3->2->1->

9->10->14->11->16->19->8->7->5->4->3->2->1->

10->11->14->19->16->9->8->7->5->4->3->2->1->

11->16->14->19->10->9->8->7->5->4->3->2->1->

16->19->14->11->10->9->8->7->5->4->3->2->1->

14->19->16->11->10->9->8->7->5->4->3->2->1->

19->14->16->11->10->9->8->7->5->4->3->2->1->

max heap sort res

19->14->16->11->10->9->8->7->5->4->3->2->1->



  评论这张
 
阅读(207)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018