记录-前端基础之10种排序算法

这里给大家分享我在网上总结出来的一些知识，希望对大家有所帮助

了解排序算法的优缺点和适用场景是非常重要的，因为在实际开发中，需要根据实际情况选择最合适的排序算法。不同的排序算法适用于不同的场景，有的算法适用于小规模的数据集，有的算法适用于大规模的数据集，有的算法适用于稳定排序，有的算法适用于不稳定排序，有的算法时间复杂度低，有的算法空间复杂度低，等等。了解这些算法的特点和适用场景可以帮助我们更好地选择算法，提高代码效率和性能。此外，了解排序算法还可以帮助我们更好地理解计算机科学的基本概念和理论，提高我们的编程能力和思维水平。

1. 冒泡排序

冒泡排序是一种简单的排序算法。它重复地遍历要排序的列表，比较相邻的两个元素，如果它们的顺序错误就交换它们。遍历整个列表的工作会一遍又一遍地进行，直到列表没有再需要交换的元素为止。

冒泡排序的代码：

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]) { // 如果前一个元素比后一个元素大，就交换它们的位置
        var temp = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}

var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(bubbleSort(arr)); // [11, 12, 22, 25, 34, 64, 90]

冒泡排序的时间复杂度为O(n^2)，其中n是列表的长度。它的空间复杂度为O(1)。在实际应用中，冒泡排序的性能通常比其他排序算法要差，因此很少被使用。

2. 快速排序

快速排序使用分治的思想来将一个大的问题分解成几个小的问题，然后递归地解决这些小问题，最终将它们组合起来得到答案。具体来说，快速排序使用一个元素作为“枢轴”，将列表分成两个子列表，一个子列表所有元素都比枢轴小，另一个子列表所有元素都比枢轴大。然后递归地对两个子列表进行排序。

快速排序的代码：

		function quickSort(arr) {
			// 如果数组长度为1或0，则已经有序
			if (arr.length <= 1) {
				return arr
			}
			// 选择一个基准元素
			let mainIndex = parseInt(arr.length / 2);
			let mainItem = arr.splice(mainIndex, 1)[0];
			// 将数组分为两个子数组，一个包含小于基准的元素，一个包含大于基准的元素
			let left = [];
			let right = [];
			arr.forEach((item) => {
				if (item > mainItem) {
					right.push(item)
				} else {
					left.push(item)
				}
			})
			// 递归地对子数组进行排序，并在基准元素中间将它们连接起来
			return quickSort(left).concat([mainItem], quickSort(right))
		}

		// 测试该函数
		var arr = [64, 34, 25, 12, 22, 11, 90];
		console.log(quickSort(arr));

快速排序的时间复杂度为O(nlogn)，其中n是列表的长度。它的空间复杂度取决于具体实现，通常为O(logn)。

快速排序的优点是它的时间复杂度较低，通常为O(nlogn)，并且它可以原地排序，即不需要分配额外的空间。此外，快速排序的实现很简单，易于理解和实现。

然而，快速排序也有一些缺点。对于小规模的数据集效果不佳，因为它的递归深度较大。其次，快速排序是一种不稳定的排序算法，这意味着在排序后相同的元素可能会被重新排序。最后，快速排序的性能可能会受到输入数据的影响，如果数据已经有序或接近有序，快速排序的效率可能会明显降低。

3. 插入排序

插入排序的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。具体来说，插入排序将列表分成两部分：已排序和未排序。每次取出未排序部分的第一个元素，然后将它插入到已排序部分的正确位置。

插入排序的代码：

function insertionSort(arr) {
  var len = arr.length;
  for (var i = 1; i < len; i++) {
    var key = arr[i]; // 将要插入的元素存储在变量key中
    var j = i - 1; // 从已排序序列的最右边开始比较
    // 将所有比key大的元素向右移动一个位置
    while (j >= 0 && arr[j] > key) {
      arr[j+1] = arr[j];
      j = j - 1;
    }
    arr[j+1] = key; // 将key插入到正确的位置
  }
  return arr;
}

var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(insertionSort(arr));

