javascript - 什么类型的排序算法与这段代码最相似?(如果有的话)。
问题描述
我正在学习编程(使用 Javascript),作为测试,我决定找到一种方法来编写算法来对字符串进行排序和数组,这就是我想出的。
// test of a sorting algorithm
var steps = 0;
var steps2 = 0;
var array = ['assa', 'erer', 'qwqw', 'ggdffdghdg', 'sdsdethhhghg', 'aaaaaa', 'gthfyjfdsfdf', 'qwqwwere', 'jygyghhf', '1', '0', '345', 'sfsdsddsfsf', 'eee3ew33', '1dwd', 'ddd2'];
var array2 = ['erer', 'jygyghhf', '1', '0', '345', 'sfsdsddsfsf', 'eee3ew33', '1dwd', 'ddd2'];
console.log('array before sort');
console.log(array);
function simpleSort(array) {
let length = array.length;
let currentPos = 1;
while (currentPos < length) {
let pivot = 0;
do {
let currentValue = array[currentPos];
if (currentValue > array[pivot]) {
array.splice(currentPos, 1);
array.splice(pivot, 0, currentValue);
steps++;
}
steps2++;
pivot++;
}
while (currentPos > pivot);
currentPos++;
}
console.log(array);
console.log('steps = ' + steps);
console.log('steps2 = ' + steps2);
}
console.log('********************');
console.log('array after sort');
simpleSort(array);
console.log('********************');
console.log('array after sort with array.sort() and array.reverse() buit in functions');
array.sort();
console.log(array.reverse());
什么类型的排序算法与这段代码最相似,其中的大 O 是什么
解决方案
该算法与以下相同,因此与O(n^2)
排序算法具有相似的结构。
function simpleSort(array) {
for (var currentPos = 1; currentPos < array.length; currentPos++) {
for (var pivot = 0; pivot < currentPos; pivot++) {
let currentValue = array[currentPos];
if (currentValue > array[pivot]) {
array.splice(currentPos, 1);
array.splice(pivot, 0, currentValue);
}
}
}
}
输入[6, 3, 5, 4, 1, 8, 6, 3]
,在每次迭代后,您将拥有:
6 3 5 4 1 8 6 3
6 3 5 4 1 8 6 3
6 5 3 4 1 8 6 3
6 5 4 3 1 8 6 3
6 5 4 3 1 8 6 3
8 6 5 4 3 1 6 3
8 6 6 5 4 3 1 3
8 6 6 5 4 3 3 1
这表明左侧在每一步都被排序,并且每次迭代都会增加一个大小。这与插入排序相同。
每次迭代该if
条件只能为真一次,因为在拼接之后,currentValue
将等于左侧数组中的最小值,并且每次都与较大的值进行比较。所以它具有O(n^2)
时间复杂度。
推荐阅读
- regex - 正则表达式重新否定前瞻不会成功排除多个字符
- java - 使用 Rest Assured 验证 Json 对象中的值
- javascript - Twilio - 在 for 循环中生成访问令牌给了我相同的令牌
- javascript - 如何检查浏览器中的url是否已被iframe更改
- qt - QML 在运行时基于一个切换主题
- c - 在 C 中,如果输入字符串太大,如何产生错误?
- bootstrap-4 - Bootstrap4 日期时间选择器:未捕获的 TypeError:$(...).pickadate 不是函数
- c# - C# - 在后台检测 Keydown 和 KeyUp 事件
- docker - 无法从不同系统连接到 docker 容器 webapp
- c - 从一个结构复制到另一个结构