首页 / 算法 / 八大经典算法之选择算法、堆算法

八大经典算法之选择算法、堆算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了八大经典算法之选择算法、堆算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1155字，纯文字阅读大概需要2分钟。

内容图文

05 选择排序 （Selection Sort）

原理：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。

            void selection_sort(int arr[], int n) {
    for (int i = 0;i < n - 1;i++) {
        int temp = a[i];
        int t = i;
        for (int j = i + 1;j < n;j++) {
            if (a[j] < temp) {
                temp = a[j];
                t = j;
            }    
        }
        a[t] = a[i];
        a[i] = temp;
    }
}

空间效率：O(1)

时间效率：最好情况：O(N)             平均情况：O(N^2)                       最坏情况：O(N^2)

稳定性（相同元素相对位置变化情况）：不稳定

比较次数与初始状态无关

06 堆排序（Heap Sort）

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

            void heap_sort(int arr[], int n) {
    int i,temp;
    for (i = (n - 2) / 2; i >= 0; i--)
        percdown(arr, n, i);
    for (i = n - 1;i > 0;i--) {
        temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        percdown(arr, i, 0);
    }
}
 
void percdown(int arr[], int n, int i) {
    int child;
    int x = arr[i];
    for (;i * 2 + 1 <= n - 1;i = child) {
        child = i * 2 + 1;
        if (child < n - 1 && arr[child + 1] > arr[child])
            child++;
        if (x >= arr[child]) break;
        else arr[i] = arr[child];
    }
    arr[i] = x;
}

空间效率：O(1)

时间效率：最好情况：O(Nlog2N)                平均情况：O(Nlog2N)                        最坏情况：O(Nlog2N)   

稳定性（相同元素相对位置变化情况）：不稳定

原文：https://www.cnblogs.com/wanghao-boke/p/10424339.html

内容总结

以上是互联网集市为您收集整理的八大经典算法之选择算法、堆算法全部内容，希望文章能够帮你解决八大经典算法之选择算法、堆算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1117582.html

来源：【匿名】