插入排序的时间复杂度为O(n^2)，其中n是列表的长度。它的空间复杂度为O(1)。

插入排序的优点是它的实现简单，容易理解。此外，它在处理小规模的数据集时效果很好。插入排序是一种稳定的排序算法，这意味着在排序后相同的元素不会被重新排序。

然而，插入排序也有一些缺点。在处理大规模的数据集时，插入排序的效率会明显降低。此外，它是一种不适合外部排序的排序算法，因为它需要频繁地访问列表中的元素。

4. 选择排序

选择排序的基本思想是每次从未排序的部分选出最小的元素，然后将它放到已排序部分的末尾。

选择排序的代码：

function selectionSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len - 1; i++) {
    var minIndex = i; // 先假设当前位置是最小值的索引
    for (var j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) { // 如果后面的元素比当前最小值还要小，更新最小值的索引
        minIndex = j;
      }
    }
    var temp = arr[minIndex]; // 将最小值与当前位置交换
    arr[minIndex] = arr[i];
    arr[i] = temp;
  }
  return arr;
}

var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(selectionSort(arr)); // [11, 12, 22, 25, 34, 64, 90]

对于一个长度为n的列表，选择排序需要进行n-1趟排序。在第i趟排序中，程序会在未排序部分中找到最小的元素，并将它与第i个元素交换位置。最终，列表将按照从小到大的顺序排列。

选择排序的时间复杂度为O(n^2)，其中n是列表的长度。它的空间复杂度为O(1)。

选择排序的优点是它的实现简单，容易理解。此外，它是一种不需要额外的空间的排序算法，因为它只需要一个额外的变量来存储最小值的索引。选择排序是一种稳定的排序算法，这意味着在排序后相同的元素不会被重新排序。

然而，选择排序也有一些缺点。它不适合外部排序的排序算法，因为它需要频繁地访问列表中的元素。最后，选择排序的性能可能会受到输入数据的影响，如果数据已经有序或接近有序，选择排序的效率可能会明显降低。

5. 归并排序

归并排序是一种分治的排序算法。它的基本思想是将一个大的问题分解成几个小的问题，然后递归地解决这些小问题，最终将它们组合起来得到答案。具体来说，归并排序将列表分成两个子列表，然后递归地对这两个子列表进行排序，并将它们合并成一个有序的列表。

归并排序的代码：

// 归并排序
function mergeSort(arr) {
  if (arr.length <= 1) { // 如果列表只有一个元素，已经有序，直接返回
    return arr;
  }
  var mid = Math.floor(arr.length / 2); // 找到列表的中间点
  var left = arr.slice(0, mid); // 将列表分成左右两部分
  var right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right)); // 递归地对左右两部分进行排序，并将它们合并起来
}

function merge(left, right) {
  var result = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) { // 如果左边的第一个元素小于等于右边的第一个元素，就将它从左边的列表中取出并加入到结果列表中
      result.push(left.shift());
    } else { // 否则，将右边的第一个元素从列表中取出并加入到结果列表中
      result.push(right.shift());
    }
  }
  while (left.length) { // 将左边剩余的元素加入到结果列表中
    result.push(left.shift());
  }
  while (right.length) { // 将右边剩余的元素加入到结果列表中
    result.push(right.shift());
  }
  return result; // 返回结果列表
}

var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(mergeSort(arr));

归并排序的时间复杂度为O(nlogn)，其中n是列表的长度。它的空间复杂度为O(n)，其中n是列表的长度。

归并排序的优点是它的时间复杂度较低，通常为O(nlogn)，并且它可以处理大规模的数据集。此外，归并排序是一种稳定的排序算法，这意味着在排序后相同的元素不会被重新排序。最后，归并排序可以用于外部排序，因为它可以将数据分成较小的块，这些块可以逐个读取到内存中进行排序。

然而，归并排序也有一些缺点。它需要额外的空间来存储临时列表和递归调用堆栈。这对于内存受限的环境可能是一个问题。其次，归并排序的实现比其他排序算法复杂，因此它不如其他排序算法易于理解和实现。归并排序的常数因子较大，因此它的实际效率可能低于其他具有相同时间复杂度的排序算法。

