排序算法

排序算法分类

比较类排序

通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序。

非比较类排序

不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

重点看堆排序、快速排序、归并排序，面试通常会考 O(nlogn) 的排序。

排序动画

• https://www.cnblogs.com/onepixel/p/7674659.html
• https://www.bilibili.com/video/av25136272
• https://www.bilibili.com/video/av63851336

初级排序 O(n^2)

选择排序（Selection Sort）

每次选最小值，然后放到待排序数组的起始位置。

function selectionSort (arr) {
  const len = arr.length;
  let minIdx, temp;
  
  for (let i = 0; i < len - 1; i++) {
    minIdx = i;
    
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }
    
    temp = arr[i];
    arr[i] = arr[minIdx];
    arr[minIdx] = temp;
  }
  
  return arr;
}

插入排序（Insertion Sort）

从前到后逐步构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

function insertionSort (arr) {
  const len = arr.length;
  let preIdx, current;

  for (let i = 1; i < len; i++) {
    preIdx = i - 1;
    current = arr[i];

    while (preIdx >= 0 && arr[preIdx] > current) {
      arr[preIdx + 1] = arr[preIdx];
      preIdx--;
    }

    arr[preIdx + 1] = current;
  }

  return arr;
}

冒泡排序（Bubble Sort）

嵌套循环，每次查看相邻的元素如果逆序，则交换。

function bubbleSort (arr) {
  const len = arr.length;

  let temp, finish;

  for (let i = 0; i < len - 1; i++) {
    finish = true;

    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;

        finish = false;
      }
    }

    if (finish) break;
  }

  return arr;
}

高级排序 O(N*LogN)

快速排序（Quick Sort）

数组取标杆 pivot，将小元素放到 pivot 左边，大元素放右侧，然后依次对左边和右边的子数组继续快排。以达到整个序列有序。

pivot 可以选在任意位置，左边、中间、右边。

function partition (arr, start, end) {
  const pivot = end;

  let counter = start;

  for (let i = start; i < end; i++) {
    if (arr[i] < arr[pivot]) {
      if (counter == i) {
        counter++;
      } else {
        const temp = arr[counter];
        arr[counter] = arr[i];
        arr[i] = temp;
        counter++;
      }
    }
  }

  const temp = arr[pivot];
  arr[pivot] = arr[counter];
  arr[counter] = temp;

  return counter;
}

function quickSort (arr, begin, end) {
  if (end < begin) return;

  const pivot = partition(arr, begin, end);

  quickSort(arr, begin, pivot - 1);
  quickSort(arr, pivot + 1, end);
}

归并排序（Merge Sort）

• 把长度为 n 的输入序列分成两个长度为 n / 2 的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

function merge (arr, left, mid, right) {
  const temp = new Array(right - left + 1);

  let i = left,
      j = mid + 1,
      k = 0;

  while (i <= mid && j <= right) {
    temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
  }

  while (i <= mid) temp[k++] = arr[i++];
  while (j <= right) temp[k++] = arr[j++];

  for (i = 0; i < temp.length; i++) {
    arr[left + i] = temp[i];
  }
}

function mergeSort (arr, left, right) {
  if (right <= left) return;

  const mid = (left + right) >> 1;

  mergeSort(arr, left, mid);
  mergeSort(arr, mid + 1, right);

  merge(arr, left, mid, right);
}

堆排序（Heap Sort）

堆插入 O(logN)，取最大值/最小值 O(1)。

• 数组元素依次建立小顶堆
• 依次取堆顶元素，并删除

class Heap {
  constructor (arr) {
    this.len = arr.length;
    
    for (let i = Math.floor(this.len / 2); i >= 0; i--) {
      this.heapify(arr, i);
    }
  }

  heapify (arr, i) {
    let left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;

    if (left < this.len && arr[left] > arr[largest]) {
      largest = left;
    }
    if (right < this.len && arr[right] > arr[largest]) {
      largest = right;
    }

    if (largest != i) {
      this.swap(arr, i, largest);
      this.heapify(arr, largest);
    }
  }

