js冒泡、选择、插入排序

• 排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等
• 数组排序的第一类，思路是将数组分为有序区和无序区两块算法过程，就是通过 遍历+比较+交换 将无序区的数移动到有序区。移动到有序区的，数都是当前无序区的，最大值或者最小值 （无序区的极值）

1、冒泡排序： 冒泡排序是一个，无序区在前，有序区在后的算法如果从小到大排序，每轮比较，都要把当前无序区的最大值移动到有序区。

• 冒泡排序的规律
  外层循环比较的是轮数， 也叫趟数
  1、规律：对于一个长度为length数组，需要比较 length – 1 趟
  2、原因：每轮都会排好一个，到最后一个时就不用排了
  3、规律：每趟需要比较的次数 == length – 轮数 – 1
  4、原因：每轮的无序区的数 == length – 轮数
  由于是两两比较，因此，每轮比较的次数 == 无序区数 – 1
  5、总循环次数 = 1 ==》 length – 1 的累加和 = length – 1 * length / 2

  for(var i = 0; i < arr.length - 1; i++) {
        for(var j = 0; j < arr.length - i - 1; j++) {
            if(arr[j] > arr[j + 1]) {
                // 大就交换位置
                var temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
       }
 }

2、选择排序：有序区在前，无序区在后

• 选择排序执行规律：
  首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

  再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

 for(var i = 0 ; i < arr.length - 1; i++){
        //定义当前轮的最小值，为有序区第一个值
        var min = arr[i];
        //记录最小值下标
        var minIndex = i;
        for(var j = i + 1; j < arr.length  ; j++){
            if(min > arr[j]){
                min = arr[j];  // min保存最小值
                minIndex = j;  //minIndex保存最小值下标
            }
        }
        // 判断如果 minIndex != i 就交换位置
        if(minIndex != i){
            var temp = arr[i];
            arr[i]   = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

3、插入排序：是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

• 插入排序执行规律：
  将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面）

 for (var i = 1; i < arr.length; i++) {
        //定义变量保存要比较的数
        var now = arr[i];
        //保存当前的位置
        var j = i;
        // 循环次数不确定用while循环
        //升序   now < arr[j - 1]
        //降序   now > arr[j - 1]
        while (j && now < arr[j - 1]) {
            //如果now比左边一位小，就将左边向右移动一位
            arr[j] = arr[j - 1];
            j--;
        }
        //将now放入arr[j]的位置
        arr[j] = now; 
    }