总之，归并排序是一种高效、稳定的排序算法，它适用于处理大规模的数据集，特别是内存受限的环境。但是，它的实现较为复杂，因此在实际应用中需要谨慎选择。

6. 希尔排序

希尔排序是一种插入排序的变体。它的基本思想是设定一个增量序列，将列表分成若干个子列表，对每个子列表进行插入排序。每次缩小增量序列，直到增量为1，最后对整个列表进行插入排序。

通过将列表分成若干子列表来提高插入排序的性能，每个子列表使用插入排序进行排序。这些子列表的长度从原始列表长度的一半开始，每次迭代都将子列表长度除以2，直到长度为1。

希尔排序的代码：

function shellSort(arr) {
  var len = arr.length;
  for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (var i = gap; i < len; i++) {
      var j = i;
      var temp = arr[i];
      // 将当前元素与之前的元素进行比较，如果需要交换就交换它们的位置
      while (j >= gap && arr[j-gap] > temp) {
        arr[j] = arr[j-gap];
        j = j - gap;
      }
      arr[j] = temp; // 将当前元素插入到正确的位置
    }
  }
  return arr;
}

var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(shellSort(arr)); // [11, 12, 22, 25, 34, 64, 90]

希尔排序的时间复杂度为O(n^2)，而它的空间复杂度为O(1)。虽然它比快速排序和归并排序慢，但它的代码实现比较简单，也比较容易理解。

希尔排序的优点是它比插入排序更快，尤其是对于较大的数据集。它的时间复杂度为O(nlogn)，比选择排序和插入排序都要快。此外，希尔排序是一种不稳定的排序算法，这意味着在排序后相同的元素可能会被重新排序。

然而，希尔排序也有一些缺点。它的实现比插入排序更复杂，需要计算增量序列并对多个子列表进行排序。希尔排序的时间复杂度比快速排序和归并排序高，因此它可能不适用于处理较大的数据集。最后，希尔排序的实现依赖于增量序列的选择，不同的增量序列可能会导致不同的性能表现。

7. 堆排序

堆排序是一种选择排序的变体。它的基本思想是将列表构建成一个堆，然后依次取出堆顶元素，并将剩余元素重新构建成一个堆。具体来说，堆排序首先将列表构建成一个大根堆或小根堆（本例使用大根堆），然后依次将堆顶元素与最后一个元素交换，然后重新构建堆。

堆排序的代码：

function heapSort(arr) {
  var len = arr.length;
  for (var i = Math.floor(len/2)-1; i >= 0; i--) {
    heapify(arr, len, i); // 将数组构建成大顶堆
  }
  for (var j = len-1; j > 0; j--) {
    var temp = arr[0];
    arr[0] = arr[j]; // 将当前最大值放到数组的末尾
    arr[j] = temp;
    heapify(arr, j, 0); // 重新将剩余的元素构建成大顶堆
  }
  return arr;
}

function heapify(arr, len, index) {
  var left = 2 * index + 1;
  var right = 2 * index + 2;
  var largest = index;
  if (left < len && arr[left] > arr[largest]) {
    largest = left;
  }
  if (right < len && arr[right] > arr[largest]) {
    largest = right;
  }
  if (largest != index) {
    var temp = arr[index];
    arr[index] = arr[largest];
    arr[largest] = temp;
    heapify(arr, len, largest); // 递归地将子树构建成大顶堆
  }
}

var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(heapSort(arr)); // [11, 12, 22, 25, 34, 64, 90]

堆排序的时间复杂度为O(nlogn)，它的空间复杂度为O(1)。
堆排序的优点是它的时间复杂度较低，对于大规模数据集的排序效率较高。此外，堆排序是一种稳定的排序算法，即排序后相同的元素不会被重新排序。另外，堆排序可以用于外部排序，因为它可以将数据分成较小的块，这些块可以逐个读取到内存中进行排序。

堆排序的缺点是它需要额外的空间来存储堆，这对于内存受限的环境可能是一个问题。其次，堆排序的实现比其他排序算法复杂，因此它不如其他排序算法易于理解和实现。最后，堆排序的常数因子较大，因此它的实际效率可能低于其他具有相同时间复杂度的排序算法。

