共计 2939 个字符,预计需要花费 8 分钟才能阅读完成。
1. sort()
sort() 依照 ASCII 字符排序,默认升序。
一般数组
// 数字
var sum = 0;
var numbers = [4, 2, 5, 1, 3];
numbers.sort(function(a, b) {
sum++;
return a - b;
});
console.log(numbers); // 1 2 3 4 5
console.log(sum); // 7
// 字符串
const months = ['March', 'Jan', 'Feb', 'Dec'];
months.sort();
console.log(months); // ['Dec', 'Feb', 'Jan', 'March']
数组对象
var student = [{'name': 'jack', 'age': 18},
{'name': 'apple', 'age': 16},
{'name': 'tony', 'age': 30},
{'name': 'marry', 'age': 8},
]
// 按年龄
student.sort(function (a, b) {return (a.age - b.age)
});
// 按姓名
student.sort(function (a, b) {var nameA = a.name.toUpperCase();
var nameB = b.name.toUpperCase();
if (nameA < nameB) {return -1;}
if (nameA > nameB) {return 1;}
});
2. 冒泡排序
相邻两个数一一比拟,如果前一个数比后一个数小则替换地位。
重点:替换过程须要变量存储较小值 / 较大值
var numbers = [4, 2, 5, 1, 3];
var sum = 0;
function bubbleSort (arr) {
let temp = '';
for (let i = 0; i < arr.length; i++) {for (let j = 0; j < arr.length - 1; j++) {if (arr[j] > arr[j + 1]) {temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
sum++;
}
}
return arr;
};
console.log(bubbleSort(numbers));
console.log(sum) // 20
3. 疾速排序
冒泡排序的改良算法。通过屡次的比拟和替换来实现排序。
重点:需设定分界值,依据分界值将数组分为左右两局部。而后在左右两边一直反复取分界值和分左右局部的操作。
var numbers = [4, 2, 5, 1, 3];
var sum = 0;
function quickSort (arr) {if (arr.length <= 1) {return arr;}
var medianIndex = Math.floor(arr.length / 2); // 合成值索引
var medianValue = arr.splice(medianIndex, 1); // 分界值
var left = [];
var right = [];
for (let i = 0; i < arr.length; i++) {if (arr[i] < medianValue) {left.push(arr[i])
} else {right.push(arr[i])
}
sum++;
}
console.log(medianIndex, medianValue, left, right)
return quickSort(left).concat(medianValue,quickSort(right));
};
console.log(quickSort(numbers));
console.log(sum) // 10
4. 插入排序
假如后面 n-1 的元素曾经排好序,将第 n 个元素插入到后面曾经排好的序列中。
重点:需定义有序序列中最初一个地位,从最初一位开始一直和序列前元素进行比拟,直到找到插入地位。
var numbers = [4, 2, 5, 1, 3];
var sum = 0;
function insertSort(arr) {
// 假如第一个元素曾经排好序
for (let i = 1; i < arr.length; i++) {if (arr[i] < arr[i - 1]) {
// 取出无序序列中须要插入的第 i 个元素
var temp = arr[i];
// 定义有序中的最初一个地位
var j = i - 1;
arr[i] = arr[j];
// 依据序列最初一位,一直循环比拟,找到插入的地位
while(j >= 0 && temp < arr[j]){arr[ j+1] = arr[j];
j--;
sum++;
};
// 插入
arr[j+1] = temp;
}
}
}
console.log(insertSort(numbers));
console.log(sum) // 6
5. 希尔排序
希尔排序是把记录按下标的肯定增量分组,对每组应用间接插入排序算法排序。
希尔排序是插入排序算法的一种更高效的改良版本。
var numbers = [4, 2, 5, 1, 3];
var sum = 0;
function shellSort(arr) {
var len = arr.length;
// 定义距离区间
var fraction = Math.floor(len / 2);
// fraction = Math.floor(fraction / 2) => 循环中一直切割区间
for (fraction; fraction > 0; fraction = Math.floor(fraction / 2)) {
// 以距离值开始遍历
for (var i = fraction; i < len; i++) {
// 如果后面一个大于前面一个
for (var j = i - fraction; j >= 0 && arr[j] > arr[fraction + j]; j -= fraction) {var temp = arr[j];
arr[j] = arr[fraction + j]; // 后移
arr[fraction + j] = temp; // 填补
sum++;
}
}
}
}
console.log(shellSort(numbers));
console.log(sum) // 6
6. 抉择排序
从待排序的数据元素中选出最小 / 最大的一个元素,寄存在序列的起始地位,而后再从残余的未排序元素中寻找到最小 / 最大元素,而后放到已排序的序列的开端。以此类推,直到全副待排序的数据元素的个数为零。
var numbers = [4, 2, 5, 1, 3];
var sum = 0;
function selectionSort(arr) {if (arr == null || arr.length < 2) {return arr;}
for (var i = 0; i < (arr.length - 1); i++) {
let minIndex = i;
for (let j = i + 1; j < arr.length; j++) {minIndex = arr[j] < arr[minIndex] ? j : minIndex;
sum++;
}
let temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
console.log(selectionSort(numbers));
console.log(sum) // 10
7. 比拟
以同一个数组 [4, 2, 5, 1, 3]
不同的办法比拟计算次数。
办法 | 计算次数 | 稳定性 |
---|---|---|
sort() | 7 | |
冒泡排序 | 20 | 稳固 |
疾速排序 | 10 | 不稳固 |
插入排序 | 6 | 稳固 |
希尔排序 | 6 | 不稳固 |
抉择排序 | 10 | 不稳固 |
正文完