JavaScript - 插入排序算法
插入排序是一种排序算法，它的工作方式与我们玩牌时整理扑克牌的方式非常相似。通过插入排序，可以将元素按排序方式排列。
在该算法中，数组将被虚拟地分为两个部分：已排序部分和未排序部分。未排序部分中的值将被挑选出来，并放置到满足排序顺序的正确位置。
插入排序是一种简单算法，实现起来也很简单。通常，该算法对于少量数据值很高效。它适用于已经部分排序的数据集。
插入排序的工作原理？
考虑一个包含随机顺序元素的数组，这些元素尚未排序。这里我们可以通过执行插入排序来对元素进行排序。下面来看看具体场景。
Input: [24, 22, 26, 10, 12]; Output: [10, 12, 22, 24, 26];
为了了解插入排序的工作方式，假设数组 arr=[24, 22, 26, 10, 12]。
第一遍
- 在插入排序中，首先比较数组中的前两个元素。
- 这里 22 小于 24，因此它们不是升序，24 不在正确位置。所以交换 22 和 24。现在 24 被存储到子数组中。
第二遍
- 现在，比较数组中的接下来的两个元素。
- 这里，元素 24 和 26 是升序的，因为 26 大于 24。因此不会发生交换。
- 24 也与 22 一起存储到子数组中。
第三遍
- 目前子数组中有两个元素 22 和 24。
- 现在比较接下来的两个元素 10 和 26。
- 由于 10 小于 26，交换这两个值。
- 即使交换后，10 和 24 仍未排序，因此再次交换。
- 再次，10 和 22 未排序，所以再次交换。
- 现在，10 处于正确位置。
第四遍
- 目前，已排序子数组中的元素是 10、22 和 24。
- 比较接下来的两个元素 26 和 12。
- 由于它们未排序，交换这两个值。
- 现在，12 小于 24。因此交换它们。
- 这里 12 小于 22 且未排序，所以交换它们。
- 现在，12 处于正确位置，整个数组已完美排序。
算法
使用插入排序算法对大小为 n 的数组按升序排序。
- 如果是第一个元素，它已经是排序好的。返回 1。
- 选取下一个元素
- 与已排序子列表中的所有元素比较
- 将已排序子列表中大于待排序值的元素向后移动
- 插入该值
- 重复直到列表排序完成
插入排序实现
以下是插入排序的示例
<!DOCTYPE html>
<html>
<head>
<title>Insertion Sort Algorithm</title>
</head>
<body>
<p id = "demo"></p>
<script>
function insertionSort(arr){
let n = arr.length;
for(let i = 1; i < n; i++){
let current = arr[i];
let j = i-1;
while ((j > -1) && (current < arr[j])) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = current;
}
return arr;
}
let arr = [24, 22, 26, 10, 12];
document.getElementById("demo").innerHTML = insertionSort(arr);
</script>
</body>
输出
让我们看看上述代码片段的输出。
[10, 12, 22, 24, 26]