//position是这个数组中值最小的数的下标
int position = 0;
//temp是最小的数
int temp = 0;
for(int i=0; i<a.length; i++){
position = i;//每次循环position都指向要交换的位置
temp = a[i];
int j = i+1;
for(; j<a.length; j++){
if(temp>a[j]){
temp = a[j];
position = j;
}
}//这个for循环结束后,position指向最小数的下标,temp是最小的数。
//下边两行代码是:把最小的数和第i个数交换
a[position] = a[i];
a[i] = temp;
}
System.out.println("选择排序后:");
for(int b:a){
System.out.print(b+"\t");
}
}
public static void main(String[] args) {
int[] a = {1,54,6,3,78,34,12,45};
new SelectSort().selectSort(a);
}
}
4,堆排序
(1)基本思想:堆排序是一种树形选择排序,是对直接选择排序的有效改进。
堆的定义如下:具有 n 个元素的序列(h1,h2,...,hn),当且仅当满足(hi>=h2i,hi>=2i+1{意思就是,
根大于等于它的左右孩子节点 })或(hi<=h2i,hi<=2i+1{意思是,根小于或等于它的左右孩子节
点})(i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出,堆顶元素
(即第一个元素)必为最大项(大顶堆)。完全二叉树可以很直观地表示堆的结构。堆顶为根,其它为左
子树、右子树。初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的存储序,使之成为
一个堆,这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新
调整使之成为堆。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有 n 个节点的有序序列。
从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排
序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。
评论0
最新资源