排序

前言

1. 开发过程中如果遇到庞大数据体系，最优化排序将会使性能最大化
2. 各种算法使用案例
3. 了解内部原理

冒泡排序(Bubble Sort)

通过比较相邻元素的大小，每次将最大（或最小）的元素“冒泡”到数组的一端，然后再从数组的另一端开始，重复这个过程，直到整个数组都排序完成。 缺点： 性能一般

  var arr = [1, 5, 7, 9, 16, 2, 4];
  //冒泡排序,每一趟找出最大的,总共比较次数为arr.length-1次,每次的比较次数为arr.length-1次，依次递减
  function sortByBubbles(arr) {
      var temp;
      for (var i = 0; i < arr.length - 1; i++) {
          for (var j = 0; j < arr.length - 1; j++) {
              if (arr[j] > arr[j + 1]) {
                  temp = arr[j];
                  arr[j] = arr[j + 1];
                  arr[j + 1] = temp;
              }
          }
      }
      return arr;
  }

选择排序(Selection Sort)

每次从未排序的元素中选出最小（或最大）的元素，将其放在已排序元素的末尾，然后重复这个过程，直到整个数组都排序完成。

function selectionSort(arr) {  
  for (let i = 0; i < arr.length - 1; i++) {  
    let minIndex = i;  
    for (let j = i + 1; j < arr.length; j++) {  
      if (arr[j] < arr[minIndex]) {  
        minIndex = j;  
      }  
    }  
    if (minIndex !== i) {  
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];  
    }  
  }  
  return arr;  
}  
  
// 测试  
let arr = [32, 15, 21, 23, 1, 0];  
console.log(selectionSort(arr));

在这个示例中，selectionSort 函数接收一个数组作为参数，然后通过遍历数组，将当前元素与已排序的元素进行比较，将当前元素交换到未排序元素的末尾，从而实现排序。具体来说，它从第二个元素开始，遍历已排序的元素，将当前元素与已排序的元素进行比较，找到最小的元素，然后将其交换到未排序元素的末尾。最后，该函数返回已排序的数组

插入排序（Insertion Sort）

通过将未排序的元素一个一个插入到已排序的数组中，逐步缩小未排序元素的范围，直到整个数组都排序完成。

function insertionSort(arr) {  
  for (let i = 1; i < arr.length; i++) {  
    let current = arr[i];  
    let j = i - 1;  
    while (j >= 0 && arr[j] > current) {  
      arr[j + 1] = arr[j];  
      j--;  
    }  
    arr[j + 1] = current;  
  }  
  return arr;  
}  
  
// 测试  
let arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];  
console.log(insertionSort(arr)); // [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

在这个示例中，insertionSort 函数接收一个数组作为参数，然后通过遍历数组，将当前元素插入到已排序的子数组中，从而实现排序。具体来说，它从第二个元素开始，将其与前面的元素进行比较，如果前面的元素比当前元素大，则将前面的元素向后移动一位，直到找到一个比当前元素小的位置，然后将当前元素插入到该位置。最后，该函数返回已排序的数组

快速排序（Quick Sort）

通过比较相邻元素的大小，选出最小（或最大）的元素，将其放在已排序元素的末尾，然后重复这个过程，直到整个数组都排序完成。

function quickSort(arr) {
      if (arr.length <= 1) {
          return arr;
      }
      var left = [];
      var right = [];
      var midIndex = parseInt(arr.length / 2);
      var mid = arr[midIndex];
      for (var i = 0; i < arr.length; i++) {
          if (i == midIndex) continue;
          if (arr[i] < mid) {
              left.push(arr[i])
          } else {
              right.push(arr[i]);
          }
      }
      return quickSort(left).concat([mid], quickSort(right));
  }

希尔排序

function shellSort(arr) {  
  const n = arr.length;  
  let gap = Math.floor(n / 2);  
  
  while (gap > 0) {  
    for (let i = gap; i < n; i++) {  
      const temp = arr[i];  
      let j = i;  
  
      while (j >= gap && arr[j - gap] > temp) {  
        arr[j] = arr[j - gap];  
        j -= gap;  
      }  
  
      arr[j] = temp;  
    }  
  
    gap = Math.floor(gap / 2);  
  }  
  
  return arr;  
}  
  
// 测试  
const arr = [52, 48, 32, 50, 17];  
console.log(shellSort(arr)); // [17, 16, 19, 22, 32, 48, 52]

在这个示例中，shellSort 函数接收一个数组作为参数，然后通过希尔排序算法对数组进行排序。具体来说，它首先将数组分成若干个子序列，对每个子序列进行插入排序，然后缩小间隔直到间隔为 1，最后对整个数组进行插入排序。在插入排序过程中，使用了一个间隔 gap 来进行元素的比较和交换

对象数组排序

//一维数组排序
    function simpleSort(arr) {
        var copyArr = JSON.parse(JSON.stringify(arr));
        copyArr.sort(function (a, b) {
            return b - a;  //降序排列，return a-b; —>升序排列
        })
        return copyArr;
    }

    var deepArr = [
        { name: 'syy', age: 0 },
        { name: 'wxy', age: 18 },
        { name: 'slj', age: 8 },
        { name: 'wj', age: 20 }
    ];
    //对象数组排序
    function deepBySort(arr, key) {
        var copyArr = JSON.parse(JSON.stringify(arr));
        copyArr.sort(function (a, b) {
            var value1 = a[key];
            var value2 = b[key];
            return value1 - value2;//升序,降序为value2 - value1
        });
        return copyArr;
    }
    var sortArr1 = deepBySort(deepArr, 'age');
    console.log(sortArr1, '=====sortArr1')

总结

以上是一些常见的 JavaScript 排序算法，实际上还有很多其他的排序算法，可以根据具体的需求选择合适的算法。还有如归并排序（Merge Sort）、堆排序（Heap Sort）、计数排序（Counting Sort）、基数排序（Radix Sort）等算法