基于js 各种排序方法和sort方法的区别(详解)

针对“基于js 各种排序方法和sort方法的区别(详解)”这个话题，我将从以下几个方面进行详细讲解。

一、基础排序算法

在介绍各种排序算法之前，我们先了解一下几个基础排序算法：冒泡排序、插入排序和选择排序。

1. 冒泡排序

冒泡排序的基本思路是比较相邻的元素，如果前面的元素比后面的大，则交换这两个元素。每完成一轮比较，就可以确定一个最大的元素，并且这个最大的元素已经排好序了。时间复杂度为O(n^2)。

以下是冒泡排序的JavaScript代码实现：

function bubbleSort(array) {
  const len = array.length;
  for(let i = 0; i < len; i++) {
    for(let j = 0; j < len - i - 1; j++) {
      if(array[j] > array[j + 1]) {
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
      }
    }
  }
  return array;
}

2. 插入排序

插入排序的基本思路是将一个数组分成两个部分，一部分是已经排好序的，另一部分是待排序的。每次取出待排序部分的第一个元素，将它插入到已排序部分的正确位置。时间复杂度为O(n^2)。

以下是插入排序的JavaScript代码实现：

function insertionSort(array) {
  const len = array.length;
  for(let i = 1; i < len; i++) {
    let j = i - 1;
    const tmp = array[i];
    while(j >= 0 && array[j] > tmp) {
      array[j + 1] = array[j];
      j--;
    }
    array[j + 1] = tmp;
  }
  return array;
}

3. 选择排序

选择排序的基本思路是从待排序的数组中找到最小的元素，将它放到已排序数组的末尾。这样每次找到的最小元素都是未排序数组中最小的元素。时间复杂度为O(n^2)。

以下是选择排序的JavaScript代码实现：

function selectionSort(array) {
  const len = array.length;
  for(let i = 0; i < len; i++) {
    let minIndex = i;
    for(let j = i + 1; j < len; j++) {
      if(array[j] < array[minIndex]) {
        minIndex = j;
      }
    }
    [array[i], array[minIndex]] = [array[minIndex], array[i]];
  }
  return array;
}

二、高级排序算法

高级排序算法包括快速排序、归并排序和堆排序。这些算法的时间复杂度都是O(nlogn)。

1. 快速排序

快速排序的基本思路是选择一个元素作为“基准元素”，然后将数组中的其他元素分别与这个基准元素进行比较，将较小的元素排在基准元素的左边，将较大的元素排在基准元素的右边。然后对基准元素左右的子数组分别进行递归后，再对其进行合并。快速排序的关键在于选取合适的基准元素。时间复杂度为O(nlogn)。

以下是快速排序的JavaScript代码实现：

function quickSort(array) {
  if (array.length <= 1) {
    return array;
  }
  const pivotIndex = Math.floor(array.length / 2);
  const pivot = array.splice(pivotIndex, 1)[0];
  const left = [];
  const right = [];
  for (let i = 0; i < array.length; i++) {
    if (array[i] < pivot) {
      left.push(array[i]);
    } else {
      right.push(array[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

2. 归并排序

归并排序的基本思路是将数组分成两个部分，对这两个部分分别进行递归，直到每个部分只有一个元素。然后将这些只有一个元素的部分合并起来，并按照从小到大的顺序排列。时间复杂度为O(nlogn)。

以下是归并排序的JavaScript代码实现：

function mergeSort(array) {
  if (array.length <= 1) {
    return array;
  }
  const midIndex = Math.floor(array.length / 2);
  const left = array.slice(0, midIndex);
  const right = array.slice(midIndex);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }
  return result.concat(left.slice(i), right.slice(j));
}

3. 堆排序

堆排序的基本思路是利用堆这种数据结构进行排序。首先将数组转化为一个大根堆，然后将堆顶元素与数组末尾元素交换，接着再将前n-1个元素转化为大根堆，再交换堆顶元素与数组末尾元素。如此反复操作直到完成排序。时间复杂度为O(nlogn)。

以下是堆排序的JavaScript代码实现：

function heapSort(array) {
  const len = array.length;
  for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
    heapify(array, len, i);
  }
  for (let i = len - 1; i >= 0; i--) {
    [array[0], array[i]] = [array[i], array[0]];
    heapify(array, i, 0);
  }
  return array;
}

function heapify(array, len, k) {
  let maxIndex = k;
  let left = 2 * k + 1;
  let right = 2 * k + 2;
  if (left < len && array[left] > array[maxIndex]) {
    maxIndex = left;
  }
  if (right < len && array[right] > array[maxIndex]) {
    maxIndex = right;
  }
  if (maxIndex !== k) {
    [array[k], array[maxIndex]] = [array[maxIndex], array[k]];
    heapify(array, len, maxIndex);
  }
}

三、数组的Sort方法

JavaScript数组自带的sort方法可以进行升序排列和降序排列。如果没有指定比较函数，则按照字符串的unicode码进行排序。如果指定了比较函数，那么按照比较函数的规则进行排序。

以下是按照数字大小进行升序排列的JavaScript代码实现：

const array = [3, 1, 4, 2, 5];
array.sort(function(a, b) {
  return a - b;
});
console.log(array); // [1, 2, 3, 4, 5]

以下是按照数字大小进行降序排列的JavaScript代码实现：

const array = [3, 1, 4, 2, 5];
array.sort(function(a, b) {
  return b - a;
});
console.log(array); // [5, 4, 3, 2, 1]

四、各种排序方法和sort方法的区别

除了基础排序算法和高级排序算法之外，还有很多其他的排序算法，比如希尔排序、计数排序、桶排序和基数排序等。这些算法有各自的优缺点和适用场景。而JavaScript数组的sort方法则只能进行升序排列和降序排列。

总体来说，使用JavaScript数组的sort方法比手写排序函数更为简便，因为它已经很好地考虑了各种情况。但如果我们需要掌握各种排序算法的原理和实现方法，还是需要手写排序函数的。