冒泡排序

Array.prototype.sort()这个API的排序原理是什么？

```const str_arr = ['2', '0', '1', '9', '19', '97', '6', '1', '3'];
const num_arr = [2, 0, 1, 9, 19, 97, 6, 1, 3];

// Array.prototype.sort
console.log('====Array.prototype.sort====');
console.log('str_arr sort before: %s', str_arr.toString());
console.log('str_arr sort after: %s', str_arr.sort().toString()); //str_arr sort after: 0,1,1,19,2,3,6,9,97
console.log('num_arr sort before: %s', num_arr.toString());
console.log('num_arr sort after: %s', num_arr.sort().toString()); //num_arr sort after: 0,1,1,19,2,3,6,9,97
console.log('====Array.prototype.sort====');```

`arr.sort([compareFunction])`,sort这个函数支持传入一个比较函数，里面可以接受两个参数a和b，即用于比较的元素，如果大于0表示 b 会被排列到 a 之前， 如果等于0，表示a和b位置不变，如果小于0，表示a排在b前面。既然是这样，那事情就好办了。

```const str_arr = ['2', '0', '1', '9', '19', '97', '6', '1', '3'];
const num_arr = [2, 0, 1, 9, 19, 97, 6, 1, 3];
// Array.prototype.sort: fix 0 相等、 -1 小于 1 大于
console.log('====Array.prototype.sort====');
console.log('str_arr sort before: %s', str_arr.toString());
console.log('str_arr sort after: %s', str_arr.sort((a, b) => a -b).toString()); //str_arr sort after: 0,1,1,2,3,6,9,19,97
console.log('num_arr sort before: %s', num_arr.toString());
console.log('num_arr sort after: %s', num_arr.sort((a, b) => a -b).toString()); //num_arr sort after: 0,1,1,2,3,6,9,19,97
console.log('====Array.prototype.sort====');```

实现一个冒泡排序

```function bubble(arr, asc = true) {
const len = arr.length;
let tmp = null;
for (let i = 0; i < len; i++) {
for (let j = i + 1; j < len; j++) {
if (asc && arr[i] > arr[j]) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
if (!asc && arr[i] < arr[j]) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
}```

```for (let i = 0; i < len; i++) {
for (let j = 0; j < len -i -1; j++) {
// code
}
}```

如何优化冒泡排序？

```function bubble(arr, asc = true) {
let left = 0;
let right = arr.length - 1;
let flag = true;
while (left < right) {
for (let i = left; i < right; i++) {
if (asc && arr[i] > arr[i + 1]) {
[arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
flag = false;
}
if (!asc && arr[i] < arr[i + 1]) {
[arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
flag = false;
}
}
right--;
for (let i = right; i > left; i--) {
if (asc && arr[i] < arr[i - 1]) {
[arr[i], arr[i - 1]] = [arr[i - 1], arr[i]];
flag = false;
}
if (!asc && arr[i] > arr[i - 1]) {
[arr[i], arr[i - 1]] = [arr[i - 1], arr[i]];
flag = false;
}
}
left++;
}
if (flag) return arr;
}```

问题思考

不增加参数、怎么互换a和b？

加减法(要考虑数字的取值范围，慎用)

```a = a + b;
b = a - b;
a = a - b;```

乘除法(要考虑数字的取值范围，慎用)

```a = a * b;
b = a / b;
a = a / b;```

位运算(异或, 慎用)

```a = a ^ b;
b = a ^ b;
a = a ^ b;```

其他语言不晓得，ES6硬核的解构语法(推荐)

`[a, b] = [b, a];`

参考文献

Array.prototype.sort(MDN): https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

0 条评论

• 选择排序

最近看了一则寓言故事跟童鞋们分享一下，讲的是大山深处的神坑（为了激发大家的想象力，这里我就不画画了，请同学们自行脑补）。事情是这样子的，旁白站在上帝视角抛出一个...

• JS面试押题（20190803）

这周跟大家分享的面试题是“数组去重”。这种题目是个正经一点的厂一般在初试的时候都会让你做到的，频率相当高。曾经统计过差不多有8种不带重复的去重方法，但由于当时数...

• 软件推荐(天若OCR) -- 文字识别，解放重复劳动

今天是软件专场的倒数第90场，跟大家分享的是文字识别工具--天若OCR。下面我们把舞台交给天若OCR，大家掌声欢迎。

• 选择排序

选择排序的思想，每次从剩余元素中最小的元素与当前元素交换，第一次从arr[0]arr[n-1]中选取最小值，与arr[0]交换；第二次从arr[1]arr[n-...

• JavaScript常用排序算法

3、对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

• 团体程序设计天梯赛-练习集 L1-019 谁先倒

划拳是古老中国酒文化的一个有趣的组成部分。酒桌上两人划拳的方法为：每人口中喊出一个数字，同时用手比划出一个数字。如果谁比划出的数字正好等于两人喊出的数字之和，谁...

• 数组中的第K个最大元素

在未排序的数组中找到第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。

• Js实现数组排序

常用排序的Js实现方案，包括原型链方法调用、简单选择排序、冒泡排序、插入排序、快速排序、希尔排序、堆排序、归并排序。

• 浙大版《C语言程序设计（第3版）》题目集 习题9-5 通讯录排序

输入n个朋友的信息，包括姓名、生日、电话号码，本题要求编写程序，按照年龄从大到小的顺序依次输出通讯录。题目保证所有人的生日均不相同。