JS 列表排序，javascript 常用的排序代码段

大家好，欢迎来到IT知识分享网。

1.冒泡排序

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

function bubbleSort(arr) { 
   
      if (Array.isArray(arr)) { 
   
        for (var i = arr.length - 1; i > 0; i--) { 
   
          for (var j = 0; j < i; j++) { 
   
            if (arr[j] > arr[j + 1]) { 
   
              [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
          }
        }
        return arr;
      }
 }

2.插入排序

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

function insertSort(arr) { 
   
      if (Array.isArray(arr)) { 
   
        for (var i = 1; i < arr.length; i++) { 
   
          var preIndex = i - 1;
          var current = arr[i]
          while (preIndex >= 0 && arr[preIndex] > c) { 
   
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
          }
          arr[preIndex + 1] = current;
        }
        return arr;
      }
}

3.选择排序

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

function selectSort(arr) { 
   
      if (Array.isArray(arr)) { 
   
        for (var i = 0; i < arr.length - 1; i++) { 
   
          var minIdex = i;
          for (var j = i + 1; 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 <= 1) return arr;
      var left = [], right = [];
      var num = Math.floor(arr.length / 2);
      var numValue = arr.splice(num, 1)[0];
      for (var i = 0; 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 = 1;
      // 动态定义间隔序列，也可以手动定义，如 gap = 5；
      while (gap < len / 5) { 
   
        gap = gap * 5 + 1;
      }
      for (gap; gap > 0; gap = Math.floor(gap / 5)) { 
   
        for (var i = gap; i < len; i++) { 
   
          temp = arr[i];
          for (var j = i - gap; j >= 0 && 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 < 2) { 
   
        return arr;
      }
      var middle = Math.floor(len / 2),
        left = arr.slice(0, 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[0] < right[0] ? result.push(left.shift()) : result.push(right.shift());
      }
      return result.concat(left, right);
    }

原文地址：https://www.cnblogs.com/bear-blogs/p/10808399.html