简单选择排序

• 基本思想：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换。（废话不多说，先看代码）。

1     function SelectSort(arr){ 2         var i,j,min,temp; 3         for(i=0;i
     
      arr[j]){     //找出arr.length-1-i个中最小的 7                     min=j; 8                 } 9             }10             if(i!=min){11                 temp=arr[min];12                 arr[min]=arr[i];13                 arr[i]=temp;14             }15         }16     }17     var arr=[9,1,5,8,3,7,4,6,2];18     SelectSort(arr);19     console.log(arr); // [1, 2, 3, 4, 5, 6, 7, 8, 9]
     

在简单选择排序中，每次将下标为i的数设为最小值（除去i前面已经排好序的数以外），然后让它和它后边的所有数值进行比较，选出最小值，放到第i个位置。（这也正是基本思想的含义：从n-i+1个记录中选出关键字最小的记录）。下标为min始终记录最小的值，当没有发生变化时，说明不需要交换，下标为i的数后边均大于下标为i的数。进行下一轮i++.....。当min发生变化时，说明下标为i的数后边存在小于下标为i的数，用min记录下它的下标。进行min和i的判断时，进行交换。

• 时间复杂度

最大的特点：交换移动数据次数比较小，大多在进行条件的判断。在比较次数中，第i趟排序需要进行n-i次关键字的比较，此时，需要（n-1）+(n-2)+.....+1=n(n-1)/2次。在交换次数中，最好的情况：交换次数为0；最差的情况：交换次数n-1。最终时间复杂度为O（n^2）.

• 在性能上，简单选择排序略优于冒泡排序。