基础排序

转

TIP

排序算法的稳定性: 能保证排序前 2 个相等的数的前后位置顺序和排序后它们两个的前后位置顺序相同

冒泡排序（稳定）

1、循环遍历，两两比较，如果前面的数大于后面的数，交换，这样第一轮交换后最后的数是最大的 2、重复 1，如果一轮下来没有要交换的，退出循环，证明已经是排序了

function sort(arr, xs) { 
  for (let i = 1; i < arr.length; i++) {
    let flag = true // 是否还需要继续判断标志
    for (let j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
        flag = false
      }
    }

    if (flag) {
      break
    }
  }

  return arr
}

选择排序（不稳定）

1、先找最大（小）的值，放起始位置 2、从剩余数组中找最大（小）的值，放第二个位置 3、重复 2

function sort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    if (minIndex !== i ) {
      [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]]
      console.log(arr)
    }
  }

  return arr
}

console.log(sort([4,2,3,6,5]))

插入排序（稳定）

1、第一个元素为已排序，取出第二个，和第一个比较，是否交换 2、第一个和第二个元素为已排序，取出第三个，和第一个，第二个比较，是否交换 3、重复 2

function sort(arr) {
  var len = arr.length
  var preIndex,current;
  for (var i = 1; i < len; i++) {
    preIndex = i -1
    current = arr[i]
    while(preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex]
      preIndex--
    }
    arr[preIndex + 1] = current
  }
  return arr
}

console.log(sort([4,2,3,6,5]))

希尔排序（不稳定）

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

以[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]为例 1、gap 为 4 的快速排序 1.a[4]=2，a[0]=8 比较(交换) => [2,9,1,7,8,3,5,4,6,0] 2.a[5]=3，a[1]=9 比较(交换) => [2,3,1,7,8,9,5,4,6,0] 3.a[6]=5，a[2]=1 比较(不交换) => [2,3,1,7,8,9,5,4,6,0] 3.a[7]=4，a[3]=7 比较(交换) => [2,3,1,4,8,9,5,7,6,0] 3.a[8]=6，a[4]=8，a[0]=2 比较(交换) => [2,3,1,4,6,9,5,7,8,0] 3.a[9]=0，a[5]=9，a[1]=3 比较(交换) => [2,0,1,4,6,3,5,7,8,9]

2、gap 为 1 普通快速排序

function shellSort(arr) {
  var len = arr.length,
    temp,
    gap = 1;
  while (gap < len / 3) {
    //动态定义间隔序列
    gap = gap * 3 + 1;
  }
  for (gap; gap > 0; gap = Math.floor(gap / 3)) {
    for (var i = gap; i < len; i++) {
      temp = arr[i];
      for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j];
      }
      arr[j + gap] = temp;
    }
  }
  return arr;
}

console.log(shellSort([8, 9, 1, 7, 2, 3, 5, 4, 6, 0]))

归并排序（稳定）

以空间换时间，递归每次用个新数组保存排序后的数

function mergeSort(arr) {
  var len = arr.length
  if (len < 2) {
    return arr
  }
  var middle = Math.floor(len / 2)
  var left = arr.slice(0, middle)
  var right = arr.slice(middle)
  return merge(mergeSort(left), mergeSort(right))
}

function merge(left, right) {
  var result = []
  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
}

快速排序（不稳定）

1、选择一个基准，这里选中间的，然后左边放小于基准的，右边放大于基准的 2、重复 1

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  var pivotIndex = Math.floor(arr.length / 2)
  var pivot = arr.splice(pivotIndex, 1)[0]
  var left = []
  var right = []
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

function quickSort(arr, left, right) {
  var len = arr.length,
    partitionIndex,
    left = typeof left != "number" ? 0 : left,
    right = typeof right != "number" ? len - 1 : right;

  if (left < right) {
    partitionIndex = partition(arr, left, right);
    quickSort(arr, left, partitionIndex - 1);
    quickSort(arr, partitionIndex + 1, right);
  }
  return arr;
}

