| Blog信息 |
|
blog名称:
日志总数:1304
评论数量:2242
留言数量:5
访问次数:7592432
建立时间:2006年5月29日 |
| |
|
 [算法]堆排序算法
软件技术
lhwork 发表于 2006/12/11 11:01:03 |
| 堆排序（Heap Sort）是另外一个比较快的排序算法，时间复杂度和快速排序算法属于同一级别，只不过系数要大些。
在我的机器上用堆排序100万个随机整数花费3.3秒，而快速排序（QuickSort）需要1.6秒。
package cn.tenyears.demo;
/**
* implements the heap sort
*
* @author taolue
*
*/
public class Heap {
private Comparable[] arrList;
private int maxSize = 0;
private int heapSize = 0;
// sort the array
public static void heapSort(Comparable[] arr) {
Heap heap = new Heap(arr);
Comparable com;
int size = arr.length;
for (int i = size - 1; i >= 1; i--) {
com = heap.delete();
arr[i] = com;
}
}
public Heap(int max) {
arrList = new Comparable[max];
maxSize = max;
heapSize = 0;
}
public Heap(Comparable[] arr) {
maxSize = arr.length;
heapSize = maxSize;
arrList = arr;
int curPos = (heapSize - 2) / 2;
while (curPos >= 0) {
goDown(curPos);
curPos--;
}
}
public void insert(Comparable com) {
if (heapSize == maxSize)
return;
arrList[heapSize] = com;
goUp(heapSize);
heapSize++;
}
public Comparable delete() {
Comparable com;
if (heapSize == 0)
return null;
com = arrList[0];
arrList[0] = arrList[heapSize - 1];
heapSize--;
goDown(0);
return com;
}
public boolean isFull() {
return this.maxSize == this.heapSize;
}
public boolean isEmpty() {
return this.heapSize == 0;
}
@SuppressWarnings("unchecked")
private void goUp(int i) {
int curPos = i;
int parentPos = (curPos - 1) / 2;
Comparable com = arrList[curPos];
while (curPos != 0) {
if (arrList[parentPos].compareTo(com) > 0)
break;
else {
arrList[curPos] = arrList[parentPos];
curPos = parentPos;
parentPos = (curPos - 1) / 2;
}
}
}
@SuppressWarnings("unchecked")
private void goDown(int i) {
int curPos = i;
int childPos = 2 * curPos + 1;
Comparable com = arrList[curPos];
while (childPos < heapSize) {
if ((childPos + 1 < heapSize)
&& arrList[childPos + 1].compareTo(arrList[childPos]) > 0)
childPos = childPos + 1;
if (com.compareTo(arrList[childPos]) > 0)
break;
else {
arrList[curPos] = arrList[childPos];
curPos = childPos;
childPos = 2 * curPos + 1;
}
}
arrList[curPos] = com;
}
public static void main(String[] args) {
int size = 1000000;
Integer[] a = new Integer[size];
for (int i = 0; i < size; i++)
a[i] = Integer.valueOf((int) Math.round(Math.random() * size));
long start = System.currentTimeMillis();
heapSort(a);
/*
Heap heap = new Heap(a);
while(!heap.isEmpty()) {
System.out.println(heap.delete());
}
*/
long end = System.currentTimeMillis();
System.out.println("Last: " + (end - start) + " ms");
}
} |
|
|
回复:堆排序算法
软件技术
想学程序设计(游客)发表评论于2007/4/23 15:34:17 |
| 测试代码，刚才忘记贴拉
#include "MergeSort.h"
const DWORD size = 20000000;
int arry [ size ] ;
int _tmain(int argc, _TCHAR* argv[]){ srand( GetTickCount( ) ) ;
for( DWORD i = 0 ; i<size ; i++) arry[ i ] = rand( ) ;
DWORD lasttick = GetTickCount( ) ; MergeSort( arry ,size ) ; lasttick = GetTickCount( ) - lasttick ;
cout<<"Merge Sort times : "<<lasttick <<endl;
return 0;} |
|
|
回复:堆排序算法
软件技术
想学程序设计(游客)发表评论于2007/4/23 15:26:38 |
| 偷别人的代码，合并排序，2000W个整数10秒左右。递归好像不好啊。
测试机器2.8G双CPU＋1G内存。我试验下1E个要多长时间，排序完成后会死机！！！怎么回事啊？？
template< class type >void MergeSort( type * arry , int size ) ;
template< class type >void Merge( type * p1 , type * p2 ) ;
template< class type >void Merge( type * p1 , type * p2 , int size ) ;
template< class type >void Merge( type * p1 , type * p2 ){#if _DEBUG assert( p1 && p2 && p1 != p2 ) ;#endif int size = p2 - p1 ; type * p1temp = p1 ; type * p2temp = p2 ; type * arry = new type[ size * 2 ] ; type * parry = arry ;#if _DEBUG assert( arry ) ;#else if( !arry ) return ;#endif do { if( *p1temp <= *p2temp ) *parry ++ = *p1temp ++ ; else *parry ++ = *p2temp ++ ; if( p1temp == p2 ) { while( p2temp != p2 + size ) *parry ++ = *p2temp ++ ; break ; } else if( p2temp == p2 + size ) { while( p1temp != p2 ) *parry ++ = *p1temp ++ ; break ; } }while( true ) ; parry = arry ; p1temp = p1 ; do { *p1temp ++ = *parry ++ ; }while( p1temp < p2 + size ) ; delete [ ] arry ;}
template< class type >void Merge( type * p1 , type * p2 , int size ){#if _DEBUG assert( p1 && p2 ) ;#else if( !p1 || !p2 ) return ;#endif int count = p2 - p1 ; type * arry = new type[ count + size ] ;#if _DEBUG assert( arry ) ;#else if( !arry ) return ;#endif type * parry = arry ; type * p1temp = p1 ; type * p2temp = p2 ; do { if( *p1temp <= *p2temp ) *parry ++ = *p1temp ++ ; else *parry ++ = *p2temp ++ ; if( p1temp == p2 ) { while( p2temp != p2 + size ) *parry ++ = *p2temp ++ ; break ; } else if( p2temp == p2 + size ) { while( p1temp != p2 ) *parry ++ = *p1temp ++ ; break ; } }while( true ) ; parry = arry ; p1temp = p1 ; do { *p1temp ++ = *parry ++ ; }while( p1temp < p2 + size ) ; delete [ ] arry ;}
template< class type >void MergeSort( type * arry , int size ){ if( !arry || size <= 1 ) return ;
type * pend = arry + size ; int i ; for( i = 2 ; i <= size ; i *= 2 ) { type * pbeg = arry ; do { Merge( pbeg , pbeg + i / 2 ) ; pbeg += i ; }while( pbeg + i <= pend ) ; if( pbeg == pend ) continue ; else if( pbeg + i / 2 >= pend ) continue ; else Merge( pbeg , pbeg + i / 2 , pend - pbeg - i / 2 ) ; } if( i != size ) Merge( arry , arry + i / 2 , size - i / 2 ) ;} |
|
» 1 »
|