常用排序算法总结（三）----选择排序 堆排序

SelectSort

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 算法的最差时间复杂度为O(n^2),最优为O(n^2),平均时间复杂度为O(n^2)，空间复杂度为O（n）,需要辅助空间O（1）

代码

package Sort;import java.util.Arrays;/** * @author Biang Hoo * * 2013年9月14日 */public class HeapSort implements Sort {public void Sorting(int[] array) {MakeMinHeap(array);for(int i=array.length-1;i>0;i--){Swap(array,0,i);ShiftDown(array,0,i-1);}}private void MakeMinHeap(int[] array){int len = array.length;for(int i=len/2-1;i>=0;i--){ShiftDown(array,i,len);}}private void ShiftDown(int[] array,int i,int n){int temp = array[i];int key=2*i+1;while(key<n ){if(key+1<n && array[key]>array[key+1]){key++;}if(array[key]>temp){break;}array[i] =array[key];i = key;key = 2*i+1;}array[i] = temp;}private void Swap(int[] array,int i,int j){int temp = array[i];array[i] = array[j];array[j] = temp;}}