package 选择排序;
public class SelectSort {
public static void main(String[] args) {
// TODO 自动生成的方法存根
int[] input = new int[]{0,9,1,5,8,3,7,4,6,2};
selectSort(input);
for(int k : input){
System.out.print(k + "\t");
}
System.out.println();
int[] input_new = new int[]{0,9,1,5,8,3,7,4,6,2};
heapSort(input_new);
for(int k : input_new){
System.out.print(k + "\t");
}
}
/**
* 堆排序
* @param input_new
*/
private static void heapSort(int[] input_new) {
// TODO 自动生成的方法存根
int n = input_new.length-1;//除开数组的哨兵,这里取有效长度
for(int i=n/2 ; i>=1 ; i--){
adjustHeap(input_new,i,n);
}
for(int i=n ; i>1 ; i--){
swap(input_new,1,i);
adjustHeap(input_new,1,i-1);
}
}
/**
* 调整堆
* @param input
* @param i 堆顶
* @param n 堆长度
*/
private static void adjustHeap(int[] input, int i, int n) {
int x = input[i];
for(int j=i*2 ; j<=n ; j*=2){
if(j<n && input[j]<input[j+1]){//左右子树节点比较,取较大的索引为j
j++;
}
if(x >= input[j]){//根节点与子节点中的最大值比较,若大,则无需交换
break;
}
input[i] = input[j];//交换值
i = j;//为循环做准备
}
input[i] = x;//注意经过循环后,i值可能有变,此时的i==j
}
/**
* 简单选择排序
* @param input
*/
private static void selectSort(int[] input) {
int i,j,min;
for(i=1 ; i<input.length ; i++){
min = i;
for(j=i+1 ; j<input.length ; j++){
if(input[min] > input[j]){
min = j;
}
}
if(i!=min){
swap(input,min,i);
}
}
}
private static void swap(int[] input, int min, int i) {
int temp = input[min];
input[min] = input[i];
input[i] = temp;
}
}
