数据结构中的各种排序方法小结(JS实现)

本文将介绍常见的八种排序算法：

1. 冒泡排序
2. 插入排序
3. 选择排序
4. 快速排序
5. 归并排序
6. 堆排序
7. 希尔排序
8. 计数排序

下面进行详细讲解。

冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历数组，比较相邻的两个元素，并按大小交换位置，一直到整个数组排序完成。它的时间复杂度为O(n^2)。

示例代码：

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

const arr = [5, 2, 7, 1, 3, 6];
const sortedArr = bubbleSort(arr);
console.log(sortedArr); // [1, 2, 3, 5, 6, 7]

插入排序

插入排序是一种简单的排序算法，它每次从未排序的数组中取出第一个元素，将它插入到已排序的数组中的合适位置。插入操作需要将插入位置后面的元素逐个后移，直到找到合适的位置。它的时间复杂度为O(n^2)。

示例代码：

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

const arr = [5, 2, 7, 1, 3, 6];
const sortedArr = insertionSort(arr);
console.log(sortedArr); // [1, 2, 3, 5, 6, 7]

选择排序

选择排序是一种简单的排序算法，它每次从未排序的数组中选出最小（大）的元素，放到已排序的数组的末尾。它的时间复杂度为O(n^2)。

示例代码：

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

const arr = [5, 2, 7, 1, 3, 6];
const sortedArr = selectionSort(arr);
console.log(sortedArr); // [1, 2, 3, 5, 6, 7]

快速排序

快速排序是一种常用的排序算法，它采用分治法的思想，将数组分成左右两个子数组，确定一个基准元素，将小于基准元素的放在左边，大于基准元素的放在右边，然后对左右两个子数组递归地调用快速排序。它的时间复杂度为O(nlogn)。

示例代码：

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

const arr = [5, 2, 7, 1, 3, 6];
const sortedArr = quickSort(arr);
console.log(sortedArr); // [1, 2, 3, 5, 6, 7]

归并排序

归并排序是一种稳定的排序算法，它使用分治法的思想，将数组递归地分成两半，对每一半递归地调用归并排序，最后将两个有序的子数组归并成一个有序的数组。它的时间复杂度为O(nlogn)。

示例代码：

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

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

const arr = [5, 2, 7, 1, 3, 6];
const sortedArr = mergeSort(arr);
console.log(sortedArr); // [1, 2, 3, 5, 6, 7]

堆排序

堆排序是一种树形选择排序算法，它的本质是利用堆这种数据结构来维护数组的顺序，利用堆这种数据结构来实现了一个优先队列，堆顶元素为整个堆中的最大（或最小）值。它的时间复杂度为O(nlogn)。

示例代码：

function heapSort(arr) {
  // 对数组进行堆化
  for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
    heapify(arr, i, arr.length);
  }
  // 依次从堆中取出最大值，放到数组末尾
  for (let i = arr.length - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, 0, i);
  }
  return arr;
}

function heapify(arr, i, len) {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  if (left < len && arr[left] > arr[largest]) {
    largest = left;
  }
  if (right < len && arr[right] > arr[largest]) {
    largest = right;
  }
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, largest, len);
  }
}

const arr = [5, 2, 7, 1, 3, 6];
const sortedArr = heapSort(arr);
console.log(sortedArr); // [1, 2, 3, 5, 6, 7]

希尔排序

希尔排序是一种插入排序的变体。它的基本思想是：将数组分成若干个子序列，对每个子序列进行插入排序，每次减少子序列的长度，最后整个数组变成一个有序序列。希尔排序的时间复杂度与选取的增量序列有关，不同的增量序列有不同的时间复杂度。最坏情况下的时间复杂度为O(n^2)。

示例代码：

function shellSort(arr) {
  const len = arr.length;
  let gap = Math.floor(len / 2);
  while (gap > 0) {
    for (let i = gap; i < len; 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 = [5, 2, 7, 1, 3, 6];
const sortedArr = shellSort(arr);
console.log(sortedArr); // [1, 2, 3, 5, 6, 7]

计数排序

计数排序是一种非基于比较的排序算法，它的核心思想是：统计每个元素出现的次数，计算出每个元素应该出现的位置。它的时间复杂度为O(n+k)，其中k为计数数组的大小。

示例代码：

function countingSort(arr) {
  const max = Math.max(...arr);
  const min = Math.min(...arr);
  const len = max - min + 1;
  const count = new Array(len).fill(0);
  for (let i = 0; i < arr.length; i++) {
    count[arr[i] - min]++;
  }
  let index = 0;
  for (let i = 0; i < len; i++) {
    while (count[i] > 0) {
      arr[index++] = i + min;
      count[i]--;
    }
  }
  return arr;
}

const arr = [5, 2, 7, 1, 3, 6];
const sortedArr = countingSort(arr);
console.log(sortedArr); // [1, 2, 3, 5, 6, 7]

以上就是八种常见的排序算法的介绍和JS代码实现。对于每种算法的时间复杂度和优缺点，可以根据实际情况选择使用。