排序算法

一、冒泡排序

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

    var sortArray = function(nums) {
        for(let i = 0;i<nums.length-1;i++){
            for(let j = 0;j<nums.length-1-i;j++){
                if(nums[j+1]<nums[j]){
                                    [nums[j+1],nums[j]] = [nums[j],nums[j+1]]
                    ~~var temp = nums[j+1]
                    nums[j+1] = nums[j]
                    nums[j] = temp~~
                }
            }
        }
        return nums;
    };

二、插入排序

思路：类似斗地主的时候分牌时边拿牌边排序的方式，每次取出数组一个数，再循环新数组，从数组的最后一位判断两个数的大小，循环中遇到第一个比他大的数A的时候，用splice把数插在A后面。
1、需要排序的数组为Arr，取出第一个数作为新数组A
2、从第二个数开始循环遍历数组Arr，并从数组A的最后一项开始循环数组A
3、Arr的每一项分别从数组A的后往前作对比，当Arr的数第一次遇到比数组A的某一项大的时候，将数插在该项的后面。
4、循环3的操作直到数组Arr结束

    let arr = [3,3,4,5,6,1,3,5,5,6,1]
      let newArr = [arr[0]]
      for(let i = 1;i < arr.length-1;i++){
          for(let j = newArr.length-1;j>=0;j--){
              if(arr[i]>newArr[j]){
                  newArr.splice(j+1,0,arr[i])
                  break;
              }
              if(j === 0){
                  newArr.unshift(arr[i])
              }
    
          }
      }
      console.log(newArr)

三、快速排序

思路:采用二分法的方式，选出中间那一项的值并取出，然后对比其他值如果比中间项大放”arrRight“数组，比中间项小又放”arrLeft“数组，最后合并”arrRIght“+中间项+“arrLeft"
1、取数组的中间项middleItem并从原数组分离
2、申请左数组arrLeft和右数组arrRight两个新空间
3、循环遍历原数组其他项与中间项对比，大的放右数组，小的放左数组
4、合并”arrRIght“+中间项+“arrLeft"

    let arr = [3,3,4,5,6,1,3,5,5,6,1]
    function quick(arr){
        if(arr.length<=1){
            return arr
        }
        //寻找数组中间项,并取出来
        let middleItem = arr.splice(Math.floor(arr.length/2),1)[0]
        let arrRight = [],
            arrLeft = []
        for(let i = 0;i<arr.length;i++){
            arr[i]>middleItem?arrRight.push(arr[i]):arrLeft.push(arr[i])
        }
        return quick(arrLeft).concat(middleItem,quick(arrRight))
    }
    console.log(quick(arr))

四、选择排序

思路:给每个位置选择当前元素最小的，比如取出第一位，取出当前数组最小值与第一位交换位置，再取第二位，再找到最小值与第二位交换，以此类推

    var arr = [1, 3, 2, 8, 9, 1, 5];
    function SelectionSort(arr) {
        if (arr == null || arr.length < 2) {
            return arr;
        }
        for (let i = 0; i < arr.length - 1; i++) {
            let minIndex = i;
            for (let j = i + 1; j < arr.length; j++) {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            [arr[i],arr[minIndex]] = [arr[minIndex],arr[i]]
        }
        return arr;
    }