Netherspite

概述

排序算法总结

排序算法 最好 最坏 平均 是否基于比较 是否稳定 空间复杂度
冒泡排序 O(n) O(n2) O(n2) √ √ O(1)
插入排序 O(n) O(n2) O(n2) √ √ O(1)
选择排序 O(n2) O(n2) O(n2) √ × O(1)
快速排序 O(nlogn) O(n2) O(nlogn) √ × O(1)
归并排序 都是O(nlogn) √ √ O(n)
堆排序 O(nlogn) √ O(1)
桶排序 O(n) × √
计数排序 O(n) × √
基数排序 O(n) × √

排序算法的分析要点

执行效率主要从以下三个方面进行分析：

  1. 最好情况、最坏情况、平均情况时间复杂度
  2. 时间复杂度的系数、常数、低阶，在对同一阶时间复杂度的排序算法性能对比时需要考虑
  3. 比较次数和交换（移动）次数，基于比较的排序算法

排序算法的空间消耗主要分为原地排序和非原地排序，原地排序算法就是空间复杂度为O(1)的算法。

排序算法还有一个重要的度量指标：稳定性，待排序的序列中存在值相等的元素，排序后相等元素之间原有的先后顺序不变，则是稳定的排序算法。

排序算法

基于比较的排序算法最频繁的操作就是比较和交换，在ES6中的交换可以用[a, b] = [b, a]来简单实现，对于比较，由于JavaScript没有实现统一的接口，对于不同类型的比较需要写不同的比较代码进行操作。

逆序数

有序数对是数组中具有有序关系的元素对的个数。完全有序的数组的有序数对=初始数组的有序数对+逆序数。

冒泡排序

冒泡排序过程中，交换的次数等于逆序数。

function bubbleSort(arr) {
  if(arr.length < 2) return;
  for(let i = 0; i < arr.length; i++){
    let flag = false;
    for(let j = i + 1; j < arr.length; j++){
      if(arr[i] > arr[j]) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
        flag = true;
      }
    }
    if(!flag) break;
  }
}

插入排序

插入排序过程中，交换的次数等于逆序数。插入排序和冒泡排序的交换次数都等于逆序数，但是在操作过程中，冒泡排序需要三个赋值操作才能交换，而插入排序只要一个，略优于冒泡排序。

function insertSort(arr) {
  if(arr.length < 2) return;
  for(let i = 1; i < arr.length; i++) {
    let val = arr[i];
    for(let j = i - 1; j >= 0; j--) {
      if(val < arr[j]) arr[j + 1] = arr[j];
      else break;
    }
  }
}

选择排序

选择排序不稳定，和冒泡、插入比稍微逊色。

function selectSort(arr) {
  if(arr.length < 2) return;
  for(let i = 0; i < arr.length - 1; i++) {
 		let min = i;
    for(let j = i + 1; j < arr.length; j++) {
      if(arr[min] > arr[j]) min = j;
    }
    [arr[i], arr[min]] = [arr[min], arr[i]];
  }
}

归并排序

function mergeSort(arr) {
  mergeSortC(arr, 0, arr.length - 1);
}
function mergeSortC(arr, p, q) {
  if(p >= q) return;
  let r = Math.floor((p + q) / 2);
  mergeSortC(arr, p, r);
  mergeSortC(arr, r + 1, q);
  merge(arr, p, r, q);
}
function merge(arr, p, r, q) {
  let i = p, j = r + 1;
  let nums = [];
  for(let k = p; k <= q; k++) {
    nums[k] = arr[k];
  }
  for (let k = p; k <= q; k++) {
    if (i > r) {
      arr[k] = nums[j++];
    } else if (j > q) {
      arr[k] = nums[i++];
    } else if (nums[i] < nums[j]) {
      arr[k] = nums[i++];
    } else {
      arr[k] = nums[j++];
    }
  }
}

归并排序需要额外的存储空间，空间复杂度是O(n)。

快速排序

