浏览 3709 次
|
锁定老帖子 主题：基于数组实现的就地堆排序
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-03-01
最后修改：2010-03-03
思想最重要，结合图形来分析就简单了： 实现的是小顶堆排序算法,大堆思路差不多： 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：
声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2010-08-13
最后修改：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");
}
|
| 返回顶楼 | |
|
发表时间：2010-08-14
用的是一些基本语法来写的，替换语言很容易。呵呵
|
| 返回顶楼 | |
