以下是实现该算法的代码
该算法的操作次数是一个等差数列 n + (n - 1) + (n - 2) + 1 ,去掉常数项以后得出时间复杂度是
O(n * n)
9,选择排序
选择排序的原理如下。遍历数组,设置最小值的索引为 0,如果取出的值比当前最小值小,就替换最小
值索引,遍历完成后,将第一个元素和最小值索引上的值交换。如上操作后,第一个元素就是数组中的
最小值,下次遍历就可以从索引 1 开始重复上述操作。
以下是实现该算法的代码
该算法的操作次数是一个等差数列 n + (n - 1) + (n - 2) + 1 ,去掉常数项以后得出时间复杂度是
O(n * n)
10,归并排序
归并排序的原理如下。递归的将数组两两分开直到最多包含两个元素,然后将数组排序合并,最终合并
为排序好的数组。假设我有一组数组 [3, 1, 2, 8, 9, 7, 6] ,中间数索引是 3,先排序数组 [3,
1, 2, 8] 。在这个左边数组上,继续拆分直到变成数组包含两个元素(如果数组长度是奇数的话,会
有一个拆分数组只包含一个元素)。然后排序数组 [3, 1] 和 [2, 8] ,然后再排序数组 [1, 3, 2,
function insertion(array) {
checkArray(array);
for (let i = 1; i < array.length; i++) {
for (let j = i - 1; j >= 0 && array[j] > array[j + 1]; j--)
swap(array, j, j + 1);
}
return array;
}
<div align="center">
<img src="https://user-gold-cdn.xitu.io/2018/4/13/162bc8ea14567e2e?
w=670&h=508&f=gif&s=965636" width="500" style="display:block;margin: 0 auto" />
</div>
function selection(array) {
checkArray(array);
for (let i = 0; i < array.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < array.length; j++) {
minIndex = array[j] < array[minIndex] ? j : minIndex;
}
swap(array, i, minIndex);
}
return array;
}