排序基础

数组：arr = [9,8,7,6,5,4,3,2,1]

1、选择排序

遍历数组
从第一项开始，循环数组，找到arr中最小的那一项，和arr中的第一项交换，arr=>[1,8,7,6,5,4,3,2,9]
从第二项开始，循环数组，找到arr中最小的那一项，和arr中的第二项交换，arr=>[1,2,7,6,5,4,3,8,9]
......

function selectionSort(arr){
    var l = arr.length,
    i = 0,temp,minIndex,j;
    for(i;i<l;i++){
        minIndex = i;
        for(j = i+1;j<l;j++){
            if(arr[minIndex]>arr[j]){
                minIndex = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

2、插入排序

从第二项开始遍历数组
把第二项插入到前面数组中合适的位置，arr=>[8,9,7,6,5,4,3,2,1]
把第三项插入到前面数组中合适的位置，arr=>[7,8,9,6,5,4,3,2,1]
把第四项插入到前面数组中合适的位置，arr=>[6,7,8,9,5,4,3,2,1]
......
插入排序因为每次进行内层循环时，当前元素的前面的数组是有序的，所以可以提前终止内层循环

方法一：

插入到前面数组中，可以与前一项比较，如果比前面的小，就交换位置

function insertionSort(arr){
    var l = arr.length,
          i = 1,j,temp;
    for(i;i<l;i++){
        for(j = i;j>0&&arr[j]<arr[j-1];j--){
            temp = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = temp;
        }    
    }
    return arr;
}

方法二：

优化方法一，方法一内层循环有三次赋值，影响效率。在第一次循环时可以复制当前值，在内层循环时，如果前一项比当前项大，前一项后移一位。当内层循环结束时，把当前值赋值给当前项

function insertionSort(arr){
    var l = arr.length,
          i = 1,j,current;
    for(i;i<l;i++){
        current = arr[i];
        for(j=i;j>0&&current<arr[j-1];j--){
             arr[j] = arr[j-1];
        }
        arr[j] = current;  
    }
    return arr;
}