sort_method 0.1.0

//! 堆排序

pub fn sort<T:Copy + PartialOrd>(data:&mut Vec<T>){
	let n = data.len();
	for i in (0..n/2).rev(){//n/2-1正好是最后一个分支节点
		heap_adjust(data,i,n-1);
	}
	for i in (1..n).rev(){
		let tmp = data[0];
		data[0] = data[i];
		data[i] = tmp;
		heap_adjust(data,0,i-1);
	}
}

//在data[s..m]所构成的一个元素序列中，除了data[s]外，其余元素均满足大顶堆的定义，
//调整data[s]的位置，使data[s..m]成为一个大顶堆
fn heap_adjust<T:Copy + PartialOrd>(data:&mut Vec<T>,s:usize,m:usize){
	if s >= m{
		return;
	}
	let mut ss = s;
	let tmp = data[ss];
	let mut j = 2 * ss + 1;
	loop{
		if j < m && data[j] < data[j+1]{
			j += 1;
		}
		if tmp >= data[j]{
			break;
		}
		data[ss] = data[j];
		ss = j;
		
		j = 2 * j + 1;
		if j > m{
			break;
		}
	}
	data[ss] = tmp;
}