欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JavaScript实现经典排序算法之选择排序

程序员文章站 2022-08-14 08:38:39
表现最稳定的排序算法之一,因为无论什么数据进去都是o(n²)的时间复杂度.....所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。...

表现最稳定的排序算法之一,因为无论什么数据进去都是o(n²)的时间复杂度.....所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间。
1)算法原理

         先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

2)算法描述和实现

       n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下:

      <1>初始状态:无序区为r[1..n],有序区为空;

      <2>第i趟排序(i=1,2,3...n-1)开始时,当前有序区和无序区分别为r[1..i-1]和r(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 r[k],将它与无序区的第1个记录r交换,使r[1..i]和r[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;

      <3>n-1趟结束,数组有序化了。

3)javascript代码实现

function selectsort(arr){ 
 var len = arr.length; 
 var index,temp; 
 for(var i = 0; i < len-1 ;i++){ 
  index = i; 
  for(var j = i + 1 ; j<len; j++){ 
   if(arr[j] < arr[index]){//寻找最小的数 
    index = j;//保存最小数的索引 
   } 
  } 
  temp = arr[i]; 
  arr[i] = arr[index]; 
  arr[index] = temp; 
 } 
 return arr; 
} 
 
var arr=[1,45,37,5,48,15,37,26,29,2,46,4,17,50,52]; 
console.log(selectsort(arr)); 

4)算法分析

       最佳情况:t(n) = o(n2)
       最差情况:t(n) = o(n2)
      平均情况:t(n) = o(n2)

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。