排序✅

常见数组排序算法有哪些？

01_10

冒泡排序

答案

比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡 wiki

function bubbleSort (arr) {
  // 非数组或数组元素小于 2 直接返回
  if (!Array.isArray(arr) || arr.length < 2) {
    return arr
  }
  // 拷贝数组避免直接在 arr 上操作
  const sortArr = [...arr]

  for (let i = sortArr.length - 1; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      const before = sortArr[j]
      const after = sortArr[j + 1]
      if (before > after) {
        // 交换元素位置
        sortArr.splice(j, 2, after, before)
      }
    }
  }
  return sortArr
}

module.exports = bubbleSort

快速排序

答案

先从数列中取出一个数作为“基准”。

分区过程：将比这个“基准”大的数全放到“基准”的右边，小于或等于“基准”的数全放到“基准”的左边。再对左右区间重复第二步，直到各区间只有一个数。

function quickSort (arr) {
  // 非数组或数组元素小于 2 直接返回
  if (!Array.isArray(arr) || arr.length < 2) {
    return arr
  } else {
    const compareNum = arr[0]
    const leftArr = []
    const rightArr = []
    for (let i = 1; i < arr.length; i++) {
      if (arr[i] < compareNum) {
        leftArr.push(arr[i])
      } else {
        rightArr.push(arr[i])
      }
    }
    const sortLeftArr = quickSort(leftArr)
    const sortRightArr = quickSort(rightArr)
    return [...sortLeftArr, compareNum, ...sortRightArr]
  }
}

module.exports = quickSort

选择排序

答案

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。

function selectionSort (arr) {
  // 非数组或数组元素小于 2 直接返回
  if (!Array.isArray(arr) || arr.length < 2) {
    return arr
  }
  // 拷贝数组避免直接在 arr 上操作
  const sortArr = []
  const tempArr = [...arr]
  while (tempArr.length) {
    let min = tempArr[0]
    let index = 0
    for (let i = 1; i < tempArr.length; i++) {
      if (tempArr[i] < min) {
        min = tempArr[i]
        index = i
      }
    }
    sortArr.push(min)
    tempArr.splice(index, 1)
  }

  return sortArr
}

module.exports = selectionSort

插入排序

答案

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

function insertSort (arr) {
  // 非数组或数组元素小于 2 直接返回
  if (!Array.isArray(arr) || arr.length < 2) {
    return arr
  }
  // 拷贝数组避免直接在 arr 上操作
  const backArr = []
  for (let i = 0; i < arr.length; i++) {
    if (i === 0) {
      backArr.push(arr[i])
    } else {
      // 插入对应位置
      let j
      for (j = backArr.length - 1; j >= 0; j--) {
        if (arr[i] > backArr[j]) {
          backArr.splice(j + 1, 0, arr[i])
          break
        }
      }
      // 若未找到此位置则插入最前面
      if (j === -1) {
        backArr.unshift(arr[i])
      }
    }
  }
  return backArr
}

module.exports = insertSort

希尔排序

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；按增量序列个数k，对序列进行k 趟排序；每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

答案

function shellSort (arr) {
  // 非数组或数组元素小于 2 直接返回
  if (!Array.isArray(arr) || arr.length < 2) {
    return arr
  }
  // 拷贝数组避免直接在 arr 上操作
  const sortArr = []
  const tempArr = [...arr]
  while (tempArr.length) {
    let min = tempArr[0]
    let index = 0
    for (let i = 1; i < tempArr.length; i++) {
      if (tempArr[i] < min) {
        min = tempArr[i]
        index = i
      }
    }
    sortArr.push(min)
    tempArr.splice(index, 1)
  }

  return sortArr
}

module.exports = shellSort

归并排序

答案

function mergeArr (arr1, arr2) {
   const k = []
   let i = 0
   let j = 0
 
   // 任意数组未结束则不退出循环
   while (i < arr1.length && j < arr2.length) {
     if (arr1[i] > arr2[j]) {
       k.push(arr2[j])
       j++
     } else {
       k.push(arr1[i])
       i++
     }
   }
   if (i >= arr1.length) {
     return k.concat(arr2.slice(j))
   } else {
     return k.concat(arr1.slice(i))
   }
 }function mergeSort (arr) {
  // 非数组或数组元素小于 2 直接返回
  if (!Array.isArray(arr) || arr.length < 2) {
    return arr
  } else if (arr.length === 2) {
    const [a, b] = arr
    if (a > b) {
      return [b, a]
    } else {
      return [a, b]
    }
  } else {
    const middleIndex = Math.floor(arr.length / 2)
    const leftArr = arr.slice(0, middleIndex)
    const rightArr = arr.slice(middleIndex)
    const sortLeft = mergeSort(leftArr)
    const sortRight = mergeSort(rightArr)
    return mergeArr(sortLeft, sortRight)
  }
}

module.exports = mergeSort

桶排序

答案

function bucketSort(arr, bucketSize = 5) {
  if (!Array.isArray(arr) || arr.length < 2) {
    return arr;
  }

  const minValue = Math.min(...arr);
  const maxValue = Math.max(...arr);

  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  const buckets = Array.from({ length: bucketCount }, () => []);

  arr.forEach(num => {
    const bucketIndex = Math.floor((num - minValue) / bucketSize);
    buckets[bucketIndex].push(num);
  });

  return buckets.reduce((sortedArray, bucket) => {
    return sortedArray.concat(bucket.sort((a, b) => a - b));
  }, []);
}

module.exports = bucketSort;

计数排序

答案

算法步骤

思想类似桶排序,但区间粒度更细,单一元素作为一个区间,适用于区间范围狭小且固定,但数据量巨大的场景

按照区间范围,将每个单一元素拆分为一个数组容器
遍历数组,存入对应元素的数组
合并所有离散数组即可

function countingSort(arr) {
  if (!Array.isArray(arr) || arr.length < 2) {
    return arr;
  }

  const max = Math.max(...arr);
  const min = Math.min(...arr);
  const count = Array(max - min + 1).fill(0);

  arr.forEach(num => {
    count[num - min]++;
  });

  const sortedArr = [];
  count.forEach((num, index) => {
    while (num > 0) {
      sortedArr.push(index + min);
      num--;
    }
  });

  return sortedArr;
}

module.exports = countingSort;

常见数组排序算法有哪些？​

冒泡排序​

快速排序​

选择排序​

插入排序​

希尔排序​

归并排序​

桶排序​

计数排序​