应用经典的Fisher–Yates洗牌算法；实现思路：数组从后向前遍历，然后将当前元素与前面（包括自身）随机位置的数进行交换
v8 在处理 sort 方法时，使用了插入排序和快排两种方案。当目标数组长度小于10时，使用插入排序；反之，使用快排。
function shuffle(arr) {
let m = arr.length;
while (m > 1){
let index = Math.floor(Math.random() * m--);
[arr[m] , arr[index]] = [arr[index] , arr[m]]
}
return arr;
}
实现思路：循环数组，比较当前元素与下一个元素；如果当前元素大于下一个元素，则向上冒泡(交换位置);这样一次循环下来后，最后一个数就是整个数组最大的；下次循环循环上面的操作；
复杂度： O(n2)
function bubbleSort(arr) {
const len = arr.length-1
for (let i = 0; i < len; i++) {
for (let j = 0;j < len-i;j++){
if (arr[j] > arr[j+1]) {
[arr[j], arr[j+1]] = [arr[j+1], arr[j]]
}
}
}
return arr
}
优化思路：设置变量pos用来记录每趟循环中最后一次进行交换的位置，由于pos之后的元素都没有进行过交换，则说明pos之后的元素是已经排序好的，下一次循环是扫描到pos位置即可
function bubbleSort1(arr) {
let i = arr.length-1; // 初始时,最后位置保持不变
while (i > 0) {
let pos = 0;//每趟开始时,无记录交换
for (let j = 0;j < i;j++) {
if (arr[j] > arr[j+1]) {
[arr[j], arr[j+1]] = [arr[j+1], arr[j]]
pos = j;//记录最后交换的位置
}
}
i = pos;//为下一趟排序作准备
}
return arr;
}
实现思路：将左侧看成有序的序列，每次遍历的时候，将元素插入到这个序列的对应位置；每次插入的时候从右侧开始比较；若比较的数较大，则向后移；
复杂度： O(n2)
function insertionSort(arr){
const len = arr.length
var prevIndex, cur;
for (var i = 1;i < len;i++) {
prevIndex = i-1
cur = arr[i]
while (prevIndex >= 0 && arr[prevIndex] > cur) {
arr[prevIndex+1] = arr[prevIndex]
prevIndex--
}
arr[prevIndex+1] = cur
}
return arr
}
实现思路：每次循环选择最小的数字放在前面有序序列的末尾；
复杂度： O(n2)
function selectionSort(array) {
for (let i = 0; i < array.length; i++) {
let minIndex = i;
for (let j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
[array[i], array[minIndex]] = [array[minIndex], array[i]];
}
}
实现思路：通过一趟遍历都将数据分为两部分，其中一部分的所有数据比另一部分的所有数据小，再将两部分数据按前面步骤递归，最终使整个数据变成有序的序列；
复杂度： 平均O(nlogn)，最坏O(n2)，实际上大多数情况下小于O(nlogn)
function quickSort(array) {
if (array.length <= 1) {
return array;
}
const target = array[0];
const left = [];
const right = [];
for (let i = 1; i < array.length; i++) {
if (array[i] < target) {
left.push(array[i]);
} else {
right.push(array[i]);
}
}
return quickSort(left).concat([target], quickSort(right));
}
原 因: 如果数据原来就是有序的或者接近有序的，每次分区点都选择最后一个数 据，那快速排序算法就会变得非常糟糕，时间复杂度就会退化为O(n2);
实现思路:
实现思路：其是建立在归并操作上的一种排序算法，该算法是采用分治法（Divide and Conquer）的一个典型的应用，把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列；
复杂度： O(nlogn)
function merge(leftArr, rightArr){
var result = [];
while (leftArr.length > 0 && rightArr.length > 0){
if (leftArr[0] < rightArr[0])
result.push(leftArr.shift()); //把最小的最先取出，放到结果集中
else
result.push(rightArr.shift());
}
return result.concat(leftArr).concat(rightArr); //剩下的就是合并，这样就排好序了
}
function mergeSort(array){
if (array.length == 1) return array;
var middle = Math.floor(array.length / 2); //求出中点
var left = array.slice(0, middle); //分割数组
var right = array.slice(middle);
return merge(mergeSort(left), mergeSort(right)); //递归合并与排序
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。