`
webdev2014
  • 浏览: 709535 次
文章分类
社区版块
存档分类
最新评论

堆排序(改良的选择排序)

 
阅读更多
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
void createheap(int[]);
void heapsort(int[]);
int main(void)
{
int number[MAX+1] = {-1};
int i, num;
srand(time(NULL));
printf("排序前:");
for(i = 1; i <= MAX; i++)
{
number[i] = rand() % 100;
printf("%d ", number[i]);
}
printf("\n建立堆积树:");
createheap(number);
for(i = 1; i <= MAX; i++)
printf("%d ", number[i]);
printf("\n");
heapsort(number);
printf("\n");
return 0;
}
void createheap(int number[])
{
int i, s, p;
int heap[MAX+1] = {-1};
for(i = 1; i <= MAX; i++)
{
heap[i] = number[i];
s = i;
p = i / 2;
while(s >= 2 && heap[p] > heap[s])
{
SWAP(heap[p], heap[s]);
s = p;
p = s / 2;
}
}
for(i = 1; i <= MAX; i++)
number[i] = heap[i];
}
void heapsort(int number[])
{
int i, m, p, s;
m = MAX;
while(m > 1)
{
SWAP(number[1], number[m]);
m--;
p = 1;
s = 2 * p;
while(s <= m)
{
if(s < m && number[s+1] < number[s])
s++;
if(number[p] <= number[s])
break;
SWAP(number[p], number[s]);
p = s;
s = 2 * p;
}
printf("\n排序中:");
for(i = MAX; i > 0; i--)
printf("%d ", number[i]);
}

}

//测试结果


分享到:
评论

相关推荐

    C经典算法之排序法 - 改良的选择排序

    本篇将探讨一种改良的选择排序方法——堆排序。 #### 选择排序的基本原理 选择排序的基本步骤如下: 1. 从未排序序列中找到最小(大)元素,存放到排序序列的起始位置。 2. 再从剩余未排序元素中继续寻找最小(大)...

    JAVA各种排序方法及改良

    堆排序利用了二叉堆的性质,将待排序的序列构造成一个大顶堆或小顶堆,然后交换堆顶元素与末尾元素,缩小排序范围,重复此过程直到所有元素排序完毕。Java中,可以利用优先队列(PriorityQueue)实现堆排序。 7. **...

    Java-各种排序算法

    这里我们将深入探讨几种常见的Java排序算法,包括冒泡排序、堆排序、插入排序、合并排序、快速排序以及选择排序和希尔排序。 1. **冒泡排序**:冒泡排序是最基础的排序算法之一,它通过重复遍历待排序数组,比较...

    JAVA经典算法各种排序算法

    Shaker 排序法 - 改良的氣泡排序 Heap 排序法 - 改良的選擇排序 快速排序法(一) 快速排序法(二) 快速排序法(三) 合併排序法 基數排序法 搜尋 循序搜尋法(使用衛兵) 二分搜尋法(搜尋原則的代表)...

    ifem.zip_Shaker_ifem_ifem编程_择排序_数据结构

    择排序分为直接选择排序和堆排序两种类型。直接选择排序的时间复杂度为O(n^2),效率较低,适用于小规模数据或部分有序的数据。而堆排序通过构建大顶堆或小顶堆,能在平均情况下达到O(n log n)的时间复杂度,更适合...

    java开发经典算法

    Heap 排序法 - 改良的选择排序 快速排序法(一) 快速排序法(二) 快速排序法(三) 合并排序法 基数排序法 循序搜寻法(使用卫兵) 二分搜寻法(搜寻原则的代表) 插补搜寻法 费氏搜寻法 堆叠 - 使用...

    数据结构与算法

    Heap 排序法 - 改良的选择排序 快速排序法(一) 快速排序法(二) 快速排序法(三) 合并排序法 基数排序法 搜寻 循序搜寻法(使用卫兵) 二分搜寻法(搜寻原则的代表) 插补搜寻法 费氏搜寻法 矩阵...

    java各种经典算法

    Heap 排序法 - 改良的选择排序 快速排序法(一) 快速排序法(二) 快速排序法(三) 合并排序法 基数排序法 搜寻 循序搜寻法(使用卫兵) 二分搜寻法(搜寻原则的代表) 插补搜寻法 费氏搜寻法 矩阵...

    经典常用算法 河内塔

    Heap 排序法 - 改良的选择排序 快速排序法(一) 快速排序法(二) 快速排序法(三) 合并排序法 基数排序法 搜寻 循序搜寻法(使用卫兵) 二分搜寻法(搜寻原则的代表) 插补搜寻法 费氏搜寻法 矩阵...

    Java和C语言实现各种经典算法(含代码图例)

    Heap 排序法 - 改良的选择排序 快速排序法(一) 快速排序法(二) 快速排序法(三) 合并排序法 基数排序法 搜寻 循序搜寻法(使用卫兵) 二分搜寻法(搜寻原则的代表) 插补搜寻法 费氏搜寻法 矩阵...

    C语言经典算法大全.pdf

    * heap sort:一种改良的选择排序算法,使用堆排序实现。 * quick sort:一种快速的排序算法,使用分治法实现。 * merge sort:一种改良的排序算法,使用合并法实现。 搜寻 * 顺序搜寻法(Linear Search):一种...

    leetcode跳跃-algorithm:算法

    希尔排序(插入排序改良版) 第三部分(commonquestion) 常见的算法 二进制简单算法 二分查找 树的前序、中序、后续遍历 第四部分 剑指offer的算法题目 第五部分(yxxxx.mxx.dxx) 后续的包打算以年为单位,以yxxxx.mxx...

    ACM经典算法 代码+详解

    Shaker 排序法 - 改良的氣泡排序 Heap 排序法 - 改良的選擇排序 快速排序法(一) 快速排序法(二) 快速排序法(三) 合併排序法 基數排序法 搜尋 循序搜尋法(使用衛兵) 二分搜尋法(搜尋原則的代表)...

    数据结构计算机科学与技术.doc

    10. 堆排序的时间复杂度:在最坏情况下,堆排序的时间复杂度是O(nlogn),对应B选项。 此外,还有关于数据结构如链表、队列、字符串、哈夫曼树、图的遍历、无向图的生成树、折半查找、快速排序以及堆的性质等的判断...

    经典算法(C&JAVA实现)

    Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的氣泡排序 Heap 排序法 - 改良的選擇排序 快速排序法(一) 快速排序法(二) 快速排序法(三) 合併排序法 基數排序法 循序搜尋法(使用衛兵) 二分...

    易语言文本快速排序源码-易语言

    易语言是一种专为中国人设计的编程语言,它以简体中文作为编程语句,降低了编程的门槛,使得更多的人能够接触并学习...同时,掌握快速排序也有助于理解和实现其他高级算法,如归并排序、堆排序等,进一步提升编程技能。

    改良版数据结构1800题含答案

    - 选择排序是另一种简单的排序算法,它的基本思想是每一趟从待排序的数据元素中选出最小(或最大)的一个元素,与前面的位置交换。 - 快速排序是一种高效的排序算法,它采用分治法的策略来把一个序列分为较小和较大...

    C和JAVA经典算法.rar

    Shaker 排序法 - 改良的氣泡排序 Heap 排序法 - 改良的選擇排序 快速排序法(一) 快速排序法(二) 快速排序法(三) 合併排序法 基數排序法 搜尋 循序搜尋法(使用衛兵) 二分搜尋法(搜尋原則的代表)...

    算法设计及分析期末总复习.doc

    3. **堆排序**:自底向上的构建过程,将列表转换为最大堆,然后交换堆顶元素以达到排序目的。 4. **Horspool算法**:在文本中查找模式,通过滑动窗口和预处理表提高字符串匹配效率。 这些知识点涵盖了算法设计与...

    软件开发实习日记.pdf

    在 Daily Work 2 中,实习生描述了自己对昨天的实例进行了改良和进步,将堆排序和冒泡排序封装在一个动态链接库中,并应用 XML 进行设置装备摆设。实习生也提到自己对 XML 的理解和应用。 在 Daily Work 3 中,实习...

Global site tag (gtag.js) - Google Analytics