排序算法 #15
Description
排序算法的动态执行过程，用这个网站： https://visualgo.net/zh
1.冒泡排序
思路
1.比较所有相邻元素，如果第一个比第二个大，则交换他们
2.一轮下来，可以保证最后一个数的最大的
3.执行n-1轮，就可以完成排序
代码
Array.prototype.bubbleSort = function () {
for (let i = 0; i < this.length - 1; i += 1) {
for (let j = 0; j < this.length - 1 - i; j += 1) {
if (this[j] > this[j + 1]) {
const temp = this[j];
this[j] = this[j + 1];
this[j + 1] = temp;
}
}
}
};
const arr = [5, 4, 3, 2, 1];
arr.bubbleSort();
2.选择排序
思路
1.找到数组中的最小值，选中他并将它放在第一位
2.接着找第二小的值，选中它并将它放在第二位
3.以此类推，执行n-1轮
Array.prototype.selectionSort = function () {
for (let i = 0; i < this.length - 1; i += 1) {
let indexMin = i;
for (let j = i; j < this.length; j += 1) {
if (this[j] < this[indexMin]) {
indexMin = j;
}
}
if (indexMin !== i) {
const temp = this[i];
this[i] = this[indexMin];
this[indexMin] = temp;
}
}
};
const arr = [5, 4, 3, 2, 1];
arr.selectionSort();
3.插入排序
思路
1.从第二个数开始往前比
2.比它大就往后排
3.以此类推
代码
Array.prototype.insertionSort = function () {
for (let i = 1; i < this.length; i += 1) {
const temp = this[i];
let j = i;
while (j > 0) {
if (this[j - 1] > temp) {
this[j] = this[j - 1];
} else {
break;
}
j -= 1;
}
this[j] = temp;
}
};
const arr = [2, 4, 5, 3, 1];
arr.insertionSort();
4.归并排序
思路
1.分，最小分成一个
2.合， 合并有序数组
代码
Array.prototype.mergeSort = function () {
const rec = (arr) => {
if (arr.length === 1) { return arr; }
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid, arr.length);
const orderLeft = rec(left);
const orderRight = rec(right);
const res = [];
while (orderLeft.length || orderRight.length) {
if (orderLeft.length && orderRight.length) {
res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift());
} else if (orderLeft.length) {
res.push(orderLeft.shift());
} else if (orderRight.length) {
res.push(orderRight.shift());
}
}
return res;
};
const res = rec(this); // 这个已经就是排序后的结果了
res.forEach((n, i) => { this[i] = n; }); // 这个是为了修改this的值
};
const arr = [5, 4, 3, 2, 1];
arr.mergeSort();
5.快速排序
思路
1.分区：选择中间一个数作为基准，比这个数小的放前面，大的放后面
2.递归：递归对基准前后的子数组再进行分区
Array.prototype.quickSort = function () {
const rec = (arr) => {
if (arr.length === 1) { return arr; }
const left = [];
const right = [];
const mid = arr[0];
for (let i = 1; i < arr.length; i += 1) {
if (arr[i] < mid) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...rec(left), mid, ...rec(right)];
};
const res = rec(this);
res.forEach((n, i) => { this[i] = n });
};
const arr = [2, 4, 5, 3, 1];
arr.quickSort();