8. 计数排序

计数排序是一种非比较排序算法。它的基本思想是统计每个元素出现的次数，然后依次输出元素。具体来说，计数排序首先找出列表中的最大值和最小值，然后创建一个计数数组，统计每个元素出现的次数，再依次输出元素。

计数排序的代码：

function countingSort(arr) {
  var len = arr.length;
  var max = Math.max.apply(null, arr); // 找到最大值
  var min = Math.min.apply(null, arr); // 找到最小值
  var count = new Array(max - min + 1).fill(0); // 创建一个计数数组，初始值为0
  var output = new Array(len); // 创建一个与原数组长度相同的输出数组
  for (var i = 0; i < len; i++) {
    count[arr[i] - min]++; // 计数数组中对应元素的计数加1
  }
  for (var j = 1; j < count.length; j++) {
    count[j] += count[j-1]; // 将计数数组进行累加，得到每个元素的最终位置
  }
  for (var k = len-1; k >= 0; k--) {
    output[count[arr[k]-min]-1] = arr[k]; // 将当前元素放到对应位置，并将计数数组中对应元素的计数减1
    count[arr[k]-min]--;
  }
  for (var m = 0; m < len; m++) {
    arr[m] = output[m]; // 将输出数组复制回原数组
  }
  return arr;
}

var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(countingSort(arr));

计数排序需要额外的空间来存储计数数组，因此它的空间复杂度为O(k)，其中k是计数数组的大小。计数排序的时间复杂度为O(n+k)，其中n是列表的长度。

计数排序的优点是它的时间复杂度较低，对于小范围的数据集排序效率较高。此外，计数排序是一种稳定的排序算法，即排序后相同的元素不会被重新排序。

然而，计数排序也有一些缺点。它只能用于非负整数排序，并且需要额外的空间来存储计数数组，因此它的空间复杂度较高。计数排序的实现比其他排序算法复杂，因此不如其他排序算法易于理解和实现。最后，计数排序的常数因子较大，因此它的实际效率可能低于其他具有相同时间复杂度的排序算法。

总之，计数排序是一种效率较高、稳定的排序算法，特别适用于小范围的数据集。但是，它的实现较为复杂，因此在实际应用中需要谨慎选择。

9. 桶排序

桶排序是一种非比较排序算法。它的基本思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。具体来说，桶排序首先将列表分到有限数量的桶里，然后对每个桶里的数据进行排序，最后将每个桶里的数据按顺序连接起来。

桶排序的代码：

function bucketSort(arr, bucketSize) {
  if (arr.length === 0) { // 如果数组为空，直接返回
    return arr;
  }
  var i;
  var minValue = arr[0]; // 找到数组中的最小值和最大值
  var maxValue = arr[0];
  for (i = 1; i < arr.length; i++) {
    if (arr[i] < minValue) {
      minValue = arr[i];
    } else if (arr[i] > maxValue) {
      maxValue = arr[i];
    }
  }
  var DEFAULT_BUCKET_SIZE = 5; // 设置默认的桶大小为5
  bucketSize = bucketSize || DEFAULT_BUCKET_SIZE; // 如果未指定桶大小，使用默认大小
  var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1; // 计算需要的桶的数量
  var buckets = new Array(bucketCount); // 创建桶数组
  for (i = 0; i < buckets.length; i++) { // 初始化桶数组
    buckets[i] = [];
  }
  for (i = 0; i < arr.length; i++) { // 将元素分配到桶中
    buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
  }
  arr.length = 0; // 将原数组清空
  for (i = 0; i < buckets.length; i++) { // 对每个桶进行插入排序，并将它们合并到原数组中
    insertionSort(buckets[i]);
    for (var j = 0; j < buckets[i].length; j++) {
      arr.push(buckets[i][j]);
    }
  }
  return arr; // 返回排序后的数组
}

var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(bucketSort(arr)); // [11, 12, 22, 25, 34, 64, 90]

