排序算法总结

数组真正乱序的实现

应用经典的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)); //递归合并与排序  
} 
小红包免费领
小礼物走一走
Last Updated:
Contributors: slbyml
部分内容来源于网络,如有侵权,请留言或联系994917123@qq.com;访问量:waiting;访客数:waiting