//! 快速排序

pub fn sort<T:Copy + PartialOrd>(data:&mut Vec<T>){
	let low = 0;
	let high = data.len() - 1;
	quick_sort(data,low,high);
}

fn partition<T:Copy + PartialOrd>(data:&mut Vec<T>,low:usize,high:usize)->usize{
	let mut i = low;
	let mut j = high;
	let pivot = data[low];
	while i < j{
		while i < j && data[j] >= pivot{
			j -= 1;
		}
		data[i] = data[j];
		while i < j && data[i] <= pivot{
			i += 1;
		}
		data[j] = data[i];
	}
	data[i] = pivot;
	i
}

fn quick_sort<T:Copy + PartialOrd>(data:&mut Vec<T>,low:usize,high:usize){
	if low < high{
		let loc = partition(data,low,high);
		quick_sort(data,low,loc-1);
		quick_sort(data,loc+1,high);
	}
}
