今天看的这节课，开头他就说full of mathmatics，没有任何有关算法的东西。
所以没什么是可以去实现的，听英语版的数学课对我来说有点难度。
就把昨天写的归并优化一下吧，昨天写的归并其实不是一个特别好的版本，用了很多额外空间和没必要的操作，今天断断续续改了很多个版本，最后一个版本看上去还不错。
首先要做的就是把DeepCopy优化一下，deepCopy是一个O(n)的函数，虽然和mergeArray在一层循环里，整个函数的时间复杂度看上去没有上升，实际上效率的偏低的。
这里用JavaScript特有的，比较方便的，对于没有循环引用的数据结构比较快的深拷贝方法。
const deepCopy = function(obj){
return JSON.parse(JSON.stringify(obj));
}
先转字符串再由字符串转成对象，在不出现循环引用的情况下这个方法相当快且准确。
第二，这个方法不是原地的，可以发现最后方法有一个返回值，而数组本身并没有被改变，所以也不合适写在原型链里，所以就把这个直接写成了一个function。
const mergeSort = function(source){
// 内容
}
后来希望不去做深拷贝，直接对mergeList做操作就行了，但最早使用深拷贝就是因为会有空数组残留，一开始想了个土办法
while(mergeList[0].length!==source.length){
for(let i = 0; i<source.length;i++){
mergeList[0]=mergeArray(mergeList[0],mergeList[i]);
}
}
然后发觉这方法根本不就是插入排序吗？一点都不归并。最后想到，可以通过array.length = n来截断最后的空数组，这个循环最后就成了
while(mergeList.length>1){
for(let i = 0; i<Math.floor(mergeList.length/2);i++){
mergeList[i]=mergeArray(mergeList[i],mergeList[mergeList.length-1-i]);
}
mergeList.length = Math.ceil(mergeList.length/2);
}
最后非原地排序的版本就成了
mergeSort = function(source){
const mergeArray = function(left,right){
var result = [];
while(left.length * right.length > 0){
left[0]>right[0]?result.push(right[0]):result.push(left[0]);
}
result = result.concat(left,right);
if(left.length) left.length = 0;
if(right.length) right.length = 0;
return result;
}
var mergeList = [];
for(let i = 0;i<source.length;i++){
var temp = [];
temp.push(source[i])
mergeList.push(temp);
}
while(mergeList.length>1){
for(let i = 0; i<Math.floor(mergeList.length/2);i++){
mergeList[i]=mergeArray(mergeList[i],mergeList[mergeList.length-1-i]);
}
mergeList.length = Math.ceil(mergeList.length/2);
}
return mergeList[0];
}
但是我还有最后的倔强，我一定要写一个原地的版本
原地版本主要问题在于我需要一个数组进行开始，第二我必须在this内部操作，在js中直接给this赋值是不合法的。
最后修改版本如下，我对这个版本的满意度不如上一个版本，不过暂时不知道怎么改良了。
Array.prototype.mergeSort = function () {
var mergeArray = function (arr1, arr2) {
var result = [];
if (!(arr1 instanceof Array)) {
arr1 = [arr1];
}
if (!(arr2 instanceof Array)) {
arr2 = [arr2];
}
while (arr1.length * arr2.length > 0) {
if (arr1[0] > arr2[0]) {
result.push(arr2.shift());
} else {
result.push(arr1.shift());
}
}
result = result.concat(arr1, arr2)
if (arr1.length > 0) {
arr1.length = 0;
}
if (arr1.length > 0) {
arr1.length = 0;
}
return result;
}
while (this.length > 1) {
for (let i = 0; i < Math.floor(this.length / 2); i++) {
this[i] = mergeArray(this[i], this[this.length - 1 - i]);
}
this.length = Math.ceil(this.length / 2);
}
for (var i = 1; i <= this[0].length; i++) {
this[i] = this[0][i - 1];
}
this.shift();
}
第一个问题通过修改了mergeArray方法实现，如果传入的元素不是Array类型的，就新建一个长度为1的Array并把这个元素加入进去。
这样我就不需要一个额外的mergeList来把每个单一的元素转换成为长度为一的数组了。
非原地的没有用这个方法来处理因为我不想在非原地的算法里改变输入的值。
第二个问题就解决的偏土了，虽然说没有了额外的空间，但是源数组却成为一个长度为1，第一项是排序结果数组的数组数组。
这时候就需要把里面所有的值拿出来按顺序然后放到源数组中，做完后再把源数组的第一项，数组数组给shift出去，最后的源数组就是排序后的数组。
网友评论