桶排序的时间复杂度为O(n+k)，其中n是列表的长度，k是桶的数量。桶排序的空间复杂度取决于桶的数量，通常为O(n)或O(k)。如果k较大，桶排序的空间复杂度将较高，如果k较小，桶排序的时间复杂度将较高。

桶排序是一种稳定的排序算法，即排序后相同的元素不会被重新排序。另外，桶排序可以用于外部排序，因为它可以将数据分成较小的块，这些块可以逐个读取到内存中进行排序。

然而，桶排序也有一些缺点。它需要额外的空间来存储桶，因此它的空间复杂度较高。其次，桶排序的实现比其他排序算法复杂，因此不如其他排序算法易于理解和实现。最后，桶排序的常数因子较大，因此它的实际效率可能低于其他具有相同时间复杂度的排序算法。另外，如果数据分布不均匀，桶的数量将不均匀，这可能会导致桶排序的性能下降。

总之，桶排序是一种效率较高、稳定的排序算法，特别适用于小范围的数据集。但是，它的实现较为复杂，因此在实际应用中需要谨慎选择。

10. 基数排序

基数排序是一种非比较排序算法。它的基本思想是将整个列表按照位数切割成不同的数字，然后按每个位数分别比较。具体来说，基数排序首先将所有的元素统一为同样的位数，然后从最低位开始依次进行排序，直到最高位排序完毕。在每个位上，使用稳定排序算法（如计数排序）对元素进行排序。

基数排序的代码：

function radixSort(arr) {
  var maxDigit = getMaxDigit(arr);
  for (var i = 0; i < maxDigit; i++) {
    arr = bucketSort(arr, i);
  }
  return arr;
}

// 获取数组中最大数字的位数
function getMaxDigit(arr) {
  var maxDigit = 1;
  for (var i = 0; i < arr.length; i++) {
    var num = arr[i];
    var digit = 1;
    while (Math.floor(num/10) !== 0) {
      digit++;
      num = Math.floor(num/10);
    }
    if (digit > maxDigit) {
      maxDigit = digit;
    }
  }
  return maxDigit;
}

// 根据数字的某一位进行桶排序
function bucketSort(arr, digit) {
  var buckets = new Array(10); // 创建10个桶
  for (var i = 0; i < buckets.length; i++) {
    buckets[i] = []; // 初始化每个桶
  }
  for (var j = 0; j < arr.length; j++) {
    var num = arr[j];
    var radix = getRadix(num, digit); // 获取数字的某一位
    buckets[radix].push(num); // 将数字放入对应的桶中
  }
  var result = [];
  for (var k = 0; k < buckets.length; k++) { // 将所有桶中的数字按顺序放入结果数组中
    result = result.concat(buckets[k]);
  }
  return result;
}

// 获取数字的某一位
function getRadix(num, digit) {
  return Math.floor(num / Math.pow(10, digit)) % 10;
}

var arr = [64, 34, 25, 12, 22, 11, 90];
console.log(radixSort(arr));

基数排序的时间复杂度为O(kn)，其中k是最大数字的位数，n是列表的长度。它的空间复杂度为O(k+n)。基数排序的时间复杂度较低，但它需要额外的空间来存储桶和排序结果，因此在空间有限的情况下可能不适用。

写在后面

这些排序算法各有优缺点，应根据待排序数据的规模、排序的稳定性、时间复杂度和空间复杂度等多种因素进行选择。对于小规模的数据集，可以考虑使用冒泡排序、选择排序、插入排序或希尔排序等简单的排序算法；对于大规模的数据集，可以考虑使用归并排序、快速排序或堆排序等高效的排序算法。而计数排序、桶排序和基数排序适用于特定的排序场景，应根据具体情况选择。

需要注意的是，排序算法的实现可能会影响排序的效率和稳定性。因此，在选择排序算法时，应综合考虑多种因素，并根据具体情况进行选择。

本文转载于:

https://juejin.cn/post/7216936647505756215

如果对您有所帮助，欢迎您点个关注，我会定时更新技术文档，大家一起讨论学习，一起进步。

 

原文链接：https://www.cnblogs.com/smileZAZ/p/17298920.html