大家好，我是拾七，持续给大家补给前端干货🔥
继上篇算法相关知识展开，分享希尔排序、选择排序、归并排序这三类知识。
排序算法 – 希尔排序（ Shell Sort ）
思路
1、先将整个待排序的记录序列分割成若干子序列
2、分别进行直接插入排序
3、待整个序列中的记录基本有序时，再对全体记录进行依次直接插入排序
过程
举个易于理解的例子：[35,33,42,10,14,19,27,44],我们采用间隔4.创建一个位于4个位置间隔的所有值的虚拟子列表。下面这些值是{35,14}, {33, 19}, {42, 27}和{10, 44}.
我们比较每个子列表中的值，并在原始数组中交换它们(如果需要)。完成此步骤后，新数组应如下所示。
然后，我们采用了2的间隔，这个间隔产生两个子列表：{14,27,35,42},{19,10,33,44}
我们比较并交换原始数组中的值（如果需要）。完成此步骤后，数组变成：[14,10,27,19,35,33,42,44], 图如下所示，10与19的位置互换一下。
最后，我们使用值间隔1对数组的其余部分进行排序，shell sort使用插入排序对数组进行排序。
代码实现
const shellSort = arr => {
let len = arr.length,
temp,
gap = 1;
console.time('希尔排序耗时');
while (gap < len / 3) {
//动态定义间隔序列
gap = gap * 3 + 1;
}
for (gap; gap > 0; gap = Math.floor(gap / 3)) {
for (let i = gap; i < len; i++) {
temp = arr[i];
let j = i - gap;
for (; j >= 0 && arr[j] > temp; j -= gap) {
arr[j + gap] = arr[j];
}
arr[j + gap] = temp;
console.log('arr :', arr);
}
}
console.timeEnd('希尔排序耗时');
return arr;
};
分析
1、希尔排序是原地排序算法吗？
希尔排序过程中，只涉及相邻数据的交换操作，只需要常量级的临时空间，空间复杂度为O(1).所以，希尔排序是原地排序算法。
2、希尔排序是稳定的排序算法吗？
单次直接插入排序是稳定的，它不会改变相同元素之间的相对顺序，但在多次不同的插入排序过程中，相同的元素尽可能在各自的插入排序中移动，可能导致相同元素相对顺序发生变化。因此，希尔排序不稳定。
3、希尔排序的时间复杂度是多少？
最佳情况：T(n) = O(nlogn)
最差情况：T(n) = O(nlog2^n)
平均情况：T(n) = O(nlog2^n)
排序算法 – 选择排序（ Selection Sort ）
思路
选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
步骤
1、首先未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2、再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3、重复第二步，直到所有元素均排序完毕。
代码实现
const selectionSort = array => {
const len = array.length;
let minIndex, temp;
for (let i = 0; i < len - 1; i++) {
minIndex = i;
for (let j = i + 1; j < len; j++) {
if (array[j] < array[minIndex]) {
// 寻找最小的数
minIndex = j; // 将最小数的索引保存
}
}
temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
console.log('array: ', array);
}
return array;
};
分析
1、选择排序是原地排序算法吗 ？
选择排序空间复杂度为 O(1)，是一种原地排序算法。
2、选择排序是稳定的排序算法吗 ？
选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。所以，选择排序是一种不稳定的排序算法。
3、 选择排序的时间复杂度是多少 ？
无论是正序还是逆序，选择排序都会遍历 n^2 / 2 次来排序，所以，最佳、最差和平均的复杂度是一样的。
最佳情况：T(n) = O(n^2)。
最差情况：T(n) = O(n^2)。
平均情况：T(n) = O(n^2)。
排序算法 – 归并排序（ Merge Sort ）
思路
排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
归并排序采用的是分治思想。
分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。
代码实现
const mergeSort = arr => {
//采用自上而下的递归方法
const len = arr.length;
if (len < 2) {
return arr;
}
// length >> 1 和 Math.floor(len / 2) 等价
let middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle); // 拆分为两个子数组
return merge(mergeSort(left), mergeSort(right));
};
const merge = (left, right) => {
const result = [];
while (left.length && right.length) {
// 注意: 判断的条件是小于或等于，如果只是小于，那么排序将不稳定.
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length) result.push(left.shift());
while (right.length) result.push(right.shift());
return result;
};
分析
1、归并排序是原地排序算法吗 ？
这是因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。 实际上，尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。 所以，归并排序不是原地排序算法。
2、 归并排序是稳定的排序算法吗 ？
merge 方法里面的 left[0] <= right[0] ，保证了值相同的元素，在合并前后的先后顺序不变。归并排序是稳定的排序方法。
3、归并排序的时间复杂度是多少 ？
从效率上看，归并排序可算是排序算法中的佼佼者。假设数组长度为 n，那么拆分数组共需 logn 步，又每步都是一个普通的合并子数组的过程，时间复杂度为 O(n)，故其综合时间复杂度为 O(nlogn)。
最佳情况：T(n) = O(nlogn)。
最差情况：T(n) = O(nlogn)。
平均情况：T(n) = O(nlogn)。
还有更多算法，点关注收藏，持续更新中 
原文链接：https://juejin.cn/post/7346481513541025827 作者：拾七视界
