js 常用排序

1. 冒泡排序

原理：从第一个元素开始，把当前元素和下一个索引元素进行比较。如果当前元素大，那么就交换位置，重复操作直到比较到最后一个元素

    function bubbleSort(arr) {

      if (Array.isArray(arr)) {

        for (var i = arr.length - ; i > ; i--) {

          for (var j = ; j < i; j++) {

            if (arr[j] > arr[j + ]) {

              [arr[j], arr[j + ]] = [arr[j + ], arr[j]];

            }

          }

        }

        return arr;

      }

    }

2.插入排序

原理：第一个元素默认是已排序元素，取出下一个元素和当前元素比较，如果当前元素大就交换位置。那么此时第一个元素就是当前的最小数，所以下次取出操作从第三个元素开始，向前对比，重复之前的操作。

    function insertSort(arr) {

      if (Array.isArray(arr)) {

        for (var i = ; i < arr.length; i++) {

          var preIndex = i - ;

          var current = arr[i]

          while (preIndex >=  && arr[preIndex] > c) {

            arr[preIndex + ] = arr[preIndex];

            preIndex--;

          }

          arr[preIndex + ] = current;

        }

        return arr;

      }

    }

3.选择排序

原理：遍历数组，设置最小值的索引为 0，如果取出的值比当前最小值小，就替换最小值索引，遍历完成后，将第一个元素和最小值索引上的值交换。如上操作后，第一个元素就是数组中的最小值，下次遍历就可以从索引 1 开始重复上述操作。

    function selectSort(arr) {

      if (Array.isArray(arr)) {

        for (var i = ; i < arr.length - ; i++) {

          var minIdex = i;

          for (var j = i + ; j < arr.length; j++) {

            minIdex = arr[j] < arr[minIdex] ? j : minIdex;

          }

          [arr[i], arr[minIdex]] = [arr[minIdex], arr[i]];

        }

        return arr;

      }

    }

4.快速排序

原理：在数据集之中，找一个基准点，建立两个数组，分别存储左边和右边的数组，利用递归进行下次比较。

    function quickSort(arr) {

      if (!Array.isArray(arr)) return;

      if (arr.length <= ) return arr;

      var left = [], right = [];

      var num = Math.floor(arr.length / );

      var numValue = arr.splice(num, )[];

      for (var i = ; i < arr.length; i++) {

        if (arr[i] > numValue) {

          right.push(arr[i]);

        } else {

          left.push(arr[i]);

        }

      }

      return [...quickSort(left), numValue, ...quickSort(right)]

    }

5. 希尔排序

原理：

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列个数 k，对序列进行 k 趟排序；

每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

    function shellSort(arr) {

      var len = arr.length,

        temp,

        gap = ;

      // 动态定义间隔序列，也可以手动定义，如 gap = 5；

      while (gap < len / ) {

        gap = gap *  + ;

      }

      for (gap; gap > ; gap = Math.floor(gap / )) {

        for (var i = gap; i < len; i++) {

          temp = arr[i];

          for (var j = i - gap; j >=  && arr[j] > temp; j -= gap) {

            arr[j + gap] = arr[j];

          }

          arr[j + gap] = temp;

        }

      }

      return arr;

    }

6.归并排序

原理：

（1）把长度为n的输入序列分成两个长度为n/2的子序列；

（2）对这两个子序列分别采用归并排序；

（3）将两个排序好的子序列合并成一个最终的排序序列。

    function mergeSort(arr) {  //采用自上而下的递归方法

      var len = arr.length;

      if (len < ) {

        return arr;

      }

      var middle = Math.floor(len / ),

        left = arr.slice(, middle),

        right = arr.slice(middle);

      return merge(mergeSort(left), mergeSort(right));

    }

    function merge(left, right) {

      var result = [];

      while (left.length && right.length) {

        // 不断比较left和right数组的第一项，小的取出存入res

        left[] < right[] ? result.push(left.shift()) : result.push(right.shift());

      }

      return result.concat(left, right);

    }

未完待续...

巴特西

js 常用排序

最新文章

热门文章