您的数据集是否分类将直接影响您可以使用的搜索方法,并可能意味着搜索需要一百万次操作或需要10次操作之间的差异,就像 二进制搜索一样。
为了简单,我们只会专注于从最小到最大的数组的排序,但这些算法可以很容易地对其他排序目标进行修改. 请记住,这些是更一般的概念和模式,而不是如何对数据的排序,因为您的具体实施可能有所不同,但最终可能在概念上类似于这些模式。
这里是50个随机数字的练习数组。
1const unsortedArr = [31, 27, 28, 42, 13, 8, 11, 30, 17, 41, 15, 43, 1, 36, 9, 16, 20, 35, 48, 37, 7, 26, 34, 21, 22, 6, 29, 32, 49, 10, 12, 19, 24, 38, 5, 14, 44, 40, 3, 50, 46, 25, 18, 33, 47, 4, 45, 39, 23, 2];
前提条件
我将通过Big O Notation(LINK0)的镜头来观察一切,所以了解复杂性随着时间的推移而增加是非常有帮助的。
黑色泡沫
这是排序方法的Hello World,没有什么疯狂的,但它完成了工作。
对于数组中的每一个项目,我们要检查下一个项目是否更大,如果是,那么在数组中交换他们的索引。为了避免重组排序的数字,我们将从数组的后面开始,而另一个为循环得到前面的数字。
图形 / 动画 通过 VisuAlgo.net
**我们的版本与动画相反,但它足够接近。
1const bubble = arr => {
2 const swap = (list, a, b) => [list[a], list[b]] = [list[b], list[a]];
3
4 for (let i = arr.length; i > 0; i--) {
5 for (let j = 0; j < i - 1; j++) {
6 if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);
7 };
8 };
9
10 return arr;
11};
12
13console.log(bubble(unsortedArr));
黑色选择
选择排序工作与泡沫排序相反,而泡沫排序正在将所有最大值推到尽头,现在我们将把最低值推到起点。
每次它跨越数组时,它会选择最小的值,如果它找到一个较低的值,那么它就会成为新的最低值。当循环完成时,它会采取最低值,并将其放在数组的前面,然后重新开始循环。
图形 / 动画 通过 VisuAlgo.net
1const selection = arr => {
2 const swap = (list, a, b) => [list[a], list[b]] = [list[b], list[a]];
3
4 arr.forEach((item, i) => {
5 let min = i;
6 for (let j = i + 1; j < arr.length; j++) {
7 if (arr[j] < arr[min]) min = j;
8 };
9 swap(arr, i, min);
10 });
11
12 return arr;
13};
14
15console.log(selection(unsortedArr));
黑色插入
我个人最喜欢的和最出色的三种,插入类型,更像是如何将某些东西按手进行排序。
我们将数组视为两个部分,排序和不排序,每次我们找到一个新的值,我们会回旋,以便在排序的一半中找到它的位置。
图形 / 动画 通过 VisuAlgo.net
1const insertion = arr => {
2 arr.forEach((item, i) => {
3 let num = arr[i];
4 let j;
5
6 for (j = i - 1; j >= 0 && arr[j] > num; j--) {
7 arr[j + 1] = arr[j];
8 };
9 arr[j + 1] = num;
10 });
11
12 return arr;
13};
14
15console.log(insertion(unsortedArr));
比较
使用Big O Notation来比较算法的一个问题是,它基于最坏情况的场景,这在算法上可能是一样的,这给出了错误的幻觉,即它们是平等的。
插入排序每次都获胜,它也有不需要在开始之前拥有整个数组的优点,这允许您在数据输入时实时排序事物。
** 记住这一点,因为在考虑您的数据已经如何组织之前,您不应该决定哪个算法是最好的。
结论
这三种解决方案远远不是高效地分类大量数据的最佳解决方案,但它们是最直观的解决方案之一,可以将你的手指沉浸在一个压倒性的海洋中。