堆排序

构建堆的时间复杂度为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 条评论
登录 后参与评论

相关文章

  • 直接插入排序

    时间复杂度: 如果排序的数组是正序的,那么时间复杂度相当于O(n), 而如果排序是随机的,时间复杂度相当于O(n^2/4). 倒置的时间复杂度是最高的,O(n^...

    用户1154259
  • 简单选择排序

    选择排序时间复杂度也为O(n^2) 算法思想: 选择排序即每次length-i的长度内选择一个最小的元素,与第一个进行替换,这样大循环length次后,就可以得...

    用户1154259
  • 冒泡排序

    冒泡排序时间复杂度上为O(n^2) 冒泡排序三种方式,第一种也是最基本的排序: void bubbleSort1(int *arr,int length){ ...

    用户1154259
  • 直接插入排序

    时间复杂度: 如果排序的数组是正序的,那么时间复杂度相当于O(n), 而如果排序是随机的,时间复杂度相当于O(n^2/4). 倒置的时间复杂度是最高的,O(n^...

    用户1154259
  • 简单选择排序

    选择排序时间复杂度也为O(n^2) 算法思想: 选择排序即每次length-i的长度内选择一个最小的元素,与第一个进行替换,这样大循环length次后,就可以得...

    用户1154259
  • C++函数退化修复

    编译器会视为:int getLen(int*),发生退化,导致产生的结果是2(64位操作系统结果),原因是退化之后取的是指针 8字节除以int 4字节,得到2,...

    公众号guangcity
  • 最大连续子数组

    题目: 给定一个数组 A[0,1..... ,n-1],求A的连续子数组,使得该子数组的和最大。

    梅花
  • 算法回顾--如何写递归?

    总之递归就是”装傻”的把原始的思路表现出来,不需要关心具体过程,只需要不停的缩小问题规模,然后答案自然就会被计算出来.

    屈定
  • 聊聊「插入排序」的正确姿势

    面试官最爱考察的是一个被试者对知识掌握的灵活程度和熟练程度,当一道题目可以同时考察到被试者多个知识点的掌握程度和思考能力时,面试官最爱这样的题目,而且对于插入排...

    五分钟学算法
  • 快速排序

    快速排序时间复杂度为O(nlogn),由于是在原数组上面利用替换来实现,因此不需要额外的存储空间。 算法思想:   通过设置一个岗哨,每次跟这个岗哨进行比较,比...

    用户1154259

扫码关注云+社区

领取腾讯云代金券