JavaScript中常见的十种排序方法

对于评述算法优劣术语的说明

排序算法图片总结

补充：算法中的log

即若 N = 2 ^ k，则 T(N) = N * (k + 1) = N log N + N = O(N log N)

我们根据上面的 N = 2 ^ k 可得到 k = log N 
所以代入公式消除变量 k：

N * k + N = N log N + N

此时只剩下一个变量可以十分清晰的展现出公式要表达的相对增长率 
故公式推导过程中如果存在类似的条件关系（如 N = 2 ^ k） 
即可代入公式消除多余的变量以 log （如 log N）的形式展现

小提示

一、冒泡排序

原理：比较相邻元素，如果前者大于后者，则调换位置，对每个元素执行，此时最后一个元素将是最大值，重复上述操作至排序完成。

代码示例：

function bubblingSort(items) { for (let i = 0; i < items.length; i++) { for (let j = 0; j < items.length - i - 1; j++) { if (items[j] > items[j + 1]) { const temp = items[j] items[j] = items[j + 1] items[j + 1] = temp } } } return items; }

二、快速排序

原理：快速排序是对冒泡排序一种改进，第一趟排序时将数据分成两部分，一部分比另一部分的所有数据都要小。然后递归调用，在两边都实行快速排序。

代码示例：

function quickSort(items) { if (items.length <= 1) { return items } const pivotIndex = Math.floor(items.length / 2) const pivotItem = items.splice(pivotIndex, 1)[0] let left = [] let right = [] items.forEach((item) => { if (item <= pivotItem) { left.push(item) } else { right.push(item) } }) return quickSort(left).concat([pivotItem], quickSort(right)) }

三、插入排序

原理：

（1）从第一个元素开始，该元素可以认为已经被排序

（2）取出下一个元素，在已经排序的元素序列中从后向前扫描

（3）如果该元素（已排序）大于新元素，将该元素移到下一位置

（4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

（5）将新元素插入到下一位置中

（6）重复步骤2

代码示例：

function insertionSort(items) { for (let i = 1; i < items.length; i++) { if (items[i] < items[i - 1]) { const guard = items[i] let j = i - 1 items[i] = items[j] while (j >= 0 && guard < items[j]) { items[j + 1] = items[j] j-- } items[j + 1] = guard } } return items }

四、选择排序

原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

代码示例：

function selectionSort(items) { for (let i = 0; i < items.length; i++) { let temp = 0, index = 0 for (let j = i; j < items.length; j++) { if (temp <= items[j]) { temp = items[j] index = j } } const selection = items.splice(index, 1)[0] items.unshift(selection) } return items }

五、希尔排序

原理：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序。

代码示例：

function shellSort(items) { const length = items.length let temp, gap = 1 while (gap < length / 5) { gap = gap * 5 + 1 } for (gap; gap > 0; gap = Math.floor(gap / 5)) { for (let i = gap; i < length; i++) { temp = items[i] for (var j = i - gap; j >= 0 && items[j] > temp; j -= gap) { items[j + gap] = items[j] } items[j + gap] = temp } } return items }

六、归并排序

原理：归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

代码示例：

function mergeSort(items) { const length = items.length if (length < 2) { return items } const middle = Math.floor(length / 2) const left = items.slice(0, middle) const right = items.slice(middle) return _merge(mergeSort(left), mergeSort(right)) } function _merge(left, right) { let result = [] while (left.length && right.length) { if (left[0] >= right[0]) { result.push(right.shift()) } else { result.push(left.shift()) } } while (left.length) { result.push(left.shift()) } while (right.length) { result.push(right.shift()) } return result }

七、堆排序

原理：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。

堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

代码示例：

function heapSort(items) { let heapSize = items.length let temp for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) { heapify(items, i, heapSize) } for (let j = heapSize - 1; j >= 1; j--) { temp = items[0] items[0] = items[j] items[j] = temp heapify(items, 0, --heapSize) } return items } function heapify(items, x, length) { // items Array, x Number const left = x * 2 + 1 const right = x * 2 + 2 let largest = x let temp if (left < length && items[left] > items[largest]) { largest = left } if (right < length && items[right] > items[largest]) { largest = right } if (largest != x) { temp = items[x] items[x] = items[largest] items[largest] = temp heapify(items, largest, length) } }

八、计数排序

原理：计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

代码示例：

function countingSort(items) { let counter = [], result = [] items.forEach(item => { if (!counter[item]) { counter[item] = 1 } else { counter[item] += 1 } }) counter.forEach((item, index) => { // index 为值 item 为index的数量 if (item) { while (item > 0) { result.push(index) item-- } } }) return result }

九、桶排序

原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

代码示例：

function bucketSort(items, num) { if (items.length <= 1) { return items } let length = items.length, buckets = [], result = [], min = max = items[0], reg = '/^[1-9]+[0-9]*$/', space, n = 0, total = num || ((num > 1 && reg.test(num)) ? num : 10) for (let i = 1; i < length; i++) { min = min <= items[i] ? min : items[i] max = max >= items[i] ? max : items[i] } space = (max - min + 1) / total for (let j = 0; j < length; j++) { let index = Math.floor((items[j] - min) / space) if (buckets[index]) { let k = buckets[index].length - 1 while (k >= 0 && buckets[index][k] > items[j]) { buckets[index][k + 1] = buckets[index][k] k-- } buckets[index][k + 1] = items[j] } else { buckets[index] = [] buckets[index].push(items[j]) } } while (n < total) { result = result.concat(buckets[n]) n++ } return result }

十、基数排序

原理：基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

代码示例：

function radixSort(items, maxDigit) { var mod = 10 var dev = 1 var counter = [] for (var i = 0; i < maxDigit; i++ , dev *= 10, mod *= 10) { for (var j = 0; j < items.length; j++) { var bucket = parseInt((items[j] % mod) / dev) if (!counter[bucket]) { counter[bucket] = [] } counter[bucket].push(items[j]) } var pos = 0 for (var j = 0; j < counter.length; j++) { var value = null if (counter[j] !== null) { while ((value = counter[j].shift()) != null) { items[pos++] = value } } } } return items }

二分查找（目标为有序递增数列）

原理：二分查找，也为折半查找。首先要找到一个中间值，通过与中间值比较，大的放又，小的放在左边。再在两边中寻找中间值，持续以上操作，直到找到所在位置为止。

function binarySearch(data, dest, start, end) { // 递归形式 const start = start || 0 const end = end || data.length - 1 let middle = Math.floor((start + end) / 2) if (dest === data[middle]) { return middle } if (dest > data[middle]) { binarySearch(data, dest, middle + 1, end) } if (dest < data[middle]) { binarySearch(data, dest, 0, middle - 1) } } function binarySearch(data, dest) { // 非递归形式 let h = data.length - 1 let l = 0 while (l <= h) { let middle = Math.floor((h + l) / 2) if (data[middle] === dest) { return middle } if (dest > data[middle]) { l = middle + 1 } else { h = niddle - 1 } } return false }