排序算法总结

静水深流's blog

排序算法总结 | 静水深流

2021-08-20 · via 静水深流's blog

数组真正乱序的实现

应用经典的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阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

静水深流's blog