数据结构与算法——排序算法之选择排序

一：选择排序原理：

将要排序的数据元素选出最小（大），将他和数据元素的首位交换位置。再次从剩下的数据元素中 找到最小（大）的元素，然后与数据元素的第二位子交换。。。直到将整个数据元素排序。

总之他在不断选择剩余元素的最小值，然后放在恰当的位置。

二：选择排序的特点：

1.运行时间和输入无关。

为了找出最小的元素，遍历整个数组并不能为下一次遍历提供信息。这样的缺点是：一个有序的数组与一个随机数组所用的排序时间相同。

2.数据移动最少。

每次交换都会改变两个元素的值，因此数组多大，就几次数据移动。

三：代码描述（java实现）：

public static void sort(int[] a){

int N=a.length;

for(int i=0;i

int min=i;

for(int j=i+1;j

if(a[j]

min=j;

}

}

int temp=a[i];

a[i]=a[min];

a[min]=temp;

}

}

内循环为找到当前序列的最小元素。然后最小元素与相应的位置的元素交换位置。每次交换能确定一个元素的位置，所以总交换次数为N.所以算法的时间效率取决于比较次数N*（N-1）/2

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!