算法基础之排序算法五之堆排序

Posted by Naah on Saturday, Sep 09,2017 09:16:48

选择排序算法

选择排序(Selection sort)是一种简单直观的排序算法。

它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

选择排序是不稳定的排序方法(比如序列[5, 5, 3]第一次就将第一个[5]与[3]交换,导致第一个5挪动到第二个5后面)。

 

堆排序

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。 可以利用数组的特点快速定位指定索引的元素。 堆分为大根堆和小根堆,是完全二叉树。 大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶

算法复杂度:O(N/*logN)

不稳定

算法思想: 1. 构建最大堆:通过取树的中间点,然后循环至根节点,每次遍历一个节点,都由该节点作为根计算大根堆 2. 计算大根堆:通过传入的根节点下标取左右子节点的下标。设置一个最大值下标,下标在堆范围中并且大于最大值下标的值时,将该下标设置为最大下标,如果这个最大值下标不是传入的根节点的下标,那么对传入的根节点以及最大值节点进行交换,并且以最大值节点下标作为根节点下标进行计算大根堆 3. 构建完大根堆以后,数组从后向前遍历,每次将数组第一个元素交换到当前下标位置,并且以第一个元素为根节点,当前下标位置为堆范围进行计算大根堆

/**
 * 堆排序
 * @author Naah
 *
 * @param <T extends Comparable<T>>泛型类必须继承比较接口
 */
public class HeapSort<T extends Comparable<T>> {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Integer[] array={-1,234,5,65,7,8,43,4,7,23,7,323,648,8,232332,543,534};
		HeapSort<Integer> sort=new HeapSort<Integer>();
		sort.heapSort(array);
		for (Integer integer : array) {
			System.out.println(integer);
		}
	}
	/**
	 * 堆排序
	 * @param array 数组
	 */
	public void heapSort(T[] array) {
		// TODO Auto-generated method stub

		//构建最大堆
		buildMaxHeap(array);

		//从后向前循环
		for (int i = array.length-1; i >=1; i--) {

			//前后交换元素
			swap(array, 0, i);

			//构建大堆
			maxHeap(array, i, 0);
		}

	}

	/**
	 * 构建最大堆
	 * @param array 数组
	 */
	private void buildMaxHeap(T[] array) {
		// TODO Auto-generated method stub

		//取数组长度的中间
		int half=(array.length-1)/2;

		//从中间向前循环
		for (int i = half; i >=0; i--) {

			//以数组长度为大堆长度,并且以当前元素作为根下标构建大堆
			maxHeap(array,array.length,i);
		}
	}

	/**
	 * 构建大堆
	 * @param array 数组
	 * @param length 大堆长度
	 * @param i 根元素下标
	 */
	private void maxHeap(T[] array, int length, int i) {

		//左孩子节点下标
		int left=2*i+1;

		//右孩子节点下标
		int right=2*i+2;

		//最大值下标
		int largest=i;

		//如果左孩子在长度以内,同时左孩子元素大于最大元素
		if (left<length&&array[left].compareTo(array[largest])==1) {

			//最大值下标为左孩子下标
			largest=left;
		}

		//如果右孩子在长度以内,同时右孩子元素大于最大元素
		if (right<length&&array[right].compareTo(array[largest])==1) {

			//最大值下标为右孩子下标
			largest=right;
		}

		//如果最大值下标不是根下标
		if (largest!=i) {

			//交换元素
			swap(array,largest,i);

			//以当前大堆长度和最大值下标为根节点下标构建大堆
			maxHeap(array, length, largest);
		}

	}

	/**
	 * 数组交换元素
	 * @param array 数组
	 * @param largest 最大值下标
	 * @param i 交换下标
	 */
	private void swap(T[] array, int largest, int i) {
		// TODO Auto-generated method stub
		T temp=array[i];
		array[i]=array[largest];
		array[largest]=temp;

	}


}