JavaScript排序专题

冒泡排序

1. 冒泡思路：
   比较任何两个相邻的项目，如果第一个比第二个大，则交换顺序，这样最大值就是气泡一个，升至表面。

先定义一个数组中用到交换顺序的函数：

// left和right表示索引值
 function swap(array, left, right) {
    let rightValue = array[right]
    array[right] = array[left]
    array[left] = rightValue
  }
// ES6用法
function swap(array, left, right) {
     [array[right], array[left]] = [array[left], array[right]];      
   }

2. 代码实现

冒泡排序两重循环：

• 外循环，循环一圈，用于遍历到数组的每一个元素
• 内循环，用于比较两个元素大小，循环一圈，将最大值放到最后，再循环一圈，将第二大值放到倒数第二的位置。

  var array = [12, 22, 2,4, 6, 1,45, 56];
    function bubbleSort (array) {
       var length = array.length;
        for (var i = 0; i < length; i++) {
            for (var j = 0; j < length-1; j++) {
              if(array[j] > array[j+1]){
                swap(array, j, j+1)
              }
            };
        };
      console.log(array);
    }

3. 代码优化
   冒泡的优化的地方是内循环，因为内循环没循环一次，将会确定最大值、第二大值，依次类推。所以没有必要比较已经确定顺序的元素，即内循环只需要比较array.length-i个元素，循环次数为array.lenght-i-1;

优化代码如下：

 var array = [12, 22, 2,4, 6, 1,45, 56];
    function bubbleSort (array) {
       var length = array.length;
        for (var i = 0; i < length; i++) {
            for (var j = 0; j < length-i-1; j++) {
              if(array[j] > array[j+1]){
                swap(array, j, j+1)
              }
            };
        };
      console.log(array);
    }

选择排序

1. 选择的思路：
   选择排序算法是一个原址比较排序算法。大致思路就是，找到数据结构中最小值，然后放到第一位，接着找到第二小的值，放到第二位置。
   那么如何通过遍历去寻找数组元素中的最小值？

    function selectionSort (array) {
        var smallIndex;
      for(let i=0; i< array.length-1; i++){
          // 循环寻找最小值
           smallIndex = i;
          for (let j = i + 1; j < array.length; j++) {
                if(array[smallIndex] > array[j]){
                    smallIndex= j;
                }
          }
          if(i !== smallIndex){
              swap(array, i, smallIndex)
          }
      }
      console.log(array)
    }

2. 代码理解：

• 外循环， i=0时，假定array[i]就是最小值，然后拿这个值去跟还没确定排序位置的元素比较。外循环，每循环一次，找出第i小的值（i从0开始算）。
• 内循环，会寻找出当前数组中还没被选中元素的最小值，所以已经被选中的排序的元素，索引值index < i的，是需要被排除在外的，只比较索引值i和比i还大的元素。

插入排序

1. 插入排序思路：
   想象一下打扑克牌，一上手，从左到右边还是乱序的，现在需要从到小排个序。
   假定第一张牌（最左）位置已经确定，
   然后看第二张（左2），第2张和第1张比较，如果第2张和第1张比大，则将第2张插入到左1的位置
   然后看第三张（左3），跟第1，2张比较，选择插入位置

2. 代码实现：

• 使用一次for循环即可为元素找到自己的位置
• 但是数组索引需要重新编号，如何实现

function insertSort (array) {
        let newArr = [];
        let j;
        // 怎么寻找array[i]的位置
      for(let i=1; i< array.length; i++){   
          j = i;
          tmp = array[i]
         while(j> 0 && array[j-1] < tmp){
             array[j] = array[j-1];
             j--;
         }
         array[j] = tmp;
      }
      console.log(array)
    }

3. 代码理解：
   －　从第二张牌开始，i=1,那第二张牌（arr[i]）与第一张牌（arr[j-1]）比较, 如果第二张牌比第一张大，将第二张牌放到第一张牌的位置， 重新给第二张牌重新编号。重新编号使用while循环。

归并排序

......

快速排序

......

算法复杂度计算方式