排序算法之冒泡排序、选择排序、插入排序

​ 排序就是将一堆无序的数组经过比较和重新排列，让这些数据以其正确的顺序排列。这篇文章先讲三种比较简单的排序算法：冒泡排序、选择排序、插入排序

1. 冒泡排序。

   用一个数组作为例子

   [3,5,2,6,9,1,7,8,0,4]

   第一步：冒泡排序简单来说就是将这个数组的第一个数拿出来和它后边的一个数进行比较，如果前边的数大于后边的数，则说明这两个数的顺序是不对的，所以现在将这两个数字交换，交换过后这两个数的顺序就是对的，第一个数比第二个数小，如果第一个数本来就比第二个数小，那么他们俩的顺序就是对的，不用做任何操作，ok，第一步完成。现在这个数组就应该是这样的：

   [3,5,2,6,9,1,7,8,0,4]

   第二步：现在看第二个数，因为这个数经过第一步的比较，它前边的数肯定比它小，所以不用考虑前边的数，只需要考虑它后边的数。所以拿第二个数和第三个数比较，如果顺序不对，就交换这两个数的位置，如果顺序正确，则不进行操作，这一步做完之后数组一个是这个样子：

   [3,2,5,6,9,1,7,8,0,4]

   第三步：然后就拿第三个和第四个比较，第四个和第五个比较，第五个和第六个比较，直到你拿到的这个数后边没有数的时候，第一遍排序就算进行完了，这个时候数组就应该是这样的：

   [3,2,5,6,1,7,8,0,4,9]

   然后就可以发现，经过一遍排序，这串数组中的最大的一个数就会派到数组的最后边。

   第四步：现在不断重复第一步到第三步，直到所有的数都比它后一个数小，就说明排序完成了，但是这样做的话会做许多没有用的操作，比如我们排了好多遍后数组变成了这样：

   [2,3,5,1,6,7,0,4,8,9]

   当我们进行下一次排序时，当我们拿到第九个数(也就是8)的时候，我们其实没有必要和它后边的数(9)进行比较，因为它后边的这个数和它在前边的几次排序中已经进行过了比较，所以他后边的数肯定比它大，所以是不用比较的，所以后边的步骤就可以跳过，以此类推，这样做就可以省掉好多没有意义的操作。

   整个过程用代码写出来就是这样：

   let str = [3,5,2,6,9,1,7,8,0,4];
   let tmp;
   for(let i = 0;i<str.length;i++){
    for(let n = 0;n<=str.length-i;n++){
        if(str[i] > str[i+n]){
            tmp = str[i];
            str[i] = str[i+n];
            str[i+n] = tmp;
        }
    }
   }
   console.log(str);
   
   

   最后打印到终端就是这样：

   [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

   里层的for循环用来执行步骤里的第一步到第三步，外层的循环用来执行第四步。

   冒泡排序的整个过程就像水里的泡泡一样，只要水够深，大的泡泡总会跑到小的泡泡前边。

2. 选择排序。

   继续用上个数组作为例子。

   [3,5,2,6,9,1,7,8,0,4]

   选择排序在我看来用两个数组来解释最容易理解。首先上边的数组还没有进行过排序，所以我们把它称作未排序数组，然后我们再定义一个数组，[]，没错，就是一个空数组，这个数组用来存放已经排序过的数字，所以把它称作已排序数组。

   第一步：首先从数组中随便挑一个数，这里我们选择未排序数组里的第一个数，然后和数组中的其他数比较，如果遇到比他大的，就继续往后找，如果遇到比他小的，就用这个小的再去比较后边的数，重复以上步骤，当把这个数组里的数都比较了一遍之后，就可以找到一个最小的数，然后把它放到已排序数组中，这个时候这两个数组就应该是这个样子：

   未排序数组：[3,5,2,6,9,1,7,8,4]

   已排序数组：[0]

   第二步：再从未排序数组中选出最小的数字，经过上一轮的比较，拿出来的这个数肯定比已排序数组中的数字大，进过这一轮的比较，肯定比未排序数组中的数字小，所以直接把这个数字跟在已排序数组中的数字的后边。现在这两个数组就应该是这个样子：

   未排序数组：[3,5,2,6,9,7,8,4]

   已排序数组：[0,1]

   第三步：就这样一遍又一遍的从未排序数组中拿出最小的放到已排序数组中，直到未排序数组中没有数字的时候，排序就完成了。

   这个过程用代码可以表示为：

   let str = [3,5,2,6,9,1,7,8,0,4];
   let arr = [];
   let minIndex;
   for(let x = str.length;x > 0; x--){
       minIndex = 0;
       for(let i = 0; i < str.length; i++){
           if(str[minIndex] > str[i]){
               minIndex = i;
           }
       }
       arr.push(str[minIndex]);
       str.splice(minIndex,1);
   }
   console.log(arr);
   

   里层的循环用来找出数组str里最小的数，外层的循环用来一遍又一遍的往数组arr里添加数据。代码运行完之后就是这个样子：

   [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

   这个办法总共需要定义两个数组，简化一下就可以只定义一个数组，简化方法就是将已排序数组放到未排序数组里，当然不是数组里套数组，而是将整个数组分成已排序部分和未排序部分已排序部分在最左侧，未已排序部分在已排序部分右侧，这个时候外层的循环条件就需要改变一下，改成for(let x = 0;x < str.length;x++),因为在一个数组操作的话，整个数组的长度是不会变化的，所以需要x < str.length，而在两个数组的情况下，未排序数组因为数组长度是一直减小的，所以循环条件需要写成for(let x = str.length;x > 0;x--)。里层循环的循环条件同样也是因为所有的操作都是在同一个数组进行，所以开始循环的位置不能从头开始，而是要从未排序部分的开头进行循环，所以循环条件就是let i = x+1;x < str.length;x++。所以最后代码就是这个样子：

   let str = [3,5,2,6,9,1,7,8,0,4];
   let minIndex,tmp;
   for(let x = 0;x < str.length; x++){
       minIndex = x;
       for(let i = x+1; i < str.length; i++){
           if(str[minIndex] > str[i]){
               minIndex = i;
           }
       }
       tmp = str[minIndex];
       str[minIndex] = str[x];
       str[x] = tmp;
   }
   console.log(str);
   

   选择排序应该是最容易理解的算法了

3. 插入排序。

   插入排序同样也用同样的数组来做例子：

   [3,5,2,6,9,1,7,8,0,4]

   插入排序用两个数组解释也很容易理解，原来的数组就是未排序数组，再新定义一个未排序空数组[]。

   第一步：先从未排序数组里取出一个数，这里我们取未排序数组的最后一个数，然后从头去比较已排序数组里的数，因为现在已排序数组里没有数，所以我们就直接将他放在第一位里，此时这两个数组是这样的：

   未排序数组：[3,5,2,6,9,1,7,8,0]

   已排序数组：[4]

   第二步：现在再取未排序数组的最后一个数，然后拿出来从头开始和已排序数组里的每一个数进行比较，如果比被比较的数大，就把这个数插入在这个被比较数的后边，在代码里表示的话就是如果被比较的数比较小，就把这个被比较数的索引记下来，直到找到比拿出来的数大的时候，这个索引就是我们想要的。此时，这两个数组就是这样：

   未排序数组：[3,5,2,6,9,1,7,8]

   已排序数组：[0,4]

   第三步：重复第二步的步骤，直到未排序数组里边没有数据的时候，排序就完成了，整个过程可以用代码这样描述：

   let str = [3,5,2,6,9,1,7,8,0,4];
   let arr = [];
   let maxIndex = 0;
   for(let x = str.length-1;x >= 0;x--){
       if(arr.length == 0){
           arr.push(str[x]);
           str.splice(9,1);
           continue;
       }
       for(let i = 0;i < arr.length; i++){
           if(str[x] > arr[i]){
               maxIndex = i+1;
           }
       }
       arr.splice(maxIndex,0,str[x]);
       str.splice(x,1);
   }
   console.log(arr,str);
   

   最后打印出来就是这样：

   [0,1,2,3,4,5,6,7,8,9][]

   这段代码中里层的循环的作用就是用来把从未排序数组中拿出来的数在已排序数组中进行比较并找到他应该插入的地方，这段循环上边放一个if判断是因为在第一次比较的时候已排序数组中是没有数据的，所以就直接将从未排序数组中拿出来的数直接放在已排序数组中。外层的循环就是用来一遍又一遍从未排序数组中拿出一个数。

   当然，这段代码也是可以进行优化的，将所有的操作放在一个数组中，修改后的代码就是这样的：

   let str = [3,5,2,6,9,1,7,8,0,4];
   let maxIndex;
   for(let x = 1;x < str.length;x++){
       maxIndex = x;
       for(let i = x - 1;i >= 0; i--){
           if(str[x] < str[i]){
               maxIndex = i;
           }
       }
       str.splice(maxIndex,0,str[x]);
       str.splice(x+1,1);
   }
   console.log(str);
   

   同选择排序一样，如果在同一个数组中进行操作，数组最左边就是已排序数组，已排序数组的右边就是未排序数组，每一次在未排序数组中拿出一个数在已排序数组中找到它正确的位置，就把它插入到正确的位置，再把它原来的那个数删掉，这样随着已排序数组的数组长度增加，未排序数组的数组长度减少，直到最后未排序数组的长度为0，整个排序过程也就完成了。

总结：在这三种排序算法中，选择排序和插入排序的思路很相近的，选择排序是在未排序数组中选择数的时候就把正确的数给选出来，然后再放到已排序数组中；而插入排序则是在未排序数组中拿到数字后，在放入已排序数组的时候找到正确的位置；冒泡排序是我接触到的最早的排序算法，也是特别容易理解。这三种算法无论是哪一个，只要按照正确的思路自己在电脑上敲一遍，就会理解的特别透彻。

如有错误，烦请指正。