哪种类型的排序算法与此代码最相似?(如果有的话)

Question

我正在学习编程(使用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 是什么

Answer 1

该算法与以下内容相同，因此它具有与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 

这表明左侧在每一步都经过排序，并且每次迭代的大小都会增加 1。这与插入排序相同。

对于每次迭代，if条件只能为真一次，因为在拼接之后，currentValue将等于左侧数组中的最小值，并且每次都与较大的值进行比较。因此，它O(n^2)时间复杂度。