堆排序

构建堆的时间复杂度为O(n),而第I次调整堆的时间复杂度为O(logi),因此,无论什么情况下时间复杂度都为O(nlogn)

算法思想:

  首先,对数组从n/2处开始进行创建堆。大顶堆就是顶点总是大于它的子节点,而小顶堆就是定点总是小于它的子节点。

  因此,构建时,对节点与他的孩子进行比较,如果创建的是大顶堆,那么就把最大的孩子跟自己进行比较,比自己大,就进行替换。依次类推。

  最后把最顶点的与最后一个元素进行替换,在进行堆的调整,此时的调整,相当于调整最顶点的元素。

主要代码:

void heapSort(int *arr,int length){
    int i;
    for(i=length/2; i>0; i--){
        sort(arr,i,length);
    }

    for(i=length; i>0; i--){
        int k = arr[0];
        arr[0] = arr[i-1];
        arr[i-1] = k;
        sort(arr,1,i-1);
    }

}
void sort(int *arr,int s,int length){
    int temp,i;
    temp = arr[s-1];
    for(i=2*s; i<=length; i*=2    ){
        if(i<length && arr[i-1] < arr[i])
            i++;
        if(temp >= arr[i-1])
            break;
        arr[s-1] = arr[i-1];
        s = i;
    }
    arr[s-1] = temp;
}

全部代码:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int arrtest1[10] = {3,4,7,8,0,9,1,2,6,5};
int arrtest2[10] = {0,1,2,3,4,5,6,7,8,9};
int arrtest3[10] = {9,8,7,6,5,4,3,2,1,0};
void copy(int *from,int *arr,int length);
void print(int *arr,int length);
void heapSort(int *arr,int length);
void sort(int *arr,int s,int length);
int main(){
    clock_t start,end;
    int Arr[10];
    int i;
    copy(arrtest1,Arr,10);
    print(Arr,10);
    heapSort(Arr,10);
    print(Arr,10);
    start = clock();
    for(i=0;i<100000;i++){
        copy(arrtest1,Arr,10);
        //print(Arr,10);
        heapSort(Arr,10);
        //print(Arr,10);
    }
    end = clock();
    printf("first test:%d\n",end-start);

    start = clock();
    for(i=0;i<100000;i++){
        copy(arrtest2,Arr,10);
        //print(Arr,10);
        heapSort(Arr,10);
        //print(Arr,10);
    }
    end = clock();
    printf("first test:%d\n",end-start);

    start = clock();
    for(i=0;i<100000;i++){
        copy(arrtest3,Arr,10);
        //print(Arr,10);
        heapSort(Arr,10);
        //print(Arr,10);
    }
    end = clock();
    printf("first test:%d\n",end-start);
    
    getchar();
    return 0;
}
void heapSort(int *arr,int length){
    int i;
    for(i=length/2; i>0; i--){
        sort(arr,i,length);
    }

    for(i=length; i>0; i--){
        int k = arr[0];
        arr[0] = arr[i-1];
        arr[i-1] = k;
        sort(arr,1,i-1);
    }

}
void sort(int *arr,int s,int length){
    int temp,i;
    temp = arr[s-1];
    for(i=2*s; i<=length; i*=2    ){
        if(i<length && arr[i-1] < arr[i])
            i++;
        if(temp >= arr[i-1])
            break;
        arr[s-1] = arr[i-1];
        s = i;
    }
    arr[s-1] = temp;
}
void copy(int *from,int *arr,int length){
    int i;
    for(i=0;i<length;i++){
        arr[i] = from[i];
    }
}

void print(int *arr,int length){
    int i;
    for(i=0;i<length;i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
}

运行示例:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python爬虫与算法进阶

Python中萌新不知道的小魔法(一)

萌新重新撸一遍基础,看看有哪些已经忘了的,顺便留下记录。 01 三引号 使用三重引号-("""或''')指定多行字符串。在三重引号中可以自由使用单引号和双...

29750
来自专栏HT

玩转 HTML5 下 WebGL 的 3D 模型交并补

建设性的立体几何具有许多实际用途,它用于需要简单几何对象的情况下,或者数学精度很重要的地方,几乎所有的工程 CAD 软件包都使用 CSG(可以用于表示刀具切削,...

237100
来自专栏hightopo

玩转 HTML5 下 WebGL 的 3D 模型交并补

12910
来自专栏云霄雨霁

设计模式----迭代器模式

19300
来自专栏Fundebug

每个JavaScript工程师都应懂的33个概念

这个项目是为了帮助开发者掌握 JavaScript 概念而创立的。它不是必备,但在未来学习(JavaScript)中,可以作为一篇指南。

34060
来自专栏光变

Java编程风格

Java编程的风格介绍,主要参考乐google的java code style。对模糊部分作出了明确的选择。

22720
来自专栏cs

javascript基础知识点1.0

知识点综述: ---- 在复习JavaScript语法,主要看的是w3cschool的教程。 用法: 1.0必须位于<script></s...

361130
来自专栏JackieZheng

初探JavaScript(一)——也谈元素节点、属性节点、文本节点

  Javascript大行其道的时候,怎么能少了我来凑凑热闹^_^   基本上自己对于js的知识储备很少,先前有用过JQuery实现一些简单功能,要论起JS的...

26270
来自专栏python3

习题10:那是什么?

    I'm tabbed in. I'm split on a line. I'm \ a \ cat. I'll do a list:     * Ca...

7110
来自专栏灯塔大数据

技术 | Python从零开始系列连载(二)

上一期学的upyter相信大家都已经会用了,我们这一期就可以愉快地学习写代码啦! Python的基本数据类型 数据类型在数据结构中的定义是一个值的集合以及定义在...

38260

扫码关注云+社区

领取腾讯云代金券