数组排序的艺术在编程领域至关重要，因为它可以有效地组织和操作数据。当谈到实现可靠的排序算法时，插入排序成为一种通用且有效的选择。在本文中，我们深入研究 JavaScript 的复杂世界，探索实现插入排序以按升序排列数字数组的过程。通过理解该算法的基本机制并利用 JavaScript 的强大功能，开发人员可以释放有效排序和组织数值数据的潜力，从而提高应用程序的性能和可用性。
问题陈述
当前的挑战涉及利用 JavaScript 实现插入排序算法的任务，以便按升序排列数字数组。主要目标是设计一个程序，可以智能地重新排列给定数组的元素，确保每个后续元素根据其数值放置在相对于前面元素的正确位置。举个例子，假设我们提供了一个数组
[9, 2, 7, 4, 1]
执行插入排序算法后，预期结果将是一个遵循递增顺序的数组，例如
[1, 2, 4, 7, 9]
方法
在本文中，我们将看到多种不同的方法来解决 JavaScript 中的上述问题 -
立即学习“Java免费学习笔记（深入）”；
基本插入排序
二进制插入排序
递归插入排序
方法一：基本插入排序
基本插入排序算法在数组中维护一个已排序的子数组。从第二个元素开始，每个元素与子数组中的前一个元素进行比较，如果较小则向右移动。此过程将持续进行，直到找到正确的位置并插入该元素。对所有元素重复此过程，从而产生完全排序的数组。
示例
insertionSort 函数将数组 arr 作为输入，并返回使用插入排序算法排序的数组。它从第二个元素开始迭代，并将其存储在当前变量中。 while 循环将当前元素与已排序子数组中的先前元素进行比较，将较大的元素向右移动。循环继续，直到到达数组的开头或找到更小的元素。然后将当前元素插入到已排序子数组中的正确位置。对所有元素重复此过程，从而产生排序数组。
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let current = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
return arr;
}
const arr = [9, 2, 7, 4, 1];
console.log(insertionSort(arr));
输出
以下是控制台输出 -
[ 1, 2, 4, 7, 9 ]
方法二：二分插入排序
二分插入排序算法通过在已排序的子数组中利用二分搜索来确定每个元素的正确位置，从而提高了基本插入排序的效率。不是线性搜索，而是通过将当前元素与子数组的中间元素进行比较来执行二分搜索，并相应地调整搜索边界。确定插入点后，将向右移动元素以腾出空间，然后插入当前元素。对所有元素重复此过程，从而产生完全排序的数组。
示例
binaryInsertionSort 函数采用数组 arr 并返回使用二进制插入排序算法排序的数组。它从第二个元素开始迭代，假设第一个元素已排序。当前元素存储在当前变量中。该算法在已排序的子数组中执行二分搜索，通过将当前元素与中间元素进行比较并调整搜索边界来找到当前元素的正确位置。一旦找到位置，算法就会将元素向右移动并将当前元素插入到正确的位置。对所有元素重复此过程，从而产生排序数组。
function binaryInsertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let current = arr[i];
let left = 0;
let right = i - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (current < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
for (let j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = current;
}
return arr;
}
const arr = [9, 2, 7, 4, 1];
console.log(binaryInsertionSort(arr));
输出
以下是控制台输出 -
[ 1, 2, 4, 7, 9 ]
方法三：递归插入排序
递归插入排序算法是插入排序的递归版本，使用递归对数组进行排序。对于大小为 1 或更小的子数组，它认为它们已经排序。对于较大的子数组，它会递归调用自身来对没有最后一个元素的子数组进行排序。递归调用返回并对子数组进行排序后，算法将最后一个元素放置在已排序子数组中的正确位置。这是通过将最后一个元素与已排序子数组中的元素进行比较并在必要时将它们向右移动来实现的。重复该过程，直到所有元素都插入到正确的位置，从而形成完全排序的数组。
示例
recursiveInsertionSort 函数递归地将插入排序算法应用于输入数组。它检查数组是否已经排序，如果是则返回。否则，它会在大小为 n - 1 的子数组上递归调用自身。递归调用后，该函数使用 while 循环将最后一个元素与已排序子数组中的元素进行比较。如果某个元素较大，则会将其向右移动。此过程持续进行，直到循环到达数组的开头或找到更小的元素。最后，最后一个元素被插入到正确的位置。对所有元素重复此过程，从而产生排序数组。
function recursiveInsertionSort(arr, n = arr.length) {
if (n <= 1) return arr;
recursiveInsertionSort(arr, n - 1);
let last = arr[n - 1];
let j = n - 2;
while (j >= 0 && arr[j] > last) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = last;
return arr;
}
const arr = [9, 2, 7, 4, 1];
console.log(recursiveInsertionSort(arr));
输出
以下是控制台输出 -
[ 1, 2, 4, 7, 9 ]
结论
最终，使用 JavaScript 实现插入排序算法以升序排列数字数组，对于寻求熟练排序方法的开发人员来说是一个精明的选择。通过迭代地将元素放置在适当的位置，该算法展示了一种组织数值数据的敏锐方法。虽然插入排序可能不像其他排序技术那样广受好评，但它的效率和简单性使其在某些情况下成为非常宝贵的工具。在 JavaScript 中使用此算法使开发人员能够在其编码库中使用鲜为人知但功能强大的工具，从而生成精简且有序的数组。总之，利用 JavaScript 中插入排序算法的强大功能，对于那些在数组排序中寻求精确性和优雅性的人来说，是一种不切实际的努力。
