美文网首页
简单选择排序

简单选择排序

作者: Random_ | 来源:发表于2017-11-09 19:49 被阅读0次

    选择排序的初步思想:在排序时找到合适的关键字再做交换,并且只移动一次就完成相应关键字的排序定位工作。

    简单选择排序法就是通过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>
    
    

    执行结果如图


    简单选择排序执行结果

    相关文章

      网友评论

          本文标题:简单选择排序

          本文链接:https://www.haomeiwen.com/subject/qwpmmxtx.html