首页 > 代码库 > 选择排序算法
选择排序算法
选择排序的基本思想是：每一趟从待排序的记录中选出关健字最小的记录，按顺序放在已排序的记录序列的最后，直到全部排完为止。
简单选择排序（Simple Selection Sort）也称作直接选择排序
代码如下
void SelectSort(int[] list){
for(int i=0;i<list.length;i++){
int min=list[i];
int t=i;
for(int j=i;j<list.length;j++){
if(min>list[j]){
min=list[j];
t=j;
}
}
list[t]=list[i];
list[i]=min;
}
}
算法时间复杂度O（n2）空间复杂度为1
算法特点
（1）就选择排序方法本身来讲，它是一种稳定的排序方法
（2）可用于链式存储
（2）移动次数较少，当每一记录占用的空间较多时，此方法比直接插入排序快
堆排序算法
堆排序（Heap Sort）是一种树形选择排序，在排序过程中，将待排序的记录r[1...n]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序的序列中选择关键字最大（或最小）的记录。
算法如下
public void heapAdjust(int H[],int start,int end){
int temp=H[start];
for(int i=2*start+1;i<=end;i*=2){
if(i<end&&H[i]<H[i+1]){
++i;
}
if(temp>H[i]){ //左右孩子中获胜者与父亲的比较
break;
}
//将孩子结点上位，则以孩子结点的位置进行下一轮的筛选
H[start]=H[i];
start=i;
}
H[start]=temp;//插入最开始不和谐的元素
}
void heapSort(int A[],int n){
//先建立大顶堆
for(int i=n/2;i>=0;--i){
heapAdjust(A,i,n);
}
//进行排序
for(int i=n-1; i>0; --i)
{
//最后一个元素和第一元素进行交换
int temp=A[i];
A[i] = A[0];
A[0] = temp;
//然后将剩下的无序元素继续调整为大顶堆
heapAdjust(A,0,i-1);
}
}
时间复杂度为O(nlog2 n) 空间复杂度为O(1).
算法特点
（1）是不稳定
（2）只能用于顺序结构，不能用于链式
（3）初始建堆所需的次数较多，因此记录数较少，因此记录数较少时不宜采用。
选择排序算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。