常见排序

2023-12-22 25 1

1、冒泡排序

• 比较所有相邻元素，如果第一个比第二个大就交换他们
• 执行一次后可以保证最后一个数字是最大的
• 重复执行 n-1 次，就可以完成排序

Array.prototype.bubbleSort = function () {

for (i = 0; i < this.length - 1; i++) {

for (let j = 0; j < this.length - 1 - i; j++) {

if (this[j] > this[j + 1]) {

// 交换数据

[this[j], this[j + 1]] = [this[j + 1], this[j]];

}

}

}

}

2、选择排序

• 找到数组中最小的值,选中它并放到第一位
• 接着找到数组中第二小的值,选中它并放到第二位
• 重复上述步骤执行 n-1 次

Array.prototype.selectionSort = function () {

for (let i = 0; i < this.length - 1; i++) {

let indexMin = i;

for (let j = i; j < this.length; j++) {

// 如果当前这个元素 小于最小值的下标 就更新最小值的下标

if (this[j] < this[indexMin]) {

indexMin = j;

}

}

// 避免自己和自己进行交换

if (indexMin !== i) {

// 进行交换数据

[this[i], this[indexMin]] = [this[indexMin], this[i]];

}

}

}

3、插入排序

• 从第二个数，开始往前比较
• 如它大就往后排
• 以此类推进行到最后一个数

Array.prototype.insertionSort = function () {

// 遍历数组 从第二个开始

for (let i = 1; i < this.length; i++) {

// 获取第二个元素

const temp = this[i];

let j = i;

while (j > 0) {

// 如果当前元素小于前一个元素 就开始往后移动

if (this[j - 1] > temp) {

this[j] = this[j - 1];

} else {

// 否则就跳出循环

break

}

// 递减

j--;

}

// 前一位置赋值为当前元素

this[j] = temp;

}

}

4、快速排序

• 分区：从数组中任意选择一个 基准， 所有比基准小的元素放在基准前面，比基准大的元素放在基准后面
• 递归： 递归的对基准前后的子数组进行分区

Array.prototype.quickSort = function () {

const rec = (arr) => {

// 如果数组长度小于等于1 就不用排序了

if (arr.length <= 1) { return arr }

// 存放基准前后的数组

const left = [];

const right = [];

// 取基准

const mid = arr[0];

for (let i = 1; i < arr.length; i++) {

// 如果当前值小于基准就放到基准前数组里面

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);

}