1. arr.sort(fn)
// 升序排序
arr.sort((a, b) => a - b);
// 降序排序
arr.sort((a, b) => b - a);2. 冒泡排序
冒泡排序-升序原理:
eg: [1, 6, 7, 9, 10, 3, 4, 5, 2]
1) 先遍历第一遍数组, 前一个数字大于后一个数字, 就交换位置, 最后最大值10放在数组的最后, 此时是 [1, 6, 7, 9, 3, 4, 5, 2, 10];
for (let j = 0; j < arr.length-1; j++) {
preNum = arr[j];
const nextNum = arr[j + 1];
if (preNum > nextNum) { // 左边的数字大于右边的数字,交换位置
// 数字小的往前挪, 数字大的往后挪
arr[j] = nextNum;
arr[j + 1] = preNum;
}
}
2) 第二遍就是: 前一个数字大于后一个数字, 就交换位置, 最后第二大的值放在数组的倒数第二位, 此时是 [1, 6, 7, 3, 4, 5, 2, 9, 10];
for (let j = 0; j < arr.length-2; j++) {
preNum = arr[j];
const nextNum = arr[j + 1];
if (preNum > nextNum) { // 左边的数字大于右边的数字,交换位置
// 数字小的往前挪, 数字大的往后挪
arr[j] = nextNum;
arr[j + 1] = preNum;
}
}
3) 第三遍就是: 前一个数字大于后一个数字, 就交换位置, 最后第三大的值放在数组的倒数第三位, 此时是 [1, 6, 3, 4, 5, 2, 7, 9, 10];
for (let j = 0; j < arr.length-3; j++) {...}
以此类推...
4) 最后一遍: 前一个数字大于后一个数字, 就交换位置, 最后第2小的值放在数组的第2位, 此时是 [1, 2, 3, 4, 5, 6, 7, 9, 10]
for (let j = 0; j < 1; j++) {...}
5) 因为for (let j = 0; j < x; j++) {...}; 推导可知x的值范围是(0, arr.length-1];
所以:
for (let j = arr.length - 1; i > 0; i--) {
for (let j = 0; j < i; j++) {...}
}
排序.js:14 第1次计算:
- (9) [1, 6, 7, 9, 3, 4, 5, 2, 10]
排序.js:14 第2次计算:
- (9) [1, 6, 7, 3, 4, 5, 2, 9, 10]
排序.js:14 第3次计算:
- (9) [1, 6, 3, 4, 5, 2, 7, 9, 10]
排序.js:14 第4次计算:
- (9) [1, 3, 4, 5, 2, 6, 7, 9, 10]
排序.js:14 第5次计算:
- (9) [1, 3, 4, 2, 5, 6, 7, 9, 10]
排序.js:14 第6次计算:
- (9) [1, 3, 2, 4, 5, 6, 7, 9, 10]
排序.js:14 第7次计算:
- (9) [1, 2, 3, 4, 5, 6, 7, 9, 10]
排序.js:14 第8次计算:
- (9) [1, 2, 3, 4, 5, 6, 7, 9, 10]
最后一次不用计算了, 最小值就是1
[1, 2, 3, 4, 5, 6, 7, 9, 10]
冒泡排序--普通双层遍历循环版本:
// 冒泡排序-升序
const bubleSort = (arr) => {
let preNum = null;
// 之所以i>0, 因为排序交互位置到最后两个的时候, 只需要比较一次就行了, 最后那个数字不必比较了
for (let i = arr.length - 1; i > 0; i--) {
for (let j = 0; j < i; j++) {
preNum = arr[j];
const nextNum = arr[j + 1];
if (preNum > nextNum) { // 左边的数字大于右边的数字,交换位置
// 数字小的往前挪, 数字大的往后挪
arr[j] = nextNum;
arr[j + 1] = preNum;
}
}
}
return arr;
}
// 冒泡排序-降序
const bubleSort = (arr) => {
let preNum = null;
// 之所以i>0, 因为排序交互位置到最后两个的时候, 只需要比较一次就行了, 最后那个数字不必比较了
for (let i = arr.length - 1; i > 0; i--) {
for (let j = 0; j < i; j++) {
preNum = arr[j];
const nextNum = arr[j + 1];
if (preNum < nextNum) { // 左边的数字小于右边的数字,交换位置
// 数字大的往前挪, 数字小的往后挪
arr[j] = nextNum;
arr[j + 1] = preNum;
}
}
}
return arr;
}冒泡排序-升序-递归
// 冒泡排序-升序
const bubleSort0 = (arr, i = arr.length - 1) => {
let preNum = null;
// 之所以i>0, 因为排序交互位置到最后两个的时候, 只需要比较一次就行了, 最后那个数字不必比较了
for (let j = 0; j < i; j++) {
preNum = arr[j];
const nextNum = arr[j + 1];
if (preNum > nextNum) { // 左边的数字大于右边的数字,交换位置
// 数字小的往前挪, 数字大的往后挪
arr[j] = nextNum;
arr[j + 1] = preNum;
}
}
i--;
if (i > 0) return bubleSort0(arr, i);
return arr
}
// 冒泡(升序排序)
var arr = bubleSort0([1, 6, 7, 9, 10, 3, 4, 5, 2])
console.log(arr, '冒泡排序-升序-递归');
// 冒泡排序-降序
const bubleSort0 = (arr, i = arr.length - 1) => {
let preNum = null;
// 之所以i>0, 因为排序交互位置到最后两个的时候, 只需要比较一次就行了, 最后那个数字不必比较了
for (let j = 0; j < i; j++) {
preNum = arr[j];
const nextNum = arr[j + 1];
if (preNum < nextNum) { // 左边的数字小于右边的数字,交换位置
// 数字大的往前挪, 数字小的往后挪
arr[j] = nextNum;
arr[j + 1] = preNum;
}
}
i--;
if (i > 0) return bubleSort0(arr, i);
return arr
}
// 冒泡(降序排序)
var arr = bubleSort0([1, 6, 7, 9, 10, 3, 4, 5, 2])
console.log(arr, '冒泡排序-升序-递归');3. 选择排序
eg: [6, 7, 9, 10, 3, 4, 5, 2, 1]
当i等于0时:
1) min=第一个元素6, 和数组其余的元素比较, 原本的第一位元素6在if (nextNum < preNum){...}中6和第一个比6小的元素3交换了位置,此时是[3, 7, 9, 10, 6, 4, 5, 2, 1];
2) min变成3, 比3小的第一个元素是2, 此时是[2, 7, 9, 10, 6, 4, 5, 3, 1];
3) min变成2, 比2小的元素是1, 所以交换位置, 此时是[1, 7, 9, 10, 6, 4, 5, 3, 2];
5) 往右数没有比1小的元素了, 结束
当i等于1时:
1) min=数组第二个元素7, 和第三个及之后的元素比较, 第一个比7小的元素是6, 交换位置, 此时是: [1, 6, 9, 10, 7, 4, 5, 3, 2];
2) min变成6, 比6小的第一个元素是4, 此时是[1, 4, 9, 10, 7, 6, 5, 3, 2];
3) min变成4, 比4小的第一个元素是3, 此时是[1, 3, 9, 10, 7, 6, 5, 4, 2];
4) min变成3, 比3小的第一个元素是2, 此时是[1, 2, 9, 10, 7, 6, 5, 4, 3];
5) 往右数没有比2小的元素了, 结束
当i等于2时:
1) min等于数组第三个元素9, 和第四个及之后的元素比较, 第一个比9小的元素是7, 此时是[1, 2, 7, 10, 9, 6, 5, 4, 3];
2) min变成7, 比7小的第一个元素是6, 此时是[1, 2, 6, 10, 9, 7, 5, 4, 3];
3) min变成6, 比7小的第一个元素是5, 此时是[1, 2, 5, 10, 9, 7, 6, 4, 3];
4) min变成5, 比7小的第一个元素是4, 此时是[1, 2, 4, 10, 9, 7, 6, 5, 3];
5) min变成4, 比4小的第一个元素是3, 此时是[1, 2, 3, 10, 9, 7, 6, 5, 4];
5) 往右数没有比3小的元素了, 结束
以此类推...
所以:
// 小的越来越靠左, 以此类推
/**
* 选择排序:
原理: 给每个位置选择当前元素最小的;
* 比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，
* 直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。
* 选择排序的本质: 每一次大循环就是选出最小的那个值，在选最小值的过程你可以通过下标记录
* 也可以每次交换值都可以
*/
选择排序-双层遍历版本:
// 选择排序-升序
const selectSort = arr => {
const len = arr.length;
for (let i = 0; i < len; i++) {
let min = arr[i];
for (let j = i + 1; j < len; j++) {
const nextNum = arr[j];
const preNum = min;
// 如果当前的值比记录的最小值还要小, 就交换这2个数字的位置
if (nextNum < preNum) {
arr[j] = preNum;
min = nextNum; // min被赋值为比较出来的较小值
continue;
}
}
arr[i] = min; // 因为min在内循环被修改了, 所以arr[i]的值应该在跳出内循环后在它自身循环体被修改
}
return arr
}
// 选择(升序排序)
var arr = selectSort([6, 7, 9, 10, 3, 4, 5, 2, 1])
console.log(arr, '选择排序-升序');选择排序-递归+for循环
// 选择排序
const selectSort0 = (arr, i=0) => {
const len = arr.length;
let min = arr[i];
for (let j = i + 1; j < len; j++) {
const nextNum = arr[j];
const preNum = min;
console.log(preNum, 'preNum=====')
// 如果当前的值比记录的最小值还要小, 就交换这2个数字的位置
if (nextNum < preNum) {
arr[j] = preNum;
min = nextNum; // min被赋值为比较出来的较小值
continue;
}
}
arr[i] = min; // 因为min在内循环被修改了, 所以arr[i]的值应该在跳出内循环后在它自身循环体被修改
i++;
if(i<=2) selectSort0(arr, i);
return arr
}
// 选择(升序排序)
var arr = selectSort0([6, 7, 9, 10, 3, 4, 5, 2, 1])
console.log(arr, '选择排序-升序00000');4. 快速排序:
如果数组的元素个数小于2个, 返回原数组;
如果数组元素个数大于等于2个:
1) flag = 一个标尺元素(一般是第一个元素); left=flag左边的元素组成的数组(初始化); right=flag右边的元素组成的数组(初始化);
2) 遍历arr, 比flag小的push进left数组, 比flag大的push进right数组
3) 将left和right数组执行上述(1)和(2)步骤
4) 使用concat拼接left数组, flag, right数组
快速排序-for循环+递归+concat
// 快速排序
const quickSort = (arr) => {
const len = arr.length;
if (len < 2) {
return arr;
}
// 选择标尺元素
let flag = arr[0];
let left = [];
let right = [];
let preNum = null;
// 因为flag取的是下标0的元素, 所以遍历从下标1开始
for (let i = 1; i < len; i++) {
preNum = arr[i];
if (preNum < flag) {
// 比flag小的放左边
left.push(preNum);
}
else {
// 比flag大的放右边
right.push(preNum);
}
}
// 进行递归
return quickSort(left).concat(flag, quickSort(right));
}快速排序-划分交换in-place
// 快速排列in-place(交换)--划分交换排序:
const quickInPlaceSort = (arr) => {
// 数组指定两个位置进行值交换
let exchange = (arr, i, j) => {
const preNum = arr[i];
const nextNum = arr[j];
arr[i] = nextNum;
arr[j] = preNum;
}
// 完成一次划分交换
let findCenter = (arr, leftIdx, rightIdx) => {
let flag = arr[leftIdx];
let centerIdx = leftIdx + 1;
for (let i = centerIdx; i <= rightIdx; i++) {
if (arr[i] < flag) {
exchange(arr, centerIdx, i); // 交换位置
centerIdx++; // 交换的下标+1
}
}
exchange(arr, leftIdx, centerIdx - 1);
return centerIdx;
}
// 递归排序
let sort = (arr, leftIdx, rightIdx) => {
if (leftIdx < rightIdx) {
let center = findCenter(arr, leftIdx, rightIdx);
sort(arr, leftIdx, center - 1);
sort(arr, center, rightIdx);
}
}
sort(arr, 0, arr.length - 1);
return arr;
}
var arr = quickInPlaceSort([1, 6, 7, 9, 10, 3, 4, 5, 2]);
console.log(arr, '快速排序-升序-划分交换'); // [1, 2, 3, 4, 5, 6, 7, 9, 10] '快速排序-升序-划分交换'
console.log('-----------------------------------------');