排序算法汇总
1. 冒泡排序
思想
从数组的第一项开始，一次和后面的每一项相比较，如果比较的项大于第一项的值则将两者交换位置，直到数组中所有的数都比较一遍位置，然后开始下一轮循环；
注意的点：
- 每一轮完成一轮比较都会归位一个数字，因此只用归位 length-1 个数字那么整个数组的排序就完成了。因此只用循环 length-1 次；
- 每一轮比较的时候因为不用和自己比较，只用和数组中剩下的 length-1 项进行比较即可。因此每一轮比较只用比较 length-1 次；
- 在每一轮比较中如果从头到尾都没有需要交换位置的操作发生的话，则说明数组已经是排好序的状态了，可以终止循环。因此可以用一个 flag 标志位来记录是否发生过换位操作，可以根据 flag 判断是否退出循环；
代码
Array.prototype.bubble = function bubble() {
// 外层循环I控制比较的轮数
let flag = true;
for (let i = 0; i < this.length - 1; i++) {
// 里层循环控制每一轮比较的次数J
for (let j = 0; j < this.length - 1 - i; j++) {
if (this[j] > this[j + 1]) {
// 当前项大于后一项，交换位置
const temp = this[j];
this[j] = this[j + 1];
this[j + 1] = temp;
flag = false;
}
}
if (flag) {
break;
}
}
return this;
};
let array = [12, 8, 24, 16, 1];
array.bubble();
console.log(array);2. 选择排序
思想
第一轮先假设第一项是最小的值，然后将最小值与后面的每一项相比较，找出最小的值将其位置与第一项交换；然后进行下一轮循环，假设第二项是最小的值……
注意的点：
- 每一轮完成一轮比较都会归位一个数字，因此只用归位 length-1 个数字那么整个数组的排序就完成了。因此只用循环 length-1 次；
代码
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
Array.prototype.select = function select() {
for (let j = 0; j < this.length - 1; j++) {
let min = j;
// 找到比当前项还小的这一项索引
for (let i = min + 1; i < this.length; i++) {
if (this[i] < this[min]) {
min = i;
}
}
// 让最小的项和当前首位交换位置
swap(this, min, j);
}
return this;
};
let array = [12, 8, 24, 16, 1];
array.select();
console.log(array);3. 插入排序
思想
类似于玩扑克牌拿牌时的情景：
1、首先拿到第一张牌放到第一位；
2、拿下一张牌，跟手中已经拿到的牌从后往前比较，插到比他小的第一张牌后，如果没有则插到第一项；
3、拿第三张牌……
代码
// 这个方法会返回一个新数组，更加耗内存
Array.prototype.insert = function insert() {
// 1.准备一个新数组，用来存储抓到手里的牌，开始先抓一张牌进来
let handle = [];
handle.push(this[0]);
// 2.从第二项开始依次抓牌，一直到把台面上的牌抓光
for (let i = 1; i < this.length; i++) {
// A是新抓的牌
let A = this[i];
// 和HANDDLE手里的牌依次比较（从后向前比）
for (let j = handle.length - 1; j >= 0; j--) {
// 每一次要比较的手里的牌
let B = handle[j];
// 如果当前新牌A比要比较的牌B大了，把A放到B的后面
if (A > B) {
handle.splice(j + 1, 0, A);
break;
}
// 已经比到第一项，我们把新牌放到手中最前面即可
if (j === 0) {
handle.unshift(A);
}
}
}
return handle;
};
let ary = [12, 8, 24, 16, 1];
const newAry = ary.insert();
console.log(newAry);
// 此种方法是在原数组上操作，不耗内存
Array.prototype.insert = function insert() {
for (let i = 1; i < this.length; i++) {
let temp = this[i];
let j = i - 1;
for (; j >= 0; j--) {
if (temp >= this[j]) break;
this[j + 1] = this[j];
}
this[j + 1] = temp;
}
return this;
};
let ary2 = [12, 8, 24, 16, 1];
ary2.insert();
console.log(ary2);4. 希尔排序
思想
- 第一轮循环时 gap 为 length / 2，数组中的第 i 项和第 i+gap 项比较，如果第 i 项>第 i+gap 项的值，则将两者的位置交换；
- 第二轮循环 gap 为上一轮 gap 的 1/2，后面操作同上一轮；
- 直到 gap 为 0 为止；
代码
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
Array.prototype.shell = function shell() {
let gap = Math.floor(this.length / 2);
while (gap >= 1) {
for (let i = gap; i < this.length; i++) {
while (i - gap >= 0 && this[i] < this[i - gap]) {
swap(this, i, i - gap);
i = i - gap;
}
}
gap = Math.floor(gap / 2);
}
};
let arr = [58, 23, 67, 36, 40, 46, 35, 28, 20, 10];
arr.shell();
console.log(arr);5. 快速排序
思想
一般而言快排的思想是：
- 找到数组的中间项，在原有的数组中把它移除;
- 准备左右两个数组，循环剩下数组中的每一项，比当前项小的放到左边数组中，反之放到右边数组中;
- 递归方式让左右两边的数组持续这样处理，一直到左右两边都排好序为止（最后让左边+中间+右边拼接成为最后的结果）
代码
// 实现方式一
function quick(nums) {
if (nums.length <= 1) {
return nums;
}
let middleIndex = Math.floor(nums.length / 2);
let middleValue = nums.splice(middleIndex, 1)[0];
let aryLeft = [],
aryRight = [];
for (let i = 0; i < nums.length; i++) {
let item = nums[i];
item < middleValue ? aryLeft.push(item) : aryRight.push(item);
}
return quick(aryLeft).concat(middleValue, quick(aryRight));
}
// 实现方式二
function quick(nums) {
if (nums.length < 2) return nums;
return quickSort(nums, 0, nums.length - 1);
}
function quickSort(nums, left, right) {
if (left >= right) return;
let pivotIndex = partition(nums, left, right);
quickSort(nums, left, pivotIndex - 1);
quickSort(nums, pivotIndex + 1, right);
return nums;
}
function partition(nums, left, right) {
let pivot = right;
let leftIndex = left;
for (let i = left; i < right; i++) {
if (nums[i] < nums[pivot]) {
[nums[leftIndex], nums[i]] = [nums[i], nums[leftIndex]];
leftIndex++;
}
}
[nums[leftIndex], nums[pivot]] = [nums[pivot], nums[leftIndex]];
return leftIndex;
}
let ary = [12, 8, 15, 16, 1, 24];
console.log(quick(ary));6. 归并排序
思想
基本思想与过程：先递归的分解数列，再合并数列（分治思想的典型应用）
- 将一个数组拆成 A、B 两个小组，两个小组继续拆，直到每个小组只有一个元素为止。
- 按照拆分过程逐步合并小组，由于各小组初始只有一个元素，可以看做小组内部是有序的，合并小组可以被看做是合并两个有序数组的过程。
- 对左右两个小数列重复第二步，直至各区间只有 1 个数。
代码
function Merger(a, b) {
let n = a && a.length;
let m = b && b.length;
let c = [];
let i = 0,
j = 0;
while (i < n && j < m) {
if (a[i] < b[j]) c.push(a[i++]);
else c.push(b[j++]);
}
while (i < n) c.push(a[i++]);
while (j < m) c.push(b[j++]);
return c;
}
function merge_sort(arr) {
if (arr.length == 1) return arr;
let mid = Math.floor(arr.length / 2);
let left = arr.slice(0, mid);
let right = arr.slice(mid);
return Merger(merge_sort(left), merge_sort(right)); //合并左右部分
}
let array = [12, 8, 15, 16, 1, 24];
console.log(merge_sort(array));
