排序算法
辅助函数
const Compare = { LESS_THAN: -1, BIGGER_THAN: 1, EQUALS: 0, } function defaultCompare(a, b) { if (a === b) { return Compare.EQUALS } return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN } function swap(array, a, b) { ;[array[a], array[b]] = [array[b], array[a]] } 复制代码1. 冒泡排序
冒泡排序是比较相邻的两个项，如果第一个比第二个大，则交换他们。元素项向上移动至正确的顺序，就像气泡升至表面一样，冒泡排序因此得名。
function bubbleSort(array, compareFn = defaultCompare) { let len = array.length for (let i = 0; i < len; i++) { for (let j = 0; j < len - 1 - i; j++) { if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) { swap(array, j, j + 1) } } } return array } 复制代码2. 选择排序
选择排序算法是一种原址比较排序算法，思路是首先找到数据结构中最小的数排在第一位，接着找到第二小的位置排在的二位，以此类推。
function selectionSort(array, compareFn = defaultCompare) { const { length } = array let indexMin for (let i = 0; i < length - 1; i++) { indexMin = i //找出最小的项 for (let j = i; j < length; j++) { if (compareFn(array[indexMin], array[j]) === Compare.BIGGER_THAN) { indexMin = j } } //把最小的项跟第i项交换 if (i !== indexMin) { swap(array, i, indexMin) } } return array } 复制代码3. 插入排序
插入排序每次排一个数据项，以此方式构建最后排序的数组。假定第一项已经排序了。接着，他和第二项进行比较，判断是否需要交换，接着第三项和前面的两项进行比较，判断是否需要交换位置，以此类推
function insertionSort(array, compareFn = defaultCompare) { const { length } = array let temp for (let i = 1; i < length; i++) { let j = i //temp：保存要插入的项 temp = array[i] //在左边找到刚好左边比temp小，右边比temp大的位置 while (j > 0 && compareFn(array[j - 1], temp) === Compare.BIGGER_THAN) { array[j] = array[j - 1] j-- } //找到正确的位置插入 array[j] = temp } return array } 复制代码4. 希尔排序
希尔排序是插入排序的优化版。将原来的大数组不断分成更小的数组进行插入排序。
function shellSort(array, compareFn = defaultCompare) { const { length } = array let gap = Math.floor(length / 2) while (gap >= 1) { for (let i = gap; i < length; i++) { const temp = array[i] let j = i while (j > gap - 1 && compareFn(array[j - gap], temp) === Compare.BIGGER_THAN) { array[j] = array[j - gap] j -= gap } array[j] = temp } gap = Math.floor(gap / 2) } return array } 复制代码5. 归并排序
归并排序是一种分而治之算法。其思想是将原始数组切分成较小的数组，直到每一个小数组只有一个位置，接着将小数组归并成较大的数组。直到最后只有一个排序完成的大数组。
//负责合并和排序产生大的数组 function merge(left, right, compareFn) { let i = 0 let j = 0 const result = [] while (i < left.length && j < right.length) { result.push(compareFn(left[i], right[j]) === Compare.LESS_THAN ? left[i++] : right[j++]) } return result.concat(i < left.length ? left.slice(i) : right.slice(j)) } function mergeSort(array, compareFn = defaultCompare) { if (array.length > 1) { const { length } = array const middle = Math.floor(length / 2) const left = mergeSort(array.slice(0, middle), compareFn) const right = mergeSort(array.slice(middle, length), compareFn) array = merge(left, right, compareFn) } return array } 复制代码6. 快速排序
首先，从数组中选择一个值作为主元(pivot)，也就是数组中间的那个值。
创建两个指针(引用)，左边一个指向数组第一个值，右边一个指向数组最后一个值。移动左指针直到我们找到一个比主元大的值，接着，移动右指针直到找到一个比主元小的值，然后交换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前，而比主元大的值都排在主元之后。这一步叫作划分(partition)操作。
接着，算法对划分后的小数组(较主元小的值组成的子数组，以及较主元大的值组成的子数组)重复之前的两个步骤，直至数组已完全排序。
//划分操作 function partitiion(array, left, right, compareFn) { const pivot = array[Math.floor((right + left) / 2)] let i = left let j = right while (i <= j) { //移动left,直到找到一个比pivot大的元素 while (compareFn(array[i], pivot) === Compare.LESS_THAN) { i++ } //rigth,直到找到一个比pivot小的元素 while (compareFn(array[j], pivot) === Compare.BIGGER_THAN) { j-- } if (i <= j) { swap(array, i, j) i++ j-- } } return i } function quick(array, left, right, compareFn) { let index if (array.length > 1) { index = partitiion(array, left, right, compareFn) if (left < index - 1) { quick(array, left, index - 1, compareFn) } if (index < right) { quick(array, index, right, compareFn) } } return array } function quickSort(array, compareFn = defaultCompare) { return quick(array, 0, array.length - 1, compareFn) }
作者：abean
链接：https://juejin.cn/post/7022167677812621326