# 排序算法

# 冒泡排序

# 概念

比较两个记录键值的大小，如果这两个记录键值的大小出现逆序，则交换这两个记录。

# 实现

function bubbleSort(list: number[]): number[] {
  for(let i = 1; i < list.length; i++) {
    for(let j = i; j > 0; j--) {
      if(list[j] > list[i]) {
        [list[j], list[j - 1]] = [list[j - 1], list[j]]
      }
    }
  }
  return list
}

# 快速排序

# 概念

在 n 个记录中取某一个记录的键值为标准，通常取第一个记录键值为基准，通过一趟排序将待排的记录分为小于或等于这个键值的两个独立的部分，这是一部份的记录键值均比另一部分记录的键值小，然后，对这两部分记录继续分别进行快速排序，以达到整个序列有序。

# 实现

function quickSort(list: number[]): number[] {
  // 默认状态下的比较函数
  function compare(a: number, b: number): number {
    if(a === b) return 0
    return a < b ? -1 : 1
  }
  
  // 换位函数
  function swap(list: number[], a: number, b: number): void {
    [list[a], list[b]] = [list[b], list[a]]
  }
  
  // 分治函数
  function partition(list: number[], left: number, right: number): number {
    const pivot = list[Math.floor((left + right) / 2)]
    let i = left
    let j = right
    
    while(i <= j) {
      while(compare[list[i], pivot] === -1) i++
      while(compare[list[j], pivot] === 1) j--
      
      if(i <= j) {
        swap(list, i, j)
        i++
        j--
      }
    }
    return i
  }
  
  // 快排函数
  function quick(list: number[], left: number, right: number): number[] {
    let index: number
    
    if(list.length > 1) {
			index = partition(list, left, right)
      if(left < index - 1) {
        quick(list, left, index - 1)
      } 
      if(index < right) {
        quick(list, index, right)
      }
    }
    
    return list
  }
  
  return quick(list, 0, list.length - 1)
}

# 希尔排序

# 概念

算法先将要排序的数组按照某个增量d（n / 2，n 为要排序数的个数）分成若干组，每组中记录的下标相差 d，对每组中全部元素进行直接插入排序，然后再用一个较小的增量 d / 2 对它进行分组，在每个组中进行插入排序。当增量减小到 1 时，进行直接插入排序后，排序完成。

# 实现

function hillSort(list: number[]): number[] {
  const len = list.length
  let temp: number
  let gap = 1
  while(gap < len / 5) { // 动态定义间隔序列
    gap = gap * 5 + 1
  }
  
  for(;gap > 0; gap = Math.floor(gap / 5)) {
    for(let i = gap; i < len; i++) {
      temp = list[i]
      for(let j = i - gap; j >= 0 && list[j] > temp; j -= gap) {
        list[j + gap] = list[j]
      }
      list[j + gap] = temp
    }
  }
  
  return list
}

# 选择排序

# 概念

在第 i 次选择操作中，通过 n - i 次键值间比较，从 n - i + 1 个记录中选择出键值最小的记录，并和第 i 个记录交换。

# 实现

function selectSort(list: number[]): number[] {
  for(let i = 0; i < list.length; i++) {
    const min = Math.min(...list.slice(i)) 
    const index = list.indexOf(min);
    [list[i], list[index]] = [list[index], list[i]]
  }
  
  return list
}

# 堆排序

# 概念

# 实现

function adjustMaxHeap(heap,head,heapSize){
    let temp = heap[head];
    let child = head * 2 + 1;
    while(child < heapSize){
        if(child+1 < heapSize && heap[child] < heap[child+1]) child++;
        if(heap[head] < heap[child]){
            heap[head] = heap[child];
            head = child;
            child = head * 2 + 1;
        }else break;
        heap[head] = temp;
    }
}

function buildHeap(heap){
    for(let i = (heap.length-1) >> 1;i >= 0;i--){
        adjustMaxHeap(heap,i,heap.length);
    }
}

function heapSort(arr){
    buildHeap(arr);
    for(let i = arr.length-1;i > 0;i--){
        [arr[i],arr[0]] = [arr[0],arr[i]];
        adjustMaxHeap(arr,0,i);
    }
    return arr;
}

# 归并排序

# 概念

把一个有 n 个记录的无需文件看成是由 n 个长度为 1 的有序子文件组成的文件，然后进行两两归并

function mergeSort(list: number[]): number[] {
  const len = list.length
  if(len < 2) {
    return list
  }
  const mid = Math.floor(len / 2)
  const left = list.slice(0, mid)
  const right = list.slice(mid)
  
  function merge(left: number[], right: number[]): number[] {
    const result: number[] = []
    
    while(left.length && right.length) {
      if(left[0] < right[0]) {
        result.push(left.shift())
      } else {
        result.push(right.shift())
      }
    }
    
    while(left.length) result.push(left.shift())
    
    while(right.length) result.push(right.shift())
    
    return result
  }
  
  return merge(mergeSort(left), mergeSort(right))
}

# 桶排序

# 概念

把数据分组，放在一个个桶中，然后对每个桶里面进行排序

# 实现

function radixSort(list: number[], groupSize: number): number[] {
  const res: number[] = []
  for(let i = 0; i < list.length; i++) {
    res.push([])
  }
  
  for(let i = 0; i < list.length; i++) {
    res[Math.floor(parseInt(list[i] / groupSize)) + 1].push(list[i])
  }
  
  for(let i = 0; i < res.length; i++) {
    quickSort(res[i])
  }
  
  return res.flat(Infinity)
}

# 各排序算法的的稳定性、时间复杂度、空间复杂度

# js自带的排序实现

对于 js 来说，数组长度大于 10 采用快速排序，否则使用插入排序。

原因在于插入排序是因为时间复杂度比较差，但是在数据量较小的情况下相差无几，而且插入排序的常数时间很小，所以相对别的排序来说会更快。

# 稳定性

稳定性的意思就是对于相同值，相对顺序不能改变。通俗的讲有两个相同的数 A 和 B，在排序之前 A 在 B 前面，而经过排序之后 B 跑到 A 前面了，对于这种情况的发生我们成为排序的不稳定性。

# 排序面试题目

快速排序在完全无序的情况下效果最好，时间复杂度为 O(nlog2n)，在有序的情况下效果最差，时间复杂度为 O(n^2)
外部排序常用算法是归并排序
数组元素基本有序的情况下，插入排序的效果最好，因为这样只需要比较大小，不需要移动，时间复杂度趋近于 O(n)
如果只想得到 1000 个元素组成的序列中第 5 个最小元素之前的部分排序的序列，用对排序方法最快
对于长度为 n 的线性表作快速排序，在最坏的情况下比较次数为 n(n - 1) / 2

# 练习题

# 排序链表 (opens new window)

var sortList = function(head) {
    let mergeList = (left,right) => {
        let res = new ListNode(0);
        let pre = res;
        while(left && right){
            if(left.val <= right.val){
                pre.next = left;
                left = left.next;
            }else{
                pre.next = right;
                right = right.next;
            }
            pre = pre.next;
        }
        pre.next = left ? left : right;
        return res.next;
    }
    let mergeSort = (node) => {
        if(!node || !node.next) return node;
        let mid = node;
        let fast = node.next;
        while(fast && fast.next){
            mid = mid.next;
            fast = fast.next.next;
        }
        let rightList = mid.next;
        mid.next = null;
        let left = node;
        let right = rightList;
        return mergeList(mergeSort(left),mergeSort(right));
    }
    return mergeSort(head);
};

← 并查集.md 栈和队列.md →