JS前端面试：排序算法详解与实现【插入/选择/归并/冒泡/快速】

本文主要介绍了JS前端面试中常见的几种排序算法，包括插入排序、选择排序、归并排序、冒泡排序和快速排序的原理与实现方法，并提供了JavaScript代码示例。 插入排序 插入排序是一种简单直观的排序算法。它的工作原理是通过构造一个有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。具体步骤如下： 1. 从第一个元素开始，该元素视为已排序。 2. 取出下一个元素，在已排序序列中从后向前扫描。 3. 如果当前元素大于新元素，将当前元素移到下一位置。 4. 重复步骤3，直到找到已排序的元素小于或等于新元素的位置。 5. 将新元素插入到该位置后。 6. 重复步骤2~5，直到所有元素均排序完毕。 例如，对于数组 `arr = [5, 6, 3, 1, 8, 7, 2, 4]`，经过插入排序后变为 `[1, 2, 3, 4, 5, 6, 7, 8]`。 插入排序的JavaScript实现如下： ```javascript function insertSort(arr) { var tmp; for (var i = 1; i < arr.length; i++) { tmp = arr[i]; for (var j = i; j >= 0; j--) { if (arr[j - 1] > tmp) { arr[j] = arr[j - 1]; } else { arr[j] = tmp; break; } } } return arr; } ``` 插入排序的时间复杂度为 O(n^2)。 选择排序 选择排序是一种不稳定的排序算法，其思想是每次从未排序的元素中找到最小（或最大）的元素，放到已排序序列的末尾。具体步骤如下： 1. 假设第一个元素为最小元素。 2. 在剩余未排序元素中找到最小（或最大）元素，放到已排序序列的末尾。 3. 重复步骤2，直到所有元素均排序完毕。 例如，对于数组 `arr = [5, 6, 3, 1, 8, 7, 2, 4]`，经过选择排序后变为 `[1, 2, 3, 4, 5, 6, 7, 8]`。 选择排序的JavaScript实现如下： ```javascript function selectSort(arr) { for (var i = 0; i < arr.length - 1; i++) { var minIndex = i; for (var 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; } ``` 选择排序的时间复杂度同样为 O(n^2)。 归并排序 归并排序是一种分治策略的排序算法，将大问题分解成小问题来解决。它将数组分成两半，分别排序，然后合并两个已排序的子数组。具体步骤如下： 1. 将数组分为两半。 2. 对每一半递归地执行归并排序。 3. 合并两个已排序的子数组。 归并排序的时间复杂度为 O(n log n)，在最坏情况下仍保持这个效率。 冒泡排序 冒泡排序也是一种简单的排序算法，它重复地遍历待排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 冒泡排序的JavaScript实现如下： ```javascript function bubbleSort(arr) { for (var i = 0; i < arr.length - 1; i++) { for (var j = 0; j < arr.length - i - 1; j++) { if (arr[j] > arr[j + 1]) { [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; } } } return arr; } ``` 冒泡排序的时间复杂度为 O(n^2)。 快速排序 快速排序是由C.A.R. Hoare在1960年提出的一种排序算法。它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序。 快速排序的JavaScript实现较为复杂，这里不再详述，但其时间复杂度在平均情况下为 O(n log n)，最坏情况下为 O(n^2)。 以上这些排序算法是前端开发者在面试中经常被问到的基础知识，掌握它们的原理和实现对于提升面试成功率有很大帮助。在实际开发中，可能会根据场景选择更适合的排序算法，例如，如果数据已经部分有序，插入排序可能会更高效；而如果数据量较大，归并排序和快速排序通常有更好的性能。