JS数组排序技巧汇总(冒泡、sort、快速、希尔等排序)

JS数组排序技巧汇总

在 Javascript 中，排序操作是非常常见的操作。本篇文章将会介绍常见的几种排序算法：冒泡排序、选择排序、插入排序、快速排序和希尔排序。同时，我们也会讲解如何使用这些算法在 Javascript 中进行排序。

冒泡排序

冒泡排序是最基础的算法之一，也是最容易理解的算法之一。它通过依次比较相邻的两个元素，把大的元素往后排，小的元素往前排。

以下是一个使用冒泡排序进行升序排序的例子：

function bubbleSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len - 1; i++) {
    for (var 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, 4, 3, 2, 1];
console.log(bubbleSort(arr)); // [1, 2, 3, 4, 5]

选择排序

选择排序是另一种基础的排序算法，它通过不断选择最小的元素，来实现排序。

以下是一个使用选择排序进行升序排序的例子：

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

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

插入排序

插入排序是一种简单直观的排序算法，它的思路是将未排序序列中的元素插入到已排序序列的合适位置。

以下是一个使用插入排序进行升序排序的例子：

function insertSort(arr) {
  var len = arr.length;
  for (var i = 1; i < len; i++) {
    var temp = arr[i];
    var j = i - 1;
    while (j >= 0 && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }
  return arr;
}

const arr = [5, 4, 3, 2, 1];
console.log(insertSort(arr)); // [1, 2, 3, 4, 5]

快速排序

快速排序是常见的排序算法之一，它通过递归调用自身来实现分治的思想，将大问题分解成小问题，以此解决大问题。

以下是一个使用快速排序进行升序排序的例子：

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];

  for (var i = 0, len = arr.length; i < len; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return quickSort(left).concat([pivot], quickSort(right));
}

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

希尔排序

希尔排序是插入排序的一种改进，它通过定义一个增量序列来将列表分成多个子序列进行排序，最终合并成完整的有序序列。

以下是一个使用希尔排序进行升序排序的例子：

function shellSort(arr) {
  var len = arr.length;
  var gap = Math.floor(len / 2);
  while (gap > 0) {
    for (var i = gap; i < len; i++) {
      var temp = arr[i];
      var j = i - gap;
      while (j >= 0 && arr[j] > temp) {
        arr[j + gap] = arr[j];
        j -= gap;
      }
      arr[j + gap] = temp;
    }
    gap = Math.floor(gap / 2);
  }
  return arr;
}

const arr = [5, 4, 3, 2, 1];
console.log(shellSort(arr)); // [1, 2, 3, 4, 5]

以上是几个常见的排序算法，它们各有优缺点，在实际开发中需要根据具体情况选择使用哪种算法来进行排序操作。