认知算法(七)

简介: 认知算法(七),一起来学习吧。

嗨,欢迎来到异星球,我是小怪同志。这篇文章主要讲认识算法,请一起学习吧。

一、堆排序

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

1.大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;
2.小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列;
堆排序的平均时间复杂度为 Ο(nlogn)。

  1. 算法步骤
    1.创建一个堆 H[0……n-1];

    2.把堆首(最大值)和堆尾互换;

    3.把堆的尺寸缩小 1,并调用 shift_down(0),目的是把新的数组顶端数据调整到相应位置;

    4.重复步骤 2,直到堆的尺寸为 1。

二、代码实现

include <stdio.h>

include <stdlib.h>

void swap(int a, int b) {

int temp = *b;
*b = *a;
*a = temp;

}

void max_heapify(int arr[], int start, int end) {

// 建立父節點指標和子節點指標
int dad = start;
int son = dad * 2 + 1;
while (son <= end) { // 若子節點指標在範圍內才做比較
    if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小,選擇最大的
        son++;
    if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢,直接跳出函數
        return;
    else { // 否則交換父子內容再繼續子節點和孫節點比較
        swap(&arr[dad], &arr[son]);
        dad = son;
        son = dad * 2 + 1;
    }
}

}

void heap_sort(int arr[], int len) {

int i;
// 初始化,i從最後一個父節點開始調整
for (i = len / 2 - 1; i >= 0; i--)
    max_heapify(arr, i, len - 1);
// 先將第一個元素和已排好元素前一位做交換,再重新調整,直到排序完畢
for (i = len - 1; i > 0; i--) {
    swap(&arr[0], &arr[i]);
    max_heapify(arr, 0, i - 1);
}

}

int main() {

int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr, len);
int i;
for (i = 0; i < len; i++)
    printf("%d ", arr[i]);
printf("\n");
return 0;

}

相关文章
|
6月前
|
安全 测试技术
认识-认知
认识-认知
101 0
|
Kubernetes 负载均衡 网络协议
K8S 的新认知与初领会
我们今天开始正式进⼊ Kubernetes 的课程学习,Kubernetes 相信各位已经听过很多次了,那么什么是 Kubernetes呢?
K8S 的新认知与初领会
|
存储 算法 搜索推荐
认知算法(三)
认知算法(三),一起来学习吧。
认知算法(三)
|
机器学习/深度学习 存储 算法
认知算法(四)
认知算法(四),一起来学习吧。
|
存储 算法 搜索推荐
认知算法(六)
认知算法(六),一起来学习吧。
认知算法(二)
认知算法(二),一起来学习吧。
|
算法 JavaScript 前端开发
认知算法(九)
认知算法(九),一起来学习吧。
|
算法 搜索推荐 大数据
认知算法(八)
认知算法(八),一起来学习吧。
|
算法 搜索推荐
认知算法(十)
认知算法(十),一起来学习吧。
|
机器学习/深度学习 算法 搜索推荐
认知算法(一)
认识算法(一),一起来学习吧。