JavaScript 常见的三种数组排序方式

算法思路（以按递增顺序排列为例）：

1、我们需要做一个内层循环来比较每对相邻元素的大小，如果前面大于后面，就让他们交换位置，我们要让小的数在前面，大的数在后面

2、当内层循环结束时，在数组最后一位的元素，就一定是这个数组中最大的元素了，这时候除了最后一个元素不用再动以外（所以内层循环每循环一次就可以少循环一次）我们还要再来确定这个数组中第二大的元素，第三大的元素，以此类推，因此我们还需要一层外层循环。如果这个数组有 n 个元素我们就要确定 n - 1 个元素的位置，所以外层循环需要循环的次数就是 n - 1 次

3、只需要内外两层循环嵌套，就可以把数组排序好啦，虽然实现方式可能有很多种，这只是我个人的想法，代码如下，排序功能已封装成函数，请放心食用：

var myArr = [89,34,76,15,98,25,67];

function bubbleSort(arr) {
for (var i = 0; i < arr.length - 1; i++) {
for (var j = 0; j < arr.length - i; j++) {
if(arr[j] > arr[j + 1]) {
// 交换两个数的位置
            var temp = 0;

            temp = arr[j];

            arr[j] = arr[j + 1];

            arr[j + 1] = temp;

        }

    }

}    

return  arr;      

}


console.log(bubbleSort(myArr));

二、选择排序

选择排序 英文叫法是 Selection sort，这也是一种简单直观的排序方法

这种排序首先会在未排序的数组中找到最小或者最大的元素，存放在排序数组的起始位置

然后再从未排序的数列中去找到这个数组中第二大或这第二小的数放在已排序的数之后，以此类推，不断重复直到所有元素排列完毕

算法思路（以按递增顺序排列为例）：

1、我们需要内层循环找出未排序数列中的最小值（找最小值可以用之前谁比最小值小谁就替换最小值的思路），循环后找到未排序数列中的最小元素时记录最小的那个元素在数组中的索引值，用索引获得最小值的位置后把它放在数组的第一位，此处注意，如果直接放在第一位会替换第一位数组中原来的元素，我们需要交换最小值的位置，和第一个元素的位置（利用两个变量交换数值的方法）

2、每经过一次内层循环，我们就能确定一个未排序数组中最小值的位置，在确定倒数第二个数的位置时，最后一个数的位置也自然而然地被确定了，因此数组中有 n 个元素我们就需要进行 n - 1 次内层循环，我们就用用外层循环来保持内层循环的重复进行

var myArr = [89,34,76,15,98,25,67];

function selectSort(arr) {
for(var i = 0; i < arr.length - 1; i++) {
//i < arr.length - 1 因为排完倒数第二个，倒数第一个数自然在它正确的位置了
        var index = i;
for(var j = i + 1; j < arr.length; j++) {
// 寻找最小值
            if(arr[index] > arr[j]){
// 保存最小值索引
                index = j;

            }

        }

// 将未排序中的最小数字，放到未排序中的最左侧
        if(index != i) {
var temp = arr[i];

            arr[i] = arr[index];

            arr[index] = temp;

        }

    }
return arr;

}


console.log(selectSort(myArr));

三、插入排序

插入排序 英文称为 Insertion sort ，插入排序也被叫做直接插入排序

它的基本思想是将一个未排序的元素插入到已经排序好的数组中，从而使得已排序的数组增加一个元素，通过插入不断完善已排序数组的过程，就是排序整个数组的过程。

算法思路（以按递增顺序排列为例）：

1、因为数组中第一个元素前面没有元素可以进行比较，所以我们从第二个元素开始比较，用 current 变量来进行存储当前要和别人比较的元素，用 preIndex变量 来方便我们去找当前准备插入元素之前的元素

2、内层循环就是按顺序比较插入元素和之前元素的大小，来确定插入元素的位置， preIndex 每比较一次就自减1 ，让准备插入元素和它之前的所有已排序元素都比较一遍，每当待插入元素比前一个数小了，前面的元素就往右挪一个位置，直到前一个数小于待插入数，跳出判断，待插入元素放在前一次判断挪动元素留出的空位上，由于我们提前用 current 保存了要插入的元素，所以要插入的元素不会因为前面的元素覆盖而丢失。

3、每循环一次内层循环，我们就可以确定一个元素的插入位置，但由于我们内层循环是从第二个元素开始的（也就是索引为 1 的元素），因此如果有 n 个元素，我们就需要 n - 1 次内层循环，内存循环我们用外层循环来实现，外层循环就这么被定义完成了

var myArr = [89,34,76,15,98,25,67];

function insertionSort(arr) {
for (var i = 1; i <= arr.length - 1; i++) {
var preIndex = i - 1;

        current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {

            arr[preIndex + 1] = arr[preIndex];

            preIndex--;

        }

        arr[preIndex + 1] = current;

    }
return arr;

}


console.log(insertionSort(myArr)); 

总结：

选择排序（一种不稳定的排序方法）

优点：移动数据的次数已知（n-1次）；

缺点：比较次数多。

冒泡排序

优点：稳定；

缺点：慢，每次只能移动相邻两个数据。

插入排序

优点：稳定，快；

缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。

原文：https://zhuanlan.zhihu.com/p/368208410