JS基础-排序

（前两种要求掌握）

1、冒泡排序

原理：比较两个相邻的元素，将值大的元素交换至右端。

思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。

第一趟比较完成后，最后一个数一定是数组中最大的一个数，所以第二趟比较的时候最后一个数不参与比较；
第二趟比较完成后，倒数第二个数也一定是数组中第二大的数，所以第三趟比较的时候最后两个数不参与比较；
依次类推，每一趟比较次数-1；

排序冒泡.gif

举例：

<script>
            var arr = [32,3,45,576,33,78,867,31,3,21,32];
            console.log(arr);
            //外层趟数length-1
            for(var i = 0; i < arr.length-1; i++){
                //内层比较次数length-1-i次
                for(var j = 0; j < arr.length-1-i; j++){
                    //谁跟谁比较？
                    if(arr[j] > arr[j+1]){
                        //交换顺序
                        var temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                    }
                }
            }
            console.log(arr);
        </script>

2、选择排序

把每一个数都与第一个数比较，如果小于第一个数，就把它们交换位置；这样一轮下来，最小的数就排到了最前面；重复n-1轮，就实现了选择排序
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。

排序选择.gif

举例：

<script>
          var arr = [32,3,45,576,33,78,867,31,3,21,32];
          console.log(arr);
          
          //外层趟数length-1
          for(var i = 0; i < arr.length - 1; i++){
              //默认当前值是剩下元素中最小的
              var minIndex = i;
              //内层循环从i+1开始,length-1结束
              
              for(var j = i+1; j < arr.length; j++){
                  //比较
                  if(arr[minIndex] > arr[j]){
                      //说明minIndex并不是最小下标
                      minIndex = j;
                  }
      
              }
              //内层循环结束之后,这一趟的最小值就是arr[minIndex]
              arr[i] += arr[minIndex];
              arr[minIndex] = arr[i] - arr[minIndex];
              arr[i] -= arr[minIndex];
          }
          console.log(arr);
      </script>

3、插入排序

（1） 从第一个元素开始，该元素可以认为已经被排序
（2） 取出下一个元素，在已经排序的元素序列中从后向前扫描
（3） 如果该元素（已排序）大于新元素，将该元素移到下一位置
（4） 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
（5）将新元素插入到下一位置中
（6） 重复步骤2

插入排序.gif

举例：

插入排序.png

4、快速排序

快速排序是对冒泡排序的一种改进，第一趟排序时将数据分成两部分，一部分比另一部分的所有数据都要小。然后递归调用，在两边都实行快速排序。
大致分三步：
1、找基准（一般是以中间项为基准）
2、遍历数组，小于基准的放在left，大于基准的放在right
3、递归

快速排序.gif

举例：

快速排序.png