  swap (arr, i, j) {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}


function heapSort (arr) {
  const heap = new Heap(arr);

  for (let i = arr.length - 1; i > 0; i--) {
    heap.swap(arr, 0, i);
    heap.len--;
    heap.heapify(arr, 0);
  }
}

总结

归并和快排具有相似性，但步骤顺序相反。

归并排序：先排序左右子数组，然后合并两个有序子数组；
快速排序：先调配出左右子数组，然后对于左右子数组进行排序；

特殊排序 O(n)

计数排序（Counting Sort）

计数排序要求输入的数组必须是有确定范围的整数。
将输入的数据值转化为键存储在额外开辟的数组空间中，然后依次把计数大于 1 的填充回原数组。

function countingSort (arr, maxVal) {
  const bucket = new Array(maxVal + 1);

  let sortedIndex = 0,
      arrLen = arr.length,
      bucketLen = bucket.length;

  for (let i = 0; i < arrLen; i++) {
    if (!bucket[arr[i]]) {
      bucket[arr[i]] = 0;
    }
    bucket[arr[i]]++;
  }

  for (let j = 0; j < bucketLen; j++) {
    while (bucket[j] > 0) {
      arr[sortedIndex++] = j;
      bucket[j]--;
    }
  }
}

桶排序（Bucket Sort）

桶排序的工作原理：假设输入数据均匀分布，将数据分到有限的桶里，每个桶再分别排序（可能使用别的排序算法或者以递归方式继续使用桶排序）。

function insertionSort (arr) {
  const len = arr.length;
  let preIdx, current;

  for (let i = 1; i < len; i++) {
    preIdx = i - 1;
    current = arr[i];

    while (preIdx >= 0 && arr[preIdx] > current) {
      arr[preIdx + 1] = arr[preIdx];
      preIdx--;
    }

    arr[preIdx + 1] = current;
  }

  return arr;
}

function bucketSort (arr, bucketSize) {
  if (arr.length === 0) return [];

  let i,
      minVal = arr[0],
      maxVal = arr[0];

  for (i = 1; i < arr.length; i++) {
    if (arr[i] < minVal) {
      minVal = arr[i];
    } else if (arr[i] > maxVal) {
      maxVal = arr[i];
    }
  }


  // 初始化桶
  bucketSize = bucketSize || 5;

  const bucketCount = Math.floor((maxVal - minVal) / bucketSize) + 1,
        buckets = new Array(bucketCount);

  for (i = 0; i < buckets.length; i++) {
    buckets[i] = [];
  }


  // 利用映射函数分配数据
  for (i = 0; i < arr.length; i++) {
    buckets[Math.floor((arr[i] - minVal) / bucketSize)].push(arr[i]);
  }


  arr.length = 0;
  
  for (i = 0; i < buckets.length; i++) {
    insertionSort(buckets[i]); // 桶排序，使用插入排序

    for (let j = 0; j < buckets[i].length; j++) {
      arr.push(buckets[i][j]);
    }
  }
}

基数排序（Radix Sort）

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。

function radixSort (arr, maxDigit) {
  const counter = [];

  let mod = 10,
      dev = 1;

  for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
    for (let j = 0; j < arr.length; j++) {
      const bucket = parseInt((arr[j] % mod) / dev);

      if (counter[bucket] == null) counter[bucket] = [];

      counter[bucket].push(arr[j]);
    }

    let pos = 0;

    for (let j = 0; j < counter.length; j++) {
      let val = null;

      if (counter[j]) {
        while ((val = counter[j].shift()) != null) {
          arr[pos++] = val;
        }
      }
    }
  }
}

相关题目

数组的相对排序

有效的字母异位词

合并区间

翻转对

// 数组的相对排序

// 计数排序
/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number[]}
 */
var relativeSortArray = function (arr1, arr2) {
  const counts = new Array(1001).fill(0);

  for (const n of arr1) {
    counts[n]++;
  }

  const ans = [];

  for (const n of arr2) {
    while (counts[n] > 0) {
      ans.push(n);
      counts[n]--;
    }
  }

  for (let i = 0; i < counts.length; i++) {
    while (counts[i] > 0) {
      ans.push(i);
      counts[i]--;
    }
  }

  return ans;
};

// 有效的字母异位词，可以使用快排和计数排序

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
  if (s.length != t.length) return false;

  const map = new Map();

  for (const i of s) {
    map.set(i, s);
  }
  for (const i of t) {
    if (!map.has(i)) return false;
    map.delete(i);
  }

  return true;
};

// 合并区间

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);

  const ans = [];

  for (let i = 0; i < intervals.length; i++) {
    const start = intervals[i][0];
    
    let cur = intervals[i][1];

    while(i < intervals.length-1 && cur >= intervals[i+1][0]) {
      cur = Math.max(intervals[i+1][1], cur);
      i++;
    }

    ans.push([start, cur]);
  }

  return ans;
};

// 翻转对

var reversePairs = function(nums) {
  if (nums.length === 0) return 0;
  return reversePairsRecursive(nums, 0, nums.length - 1);
};

const reversePairsRecursive = (nums, left, right) => {
  if (left === right) return 0;

  const mid = Math.floor((left + right) / 2),
        n1 = reversePairsRecursive(nums, left, mid),
        n2 = reversePairsRecursive(nums, mid + 1, right);

  let ret = n1 + n2,
      i = left,
      j = mid + 1;

  while (i <= mid) {
    while (j <= right && nums[i] > 2 * nums[j]) j++;

    ret += j - mid - 1;
    i++;
  }

  const sorted = new Array(right - left + 1);

  let p1 = left,
      p2 = mid + 1,
      p = 0;

  while (p1 <= mid || p2 <= right) {
    if (p1 > mid) {
      sorted[p++] = nums[p2++];
    } else if (p2 > right) {
      sorted[p++] = nums[p1++];
    } else {
      if (nums[p1] < nums[p2]) {
        sorted[p++] = nums[p1++];
      } else {
        sorted[p++] = nums[p2++];
      }
    }
  }

  for (let k = 0; k < sorted.length; k++) {
    nums[left + k] = sorted[k];
  }

  return ret;
}