function partition(arr, left, right) {
  // 分区操作
  var pivot = left, // 设定基准值（pivot）
    index = pivot + 1;
  for (var i = index; i <= right; i++) {
    if (arr[i] < arr[pivot]) {
      swap(arr, i, index);
      index++;
    }
  }
  swap(arr, pivot, index - 1);
  return index - 1;
}

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

const arr = [9, 8, 1, 7, 2, 3, 5, 4, 6, 0];
console.log(quickSort(arr));

function partition2(arr, low, high) {
  let pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] > pivot) {
      --high;
    }
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) {
      ++low;
    }
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}

function partition3(a, left, right) {
  if (left > right) {
    return
  }

  let pivot = a[left]  // 基准
  let i = left
  let j = right
  while(i < j) {
    if(a[j] >= pivot && i < j) {
      j--
      continue
    }
    if(a[i] <= pivot && i < j) {
      i++
      continue
    }
    [a[i],a[j]] = [a[j],a[i]]
    i++
    j--
  }

  [a[left],a[i]] = [a[i],a[left]]

  return i
}

堆排序（不稳定）

1、创建一个大根堆H[0,...,n-1]，最大值在顶部 2、堆首和堆尾互换, 调整H[0, n-2]堆 3、重复2

  // 交换两个节点
  function swap(A, i, j) {
    let temp = A[i]
    A[i] = A[j]
    A[j] = temp
  }

  // 创建堆，其实是对data数组做一个结构调整，使其具有堆的特性
  function buildHeap(data) {
    var len = data.length
    for (var i = Math.floor(len / 2); i >= 0; i--) {
      heapAjust(data, i, len)
    }
  }
  // 堆调整函数，即调整当前data为大根堆
  function heapAjust(data, i, len) {
    var child = 2 * i + 1
    // 如果有孩子结点，默认情况是左孩子
    while (child <= len) {
      var temp = data[i]
      // 如果右孩子存在且其值大于左孩子的值，则将child指向右孩子
      if (child + 1 <= len && data[child] < data[child + 1]) {
        child = child + 1
      }
      // 如果当前结点的值小于其孩子结点的值，则交换，直至循环结束
      if (data[i] < data[child]) {
        data[i] = data[child]
        data[child] = temp
        i = child
        child = 2 * i + 1
      } else {
        break
      }
    }
  }
  // 排序
  function heapSort(data) {
    buildHeap(data)

    var len = data.length
    for (var i = len - 1; i >= 0; i--) {
      swap(data, i, 0)
      heapAjust(data, 0, i - 1)
    }
    return data
  }
  const arr = [62, 88, 58, 47, 35, 73, 51, 99, 37, 93]
  var newArr = heapSort(arr)
  console.log(newArr) // [35, 37, 47, 51, 58, 62, 73, 88, 93, 99]

计数排序（稳定）

1、花O(n)的时间扫描一下整个序列 A，获取最小值 min 和最大值 max 2、开辟一块新的空间创建新的数组 B，长度为 ( max - min + 1) 3、数组 B 中 index 的元素记录的值是 A 中某元素出现的次数 4、最后输出目标整数序列，具体的逻辑是遍历数组 B，输出相应元素以及对应的个数

function countSort(arr) {
  let max = arr[0]
  let min = arr[0]
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i]
    }
    if (arr[i] < min) {
      min = arr[i]
    }
  }

  let buckets = new Array(max - min + 1).fill(0)
  for (let i = 0; i < arr.length; i++) {
    buckets[arr[i] - min]++ //减去最小值，确保索引大于负数
  }
  let index = 0
  let bucketCount = max - min + 1
  for (var i = 0; i < bucketCount; i++) {
    while (buckets[i]) {
      //将桶的编号加上最小值，变回原来的元素
      arr[index] = i + min
      index++
      buckets[i]--
    }
  }
  return arr
}
var arr = [2, 3, 8, 7, 1, 2, 7, 3]
console.log(countSort(arr)) //1,2,2,3,3,7,7,8

桶排序（稳定）