function quickSort(arr) {
  quickSortC(arr, 0, arr.length - 1);
}
function quickSortC(arr, p, q) {
  if(p >= q) return;
  let r = partition(arr, p, q);
  quickSortC(arr, p, r - 1);
  quickSortC(arr, r + 1, q);
}
function partition(arr, p, q) {
  let pivot = arr[q];
  let i = p;
  for(let j = p; j <= q - 1; j++) {
    if(arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[q]] = [arr[q], arr[i]];
  return i;
}

快速排序的优化

每次分区选择最后或第一个数据，快速排序很可能会退化成O(n2)，快速排序恶化的原因主要是分区点选择的不合理。最理想的情况是：被分区点分开的两个分区中数据的数量差不多。常见的分区算法有：

  1. 将数组的第一个、最后一个和中间的三个数中取三个数的中间值作为分区点。当排序的数组比较大的时候，可以采样更多的数据来取比如五数取中。
  2. 从排序区间中随机选择一个元素作为分区点。

桶排序

桶排序的数据要很容易就能划分成m个桶，同时，桶与桶之间有着天然的大小顺序。其次，数据在各个桶之间的分布是比较均匀的。桶排序适合用在外部排序中，即数据量大（存储在外部磁盘中的数据），内存有限。

计数排序

桶排序的一种特殊情况。桶的数量可以大于要排序的数的范围，比如数字范围是[0, 100]，即可以用101个桶，每个桶存储一个数字的对象，即是计数排序。

function countSort(a) {
    const max = Math.max(...a);
    let result = [],
        temp = Array(max + 1).fill(0);
    for (let i = 0; i <= max; i++) {
        temp[a[i]]++;
    }
    for (let i = 1; i <= max; i++) {
        temp[i] += temp[i - 1];
    }
    for (let i = a.length - 1; i >= 0; i--) {
        let index = temp[a[i]] - 1;
        result[index] = a[i];
        temp[a[i]]--;
    }
    for(let i = 0; i < a.length; i++) {
      	a[i] = result[i];
    }
}

基数排序

基数排序需要可以分割出独立的位来比较，而且位之间有递进的关系，如果a数据的高位比b数据大，那剩下的低位就不用比较了，比如11位手机号码的排序，可以从最后一位开始逐位比较进行排序。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则就不能到O(n)了。

堆排序

堆是一个完全二叉树，且堆中的每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。一般用数组存储堆，数组第0个元素为空。数组中下标为i的节点的左子节点是i*2，右子节点是i*2+1，父节点是i/2。

堆排序的过程大致分解成建堆和排序两个步骤。

建堆

从后往前处理数组，并且每个数据都是从上往下堆化。下面以大顶堆为例。

class HeapSort{
  constructor(capacity) {
    this.capacity = capacity;
    this.heap = [];
  }
  buildHeap(a, n) {
  	for(let i = Math.floor(n / 2); i > 0; i--) {
    	this.heapify(a, n, i);
  	}
	}
	heapify(a, n, i) {
  	while(true) {
    	let maxPos = i;
    	if(i * 2 <= n && a[i] < a[i * 2]) maxPos = i * 2;
    	if(i * 2 + 1 <= n && a[maxPos] < a[i * 2 + 1]) maxPos = i * 2 + 1;
    	if(maxPos === i) break;
    	[a[i], a[maxPos]] = [a[maxPos], a[i]];
    	i = maxPos;
  	}
	}
}

排序

将堆顶元素移除，并与数组最后一个元素交换，对剩下的n-1个元素重新建堆。

sort(a) {
  this.buildHeap(a, this.capacity);
  let k = this.capacity;
  while(k > 0) {
    [a[k], a[1]] = [a[1], a[k]];
    k--;
    heap(a, k, 1);
  }
}

堆排序性能没有快速排序好的原因主要有两方面，一是堆排序数据访问的方式是跳跃的，对CPU缓存不友好。二是对于同样的数据，堆排序的数据交换次数要多于快速排序。

应用

  1. 优先级队列

    优先级队列中，优先级最高的最先出队。堆和优先级队列非常相似，一个堆就可以看做一个优先级队列。

  2. 求Top K问题

    可以维护一个大小为K的小顶堆，顺序遍历数组，从数组中取出元素与堆顶元素比较，如果比堆顶元素大，就把堆顶元素删除，并且插入到堆中，否则不做处理。遍历完后堆中的数据就是前K大数据了。时间复杂度O(nlogk)。

  3. 求中位数

    维护两个堆，一个大顶堆，一个小顶堆。大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。如果新加入的数据小于等于大顶堆的堆顶元素，将新数据插入到大顶堆，否则插入到小顶堆。大顶堆的堆顶元素就是中位数。


 上一页

数据结构与算法

 评论