排序
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序
- 归并排序
- 快速排序
References:
冒泡排序
每次交换两个相邻的元素，数组最后是最大的值(或最小的值)。
const bubbleSort = arr => {
const length = arr.length;
if (length <= 1) return ;
for (let i = 0; i < length - 1; i++) {
for (let j = 0; j < length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
return arr;
}
let arr = [1, 5, 3, 2, 10, 6, 9, 20, 2];
console.log(bubbleSort(arr));选择排序
每次从数组中找到最小值，然后将最小值跟待排序数组序列的第一个元素交换位置。
/* 将数组分为两部分：
已排序部分和未排序部分。
记录未排序部分中最小值或最大值的索引，
然后和未排序部分开始位置的数交换位置，
放到已排序数组的末尾 */
const selectionSort = arr => {
const len = arr.length;
let minIndex, temp;
for (let i = 0; i < len - 1; i++) {
minIndex = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
// 寻找最小的数
minIndex = j;
}
}
// 将索引i之后的最小值放到之前已排序的序列后面
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
return arr;
}
let arr = [1, 5, 3, 2, 10, 6, 9, 20, 2];
console.log(selectionSort(arr));插入排序
将当前元素 current 之前的序列看作是已排序的序列 arr，然后将当前元素current跟序列arr中的每个元素比较，如果 current 比序列中的元素 arr[index] 小就将arr[index] 往后移动一个位置，最后将 current 插入到空出来的位置。（类似斗地主理牌的顺序）
/**
* 将待排序序列的第一个元素当成一个有序序列，把第二个元素到最后一个元素当成未排序序列。从头到尾扫描，每次将当前元素插入到有序序列的适当位置
* 将当前元素 current 之前的序列看作是已排序的序列 arr，然后将当前元素 current 跟序列 arr 中的每个元素比较，
* 如果 current 比序列中的元素 arr[index] 小就将 arr[index] 往后移动一个位置，最后将 current 插入到空出来的位置。（类似斗地主理牌的顺序）
*/
const insertionSort = arr => {
const length = arr.length;
if (length <= 1) return ;
for (let i = 1; i < length; i++) {
let preIndex = i - 1; // current 的前一个元素
let current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
// 将 current 之前的比它大的元素往后移动一个位置
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
// 当 current 比前一个元素大的时候不需要赋值
if (preIndex + 1 !== i) {
// 将 current 插入到空出来的位置
arr[preIndex + 1] = current;
}
}
return arr;
}
let arr = [1, 5, 3, 2, 10, 6, 9, 20, 2];
console.log(insertionSort(arr));快速排序
/**
* 1. 找基准点，将基准点从原数组中删除；
* 2. 遍历原数组，根据元素与基准点大小的关系，将元素存放到 left 或 right 数组中
* （left 存放小于基准点的元素，right 存放大于基准点的元素）；
* 3. 递归 left 和 right，并把 left 和 right 合并。
* @param {*} arr 未排序的数组
* @returns arr 已排好序的数组
*/
const quickSort = arr => {
if (arr.length <= 1) {
return arr;
}
const midIndex = Math.floor(arr.length / 2); // 基准点的索引
const midVal = arr.splice(midIndex, 1); // 基准点的值
const left = []; // 存放比基准点小的元素
const right = []; // 存放比基准点大的元素
for (let i = 0; i < arr.length; i++) {
// 遍历数组，根据元素与基准值的大小关系进入到相应的数组中
if (arr[i] < midVal) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat(midVal, quickSort(right)); // 递归执行
};
const arr = [1, 5, 3, 2, 10, 6, 9, 20, 2];
console.log(quickSort(arr));堆排序
/** 堆是一个完全二叉树
* 1. 将待排序的序列构造成一个大顶堆。（此时，整个序列的最大值就是堆顶元素）；
* 2. 将堆顶元素与堆尾元素交换，然后将剩余 n-1 个序列重新构造成一个大顶堆，这样就得到
* n 个元素中的次大值。如此反复执行，最终得到一个有序序列。
* @param {Array} array 待排序的数组
* @returns 已排序的数组
*/
const heapSort = array => {
// 初始化一个大顶堆，从第一个非叶子节点开始
for (let i = Math.floor(array.length / 2 - 1); i >= 0; i--) {
heapify(array, i, array.length)
}
// 排序，每一次for循环找出一个当前的最大值，交换堆首与堆尾，
// 然后将剩下i个序列重新构造成一个大顶堆。
for (let i = Math.floor(array.length - 1); i > 0; i--) {
swap(array, 0, i)
heapify(array, 0, i)
}
return array
}
/**
* 交换数组索引 i 和 j 处的值
* @param {Array} array 待排序数组
* @param {Number} i 索引 i
* @param {Number} j 索引 j
*/
const swap = (array, i, j) => {
const temp = array[i]
array[i] = array[j]
array[j] = temp
}
/**
* 将以i位置以下的序列调整为大顶堆
* @param {Array} array 待排序数组
* @param {Number} i 根节点索引
* @param {Number} length 待排序数组的长度
*/
const heapify = (array, i, length) => {
let temp = array[i] // 根节点的值
// j 是根节点 i 的左右孩子的索引，从左孩子遍历到右孩子，
// 对结点 i 以下的结点全部做顺序调整
for (let j = 2 * i + 1; j < length; j = 2 * j + 1) {
temp = array[i]
// 左孩子的值小于右孩子
if (j + 1 < length && array[j] < array[j + 1]) {
j++
}
// 子节点的值大于根节点，交换
if (temp < array[j]) {
swap(array, i, j)
i = j
} else {
break
}
}
}
const array = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2]
console.log('原始array:', array)
const newArr = heapSort(array)
console.log('newArr:', newArr)归并排序
/**
* 自上而下递归，将 arr 分为两个数组，然后继续分，直到 left 和 right 都只有一个元素，
* 然后又逐级向上合并已排序的 left 和 right
* @param {Array} arr 原数组
* @returns res 已排序的数组
*/
const mergeSort = arr => {
if (arr.length < 2) {
return arr
}
const mid = Math.floor(arr.length / 2)
const left = arr.slice(0, mid)
const right = arr.slice(mid, arr.length)
return merge(mergeSort(left), mergeSort(right))
}
const merge = (left, right) => {
const res = []
while (left.length && right.length) {
// 合并left和right
if (left[0] <= right[0]) {
res.push(left.shift())
} else {
res.push(right.shift())
}
}
// 如果 left 和 right 中有一个里面没有元素而另一个里面有，
// 直接将剩下的元素添加到合并的数组后面（剩下的都是比 res 中元素大的元素）
while (left.length) {
res.push(left.shift())
}
while (right.length) {
res.push(right.shift())
}
return res
}
const arr = [1, 5, 3, 2, 10, 6, 9, 20, 2]
console.log(mergeSort(arr))希尔排序
/**
* 希尔排序的代码直接看，很难懂，但从原理上来理解之后再去看代码就很清晰了：
* 希尔排序是插入排序的升级版。插入排序的 gap=1，希尔排序是设置几个不同大小的 gap，
* 按 gap 递减的顺序每次对 arr 进行插入排序。这样做的目的是先将 arr 排成一个尽量有序的数组，
* 元素值小的位置靠前，元素值大的位置靠后，其他的位于中间位置。最后再进行一次 gap=1 的
* 插入排序，减小排序的时间。
* 因此希尔排序的代码其实就是在插入排序的基础上，在最外层包了一个设置 gap 递减的 for 循环。
* @param {Array} arr 未排序的 arr
* @returns arr 已排好序的 arr
*/
const shellSort = arr => {
const length = arr.length
let current = 0
// 初识化gap
let gap = 1
while (gap < length / 3) {
gap = gap * 3 + 1
}
for (gap; gap > 0; gap = Math.floor(gap / 3)) { // 外层 for 循环控制 gap 递减
for (let i = gap; i < length; i++) { // 插入排序的代码，只是将1替换成了 gap
current = arr[i]
let preIndex = i - gap
for (; preIndex >= 0 && arr[preIndex] > current; preIndex -= gap) {
arr[preIndex + gap] = arr[preIndex]
}
arr[preIndex + gap] = current
}
}
return arr
}
const arr = [1, 5, 3, 2, 10, 6, 9, 20, 2]
console.log(shellSort(arr))桶排序
/**
* 1. 确定桶大小，桶的个数，将 array 中的元素根据映射关系装入桶中；
* 2. 分别每个桶中的元素单独排序（插入排序或快速排序）；
* 3. 将每个桶内的元素按顺序取出，组成的序列就是有序的了；
* @param {Array} array 待排序数组
* @param {Number} bucketSize 桶的大小
* @returns 已排序的数组
*/
const bucketSort = (array, bucketSize) => {
if (array.length === 0) {
return array
}
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 // 桶大小的默认值
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE
const bucketCount =
Math.floor((maxValue - minValue) / bucketSize) + 1 // 桶的个数
const buckets = new Array(bucketCount)
.fill(null)
.map(item => new Array(bucketSize)) // 初始化桶
/* 利用映射函数((array[i] - minValue) / bucketSize))将数据分配到各个桶中 */
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 (let j = 0; j < buckets[i].length; j++) {
array.push(buckets[i][j])
}
}
return array
}
// const quickSort = arr => {
// if (arr.length <= 1) {
// return arr
// }
// const midIndex = Math.floor(arr.length / 2)
// const midVal = arr.splice(midIndex)
// const left = []
// const right = []
// for (let i = 0; i < arr.length; i++) {
// if (arr[i] < midVal) {
// left.push(arr[i])
// } else {
// right.push(arr[i])
// }
// }
// return quickSort(left).concat(midVal, quickSort(right))
// }
/**
* 快速排序的原地实现，没有搞懂！
* @param {Array} arr 待排序数组
* @param {Number} left 数组的左边界
* @param {Number} right 数组的右边界
* @returns 已排序的数组
*/
// TODO: 搞懂实现细节
const quickSort = (arr, left, right) => {
let partionIndex = 0
left = typeof left !== 'number' ? 0 : left
right = typeof right !== 'number' ? arr.length - 1 : right
if (left < right) {
partionIndex = partion(arr, left, right)
quickSort(arr, left, partionIndex - 1)
quickSort(arr, partionIndex + 1, right)
}
return arr
}
const partion = (arr, left, right) => {
const pivot = left // 基准点
let index = pivot + 1
for (let i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
;[arr[i], arr[index]] = [arr[index], arr[i]]
index++
}
}
;[arr[pivot], arr[index - 1]] = [arr[index - 1], arr[pivot]]
return index - 1
}
const array = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2]
console.log('原始array:', array)
const newArr = bucketSort(array)
console.log('newArr:', newArr)计数排序
/**
* 1.找出待排序的数组中最大和最小的元素。
* 2.统计数组中每个值为 i 的元素出现的次数，存入新数组 countArr 的第 i 项。
* 3.对所有的计数累加（从 countArr 中的第一个元素开始，每一项和前一项相加）。
* 4.反向填充目标数组：将每个元素 i 放在新数组的第 countArr[i] 项，每放一个元素就将 countArr[i] 减去 1 。
* @param {Array} array 待排序数组
* @returns 已排序数组
*/
const countingSort = array => {
const len = array.length
const result = [] // 存放排序后的结果
const countArr = [] // 统计 array 中每个数出现的次数
let min = array[0]
let max = array[0]
for (let i = 0; i < len; i++) {
// 获取最小，最大值
min = min <= array[i] ? min : array[i]
max = max >= array[i] ? max : array[i]
countArr[array[i]] = countArr[array[i]]
? countArr[array[i]] + 1
: 1
}
// 从最小值->最大值，将计数逐项相加
for (let j = min; j < max; j++) {
countArr[j + 1] = (countArr[j + 1] || 0) + (countArr[j] || 0)
}
// 反向填充结果数组
for (let k = len - 1; k >= 0; k--) {
result[countArr[array[k]] - 1] = array[k]
countArr[array[k]]--
}
return result
}
const array = [1, 3, 5, 2, 6, 3]
console.log('原始 array: ', array)
const newArr = countingSort(array)
console.log('newArr: ', newArr)