1、确认范围，亦即求取原数组的最大值与最小值。 2、确认需要多少个桶（这个通常作为参数传入，不能大于原数组长度），然后最大值减最小值，除以桶的数量，但得每个桶最多能放多个元素，我们称这个数为桶的最大容量。 3、遍历原数组的所有元素，除以这个最大容量，就能得到它要放入的桶的编号了。在放入时可以使用插入排序，也可以在合并时才使用快速排序。 对所有桶进行遍历，如果桶内的元素已经排好序，直接一个个取出来，放到结果数组就行了

  const bucketSort = (array, bucketSize) => {
    if (array.length === 0) {
      return array
    }

    console.time('桶排序耗时')
    let i = 0
    let minValue = array[0]
    let maxValue = array[0]
    for (i = 1; i < array.length; i++) {
      if (array[i] < minValue) {
        minValue = array[i] //输入数据的最小值
      } else if (array[i] > maxValue) {
        maxValue = array[i] //输入数据的最大值
      }
    }

    //桶的初始化
    const DEFAULT_BUCKET_SIZE = 5 //设置桶的默认数量为 5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE
    const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1
    const buckets = new Array(bucketCount)
    for (i = 0; i < buckets.length; i++) {
      buckets[i] = []
    }

    //利用映射函数将数据分配到各个桶中
    for (i = 0; i < array.length; i++) {
      buckets[Math.floor((array[i] - minValue) / bucketSize)].push(array[i])
    }

    array.length = 0
    for (i = 0; i < buckets.length; i++) {
      quickSort(buckets[i]) //对每个桶进行排序，这里使用了快速排序
      for (var j = 0; j < buckets[i].length; j++) {
        array.push(buckets[i][j])
      }
    }
    console.timeEnd('桶排序耗时')

    return array
  }

  // 快速排序
  const quickSort = (arr, left, right) => {
    let len = arr.length,
      partitionIndex
    left = typeof left != 'number' ? 0 : left
    right = typeof right != 'number' ? len - 1 : right

    if (left < right) {
      partitionIndex = partition(arr, left, right)
      quickSort(arr, left, partitionIndex - 1)
      quickSort(arr, partitionIndex + 1, right)
    }
    return arr
  }

  const partition = (arr, left, right) => {
    //分区操作
    let pivot = left, //设定基准值（pivot）
      index = pivot + 1
    for (let i = index; i <= right; i++) {
      if (arr[i] < arr[pivot]) {
        swap(arr, i, index)
        index++
      }
    }
    swap(arr, pivot, index - 1)
    return index - 1
  }

  const swap = (arr, i, j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
  }
  const array = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
  const newArr = bucketSort(array);
  console.log('newArr:', newArr);

基数排序（稳定）

1、将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零 2、从最低位开始，依次进行一次排序 3、从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列

  function radixSort(array) {
    var max = Math.max.apply(0, array);
    var times = getLoopTimes(max),
        len = array.length;
    var buckets = [];
    for (let i = 0; i < 10; i++) {
        buckets[i] = []; //初始化10个桶
    }
    for (var radix = 1; radix <= times; radix++) {
        //个位，十位，百位，千位这样循环
        lsdRadixSort(array, buckets, len, radix);
    }
    return array;
  }
  // 根据数字某个位数上的值得到桶的编号
  function getBucketNumer(num, d) {
    return (num + "").reverse()[d];
  }
  // 或者这个
  function getBucketNumer(num, i) {
    return Math.floor((num / Math.pow(10, i)) % 10);
  }
  // 获取数字的位数
  function getLoopTimes(num) {
    var digits = 0;
    do {
        if (num > 1) {
            digits++;
        } else {
            break;
        }
    } while ((num = num / 10));
    return digits;
  }
  function lsdRadixSort(array, buckets, len, radix) {
    //入桶
    for (let i = 0; i < len; i++) {
        let el = array[i];
        let index = getBucketNumer(el, radix);
        buckets[index].push(el);
    }
    var k = 0;
    //重写原桶
    for (let i = 0; i < 10; i++) {
        let bucket = buckets[i];
        for (let j = 0; j < bucket.length; j++) {
            array[k++] = bucket[j];
        }
        bucket.length = 0;
    }
  }
  // test
  var arr = [278, 109, 63, 930, 589, 184, 505, 269, 8, 83];
  console.log(radixSort(arr));