选择排序算法
选择排序（Selection sort）是一种简单直观的排序算法。
它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。
堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。 可以利用数组的特点快速定位指定索引的元素。 堆分为大根堆和小根堆，是完全二叉树。 大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶
算法复杂度：O(N/*logN)
不稳定
算法思想：
- 构建最大堆：通过取树的中间点，然后循环至根节点，每次遍历一个节点，都由该节点作为根计算大根堆
- 计算大根堆：通过传入的根节点下标取左右子节点的下标。设置一个最大值下标，下标在堆范围中并且大于最大值下标的值时，将该下标设置为最大下标，如果这个最大值下标不是传入的根节点的下标，那么对传入的根节点以及最大值节点进行交换，并且以最大值节点下标作为根节点下标进行计算大根堆
- 构建完大根堆以后，数组从后向前遍历，每次将数组第一个元素交换到当前下标位置，并且以第一个元素为根节点，当前下标位置为堆范围进行计算大根堆
/**
* 堆排序
* @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;
}
}
