选择排序的初步思想:在排序时找到合适的关键字再做交换,并且只移动一次就完成相应关键字的排序定位工作。
简单选择排序法就是通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1=<i<=n) 个记录交换之。
void SelectSort(SeList *L)
{
int i,j,min;
for(i=1;i<=L->length;i++)
{
min=i; /*将当前下标定义为最小值下标*/
for(j=i+1;j<=L->length;j++) /**循环之后的数据/
{
if(L->r[min]>L->r[j]) /*如果有小于当前最小值的关键字,将此关键字的下标赋给min*/
min=j;
}
if(i!=min) /*i不等于min,说明找到最小值*/
swap(L,i,min);/*交换l->r[i]和l->r[min]的值*/
}
}
复杂度分析
交换移动数据的次数相当少
最好的时候,交换0次
最坏的时候,交换次数为n-1次
时间复杂度为O(n2)
在性能上优先于冒泡排序
js代码
<!doctype html>
<html>
<head>
<title></title>
<script type="text/javascript">
function SelectSort(arr){
for (var i = 1; i <=arr.length; i++) {
var min=i;
for (var j= i+1; j<=arr.length; j++) {
if (arr[min]>arr[j]) {
min=j;
}
}
if (i!=min) {
var temp;
temp=arr[i];
arr[i]=arr[min];
arr[min]=temp;
}
}
}
var array=[1,3,4,2,5,6];
SelectSort(array);
document.write(array);
</script>
</head>
<body
</body>
</html>
执行结果如图
简单选择排序执行结果
网友评论