`

基于数组实现的就地堆排序

阅读更多

思想最重要,结合图形来分析就简单了:

实现的是小顶堆排序算法,大堆思路差不多:

java代码:

package org.forever.music.dao;

/** 就地堆排序 */
public class HeapSort {
	public int size;// 记录规模

	// 构造方法
	public HeapSort() {
		size = 0;
	}

	// 建堆方法,只需线性时间建好
	public void buildHeap(int[] num) {
		size = num.length;// 获取堆的规模
		for (int i = num.length / 2 - 1; i >= 0; i--) {// 对前一半的节点,
			percolateDown(num, i);// 进行下滤操作
		}
	}

	// 给定数组交换两个数的位置
	public void swap(int[] num, int v, int u) {
		int temp = num[v];
		num[v] = num[u];
		num[u] = temp;
	}

	// 对该数进行上滤操作,直到该数比父节点大就停止上滤
	public void percolateUp(int[] num, int index) {
		while (index != 0) {// 只要下标不为0
			int parent = (index - 1) / 2;// 获取该数的父节点
			if (num[index] < num[parent]) {// 和父节点进行比较
				swap(num, index, parent);// 如果比父节点小,就交换两个的位置
				index = parent;// 更新index的指向
			}
		}
	}

	/******************************* 排序用的方法 ************************************/

	public int getSize() {
		return size;
	}

	// 判断该数是否有左节点
	public boolean hasLChildTwo(int index) {
		return index * 2 + 1 < size ? true : false;
	}

	// 判断该数是否有右节点
	public boolean hasRChildTwo(int index) {
		return index * 2 + 2 < size ? true : false;
	}

	// 对该数进行下滤操作,直到该数比左右节点都小就停止下滤
	public void percolateDown(int[] num, int index) {
		int min;// 设置最小指向下标
		while (hasLChildTwo(index)) {// 如果该数有左节点,则假设左节点最小
			min = index * 2 + 1;// 获取左节点的下标
			if (hasRChildTwo(index)) {// 如果该数还有右节点
				if (num[min] > num[index * 2 + 2]) {// 就和左节点分出最小者
					min = index * 2 + 2;// 此时右节点更小,则更新min的指向下标
				}
			}
			// 此时进行该数和最小者进行比较,
			if (num[index] < num[min]) {// 如果index最小,
				break;// 停止下滤操作
			} else {
				swap(num, index, min);// 交换两个数,让大数往下沉
				index = min;// 更新index的指向
			}
		}// while
	}

	/*********************************************************************/
	public static void main(String[] args) {
		int[] num = { 6, 4, 1, 2, 8, 4, 7, 3, 0, 9 };
		HeapSort heap = new HeapSort();
		heap.buildHeap(num);// 建立小顶堆
		for (int i = 0; i < num.length; i++) {
			System.out.print(num[i] + " ");
		}
		System.out.println();
		for (int i = num.length - 1; i >= 1; i--) {
			heap.swap(num, 0, i);// 交换
			heap.size--;// 每交换一次让规模减少一次
			heap.percolateDown(num, 0);// 将新的首元素下滤操作
		}
		for (int i = 0; i < num.length; i++) {
			System.out.print(num[i] + " ");
		}

	}
}

 

下面是例子的图形分析:

图1:

 



 图2:



 图3:



 

  • 大小: 29.3 KB
  • 大小: 24.7 KB
  • 大小: 43.7 KB
分享到:
评论
2 楼 AbstractForever 2010-08-14  
用的是一些基本语法来写的,替换语言很容易。呵呵
1 楼 uu_ovo 2010-08-13  
将楼主的程序改为C语言版的,在Dev C++下调试通过,函数percolateUp用不到所以就去掉了,代码如下:
#include <stdio.h>
#include <stdlib.h>

void HeapSort(int num[],int size);
void BuildHeap(int num[] ,int size);
void PercolateDown(int num[] , int index,int size);
void PrintHeap(const char* strMsg,int array[],int nLength); 
void Swap(int num[] , int v, int u);

int main(int argc, char *argv[])
{
  int data[13]={8,5,4,6,13,7,1,9,12,11,3,10,2};
  HeapSort(data,13);
  
  system("PAUSE");	
  return 0;
}


void HeapSort(int num[] ,int size)
{
    int i;
    int iLength=size;
    
    PrintHeap("Befor Sort:",num,iLength);
    
    BuildHeap(num,size);// 建立小顶堆   
    
    for (i = iLength - 1; i >= 1; i--) {   
        Swap(num, 0, i);// 交换   
        size--;// 每交换一次让规模减少一次   
        PercolateDown(num, 0,size);// 将新的首元素下滤操作 
        PrintHeap("Sort Heap:",num,iLength);  
    }
}

// 建堆方法,只需线性时间建好   
void BuildHeap(int num[] ,int size) { 
    int i; 
    for (i = size / 2 - 1; i >= 0; i--) {// 对前一半的节点(解释为“从最后一个非叶子节点开始,将每个父节点都调整为最小堆”更合理一些)   
        PercolateDown(num, i,size);// 进行下滤操作
        PrintHeap("Build heap:",num,size);
    }   
}
    
// 对该数进行下滤操作,直到该数比左右节点都小就停止下滤   
void PercolateDown(int num[] , int index,int size) {   
    int min;// 设置最小指向下标   
    while (index * 2 + 1<size) {// 如果该数有左节点,则假设左节点最小   
        min = index * 2 + 1;// 获取左节点的下标   
        if (index * 2 + 2<size) {// 如果该数还有右节点   
            if (num[min] > num[index * 2 + 2]) {// 就和左节点分出最小者   
                min = index * 2 + 2;// 此时右节点更小,则更新min的指向下标   
            }   
        }   
        // 此时进行该数和最小者进行比较,   
        if (num[index] < num[min]) {// 如果index最小,   
            break;// 停止下滤操作   
        } else {   
            Swap(num, index, min);// 交换两个数,让大数往下沉   
            index = min;// 更新index的指向   
        }   
    }// while   
}
    
// 给定数组交换两个数的位置   
void Swap(int num[] , int v, int u) {  
    int temp = num[v];   
    num[v] = num[u];   
    num[u] = temp;   
}   

void PrintHeap(const char* strMsg,int array[],int nLength)
{
     int i;
     printf("%s",strMsg);
     for(i=0;i<nLength;i++)
     {
        printf("%d ",array[i]);
     }
     printf("\n");
}

相关推荐

    Python实现堆排序的方法详解

    堆排序是一种基于比较的排序技术,利用了特殊的树形数据结构——堆。堆排序可以分为两个阶段:构建最大堆和排序过程。 ##### 1. 堆的概念 - **堆定义**:堆是一种特殊的数据结构,通常以完全二叉树的形式存储。根据...

    十大经典排序算法.pdf

    十大经典排序算法是数据结构与算法领域中的基础,它们包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序和基数排序。这些算法分别适用于不同的场景,具有各自的时间复杂度...

    c语言经典排序算法(8种-含源代码)

    在堆结构的数组A中,堆的根节点为A[1],所以堆排序从A[n/2]开始,将每个非叶子节点进行下沉操作以确保每个子树都是一个合法的堆,然后再将根节点与最后一个元素交换,并排除最后一个元素,重复这个过程直到堆的大小...

    排序算法总结

    堆排序(Heap Sort)是一种基于二叉堆数据结构的排序算法,其思想是利用堆这种数据结构的特点进行排序。在建堆阶段,算法将输入数据构造为一个大顶堆或小顶堆,然后将堆顶元素(即最大或最小的元素)与堆的最后一个...

    C++直接插入排序详解以及代码实现

    需要注意的是,虽然直接插入排序简单且实现容易,但它在处理大规模数据或无序数据时效率较低,不如其他更高效的排序算法如快速排序、归并排序或堆排序。归并排序,作为一种基于分治策略的排序算法,具有稳定的O(n ...

    快速排序C++

    4. 排序算法比较:了解其他排序算法如冒泡排序、插入排序、选择排序、堆排序等,对比它们的效率和适用场景。 5. 静态分析和动态分析:了解如何分析算法的时间复杂度和空间复杂度,理解最好、最坏和平均情况下的性能...

    PB15111604-金泽文-project11

    堆排序和快速排序的实现与教科书中的基本思路相似,但需要根据数组从0开始索引进行微调。归并排序则需要使用特殊的“无穷大”字符串,这里用33个'A'来代替。 实验2则针对整数排序,使用冒泡排序、快速排序、基数...

    数据结构习题及答案与实验指导(排 序)10.pdf

    堆排序在最坏、最好和平均情况下的时间复杂度均为O(n log n),且不需要额外的存储空间,因此是就地排序的一种。 7. **归并排序**采用分治策略,将数组分成两半,分别排序后再合并,确保了O(n log n)的时间复杂度。...

    sorting.js:可视化JavaScript中的排序算法

    更具体地说,我们通过以蓝色突出显示每个比较并以红色突出显示每个交换来可视化基于就地比较的排序算法。 当前,实现了以下排序算法: Quicksort和introsort围绕枢轴值递归划分数组的块; 枢纽的选择可能对算法的...

    200个经典C程序源码小游戏

    047 堆排序 048 归并排序 049 基数排序 050 二叉搜索树操作 051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 ...

    scala-sorts:scala中的排序算法

    7. **堆排序(Heap Sort)**:利用二叉堆结构实现的排序算法。时间复杂度为 O(n log n),空间复杂度为 O(1)。 8. **计数排序(Counting Sort)、桶排序(Bucket Sort)和基数排序(Radix Sort)**:适用于整数排序...

    ACM程序设计常用算法与数据结构参考

    - **堆排序**:堆排序也是一种基于比较的排序算法。堆是一种特殊的完全二叉树结构,可以是最大堆或最小堆。堆排序首先构建一个堆结构,然后不断地将堆顶元素与最后一个元素交换,减少堆的大小,并重新调整堆结构,...

    C++参考pdf(用了才知pdf不适用,不要下)

    - **示例**: 对于已排序的数组 `int arr[] = {1, 2, 3, 4, 5};`,`std::binary_search(arr, arr + 5, 3)` 将返回 `true`。 - **应用场景**: 在大量有序数据中快速查找特定元素。 #### 5. copy - **功能**: `copy` ...

    leetcodepdfpython-DSA_Tech_Drill:技术面试准备之旅-涵盖数据结构和算法、设计和行为以及资源

    链表的就地反转 BFS,DFS和拓扑排序 2 堆 二分搜索(保存和移动技巧) 按位异或 前 K 个元素 排序算法 K-way合并 前缀总和法 回溯法 单调队列算法 荷兰国旗图案 辅助缓冲法 二分图 连接组件 基于括号的问题 下一个...

    中科大软件学院面试真题-2013最新版

    3. 堆排序与快速排序的不同:堆排序是一种基于比较的排序算法,利用堆这种数据结构进行排序,而快速排序是一种分治算法,通过递归将数据分为较小和较大的两个子集来排序。 4. 循环队列为什么要空一个位置:循环队列...

    中科大软件学院复试面试指南

    - **堆排序**: 基于完全二叉树的数据结构,通过构建和调整堆来排序。 - **快速排序**: 使用分治策略,选择基准值将数组分为两部分,递归排序。 - **不同点**: 快速排序更依赖于好的基准选择,而堆排序的稳定性不受...

    清华2018-21

    2. 基于 CBA 的算法对所有大小为 n 的数组时间复杂度是Ω(nlogn)。这说明 CBA 算法的时间复杂度是Ω(nlogn)。 3. 基数排序的底层排序算法一定是稳定的。基数排序是对数字或字符串进行排序的算法,它的底层排序算法...

    2018清华912回忆版.docx

    - 基于CBA的算法对所有大小为n的数组的时间复杂度是Ω(nlogn),可能涉及到排序或字符串操作。 - 基数排序的底层排序算法必须稳定,因为它依赖于数字的每一位进行排序。 - 完全二叉堆的插入在输入随机的情况下,...

    912_18最全版本1

    - 第2条指出,基于CBA的算法对所有大小为`n`的数组的时间复杂度是`Ω(nlogn)`,这通常意味着它具有最低的下界,比如快速排序或归并排序。 - 第3条中的基数排序是一种稳定的排序算法,这意味着相等的元素在排序后的...

Global site tag (gtag.js) - Google Analytics