1. 介绍
数据结构算法中排序有很多种，常见的、不常见的，至少包含十种以上。根据它们的特性，可以大致分为两种类型：比较类排序和非比较类排序
-
比较类排序：通过比较来决定元素间的相对次序，其时间复杂度不能突破 O(nlogn)，因此也称为非线性时间比较类排序。
-
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序
非比较类的排序在实际情况中用的比较少，笔记中主要围绕比较类排序展开讲解。其实根据排序的稳定性，也可以分为稳定排序和不稳定排序，例如快速排序就是不稳定的排序、冒泡排序就是稳定的排序
2. 冒泡排序
冒泡排序是一次比较两个元素，如果顺序是错误的就把它们交换过来。，直到不需要再交换
function bubbleSort(array) {
const len = array.length
if (len < 2) return array
for (let i = 0; i < len - 1; i++) {
for (let j = i + 1; j < len; j++) {
if (array[j] < array[i]) {
[array[i], array[j]] = [array[j], array[i]]
}
}
}
return array
}
var a = [1, 3, 6, 3, 23, 76, 1, 34, 222, 6, 456, 221];
console.log(bubbleSort(a)) // [1, 1, 3, 3, 6, 6, 23, 34, 76, 221, 222, 456]
3. 快速排序
快速排序的基本思想是通过一趟排序，将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序
function quickSort(array) {
var quick = function(arr) {
const len = arr.length
if (len < 2) return arr
const index = Math.floor(len >> 1) // 找中间坐标
// => const index = Math.floor(len / 2)
const pivot = arr.splice(index, 1)[0] // 中间值
const left = []
const right = []
for (let i = 0; i < len; i++) {
arr[i] > pivot
? right.push(arr[i])
: left.push(arr[i])
}
return quick(left).concat([pivot], quick(right))
}
从数列中挑出一个元素，称为 “基准”（pivot）；然后重新排序数列，所有元素比基准值小的摆放在基准前面、比基准值大的摆在基准的后面；在这个区分搞定之后，该基准就处于数列的中间位置；然后把小于基准值元素的子数列（left）和大于基准值元素的子数列（right）递归地调用 quick 方法排序完成，这就是快排的思路
4. 插入排序
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，从而达到排序的效果
function insertSort(array) {
const len = array.length
let current, prev
for (let i = 1; i < len; i++) {
current = array[i]
prev = i - 1
while (prev >= 0 && array[prev] > current) {
array[prev + 1] = array[prev]
prev--
}
array[prev + 1] = current
}
return array
}
插入排序的思路是基于数组本身进行调整的，首先循环遍历从 i 等于 1 开始，拿到当前的 current 的值，去和前面的值比较，如果前面的大于当前的值，就把前面的值和当前的那个值进行交换，通过这样不断循环达到了排序的目的
5. 选择排序
将最小的元素存放在序列的起始位置，再从剩余未排序元素中继续寻找最小元素，然后放到已排序的序列后面……以此类推，直到所有元素均排序完毕
function selectSort(array) {
const len = array.length
let minIndex
for (let i = 0; i < len - 1; i++) {
minIndex = i
for (let j = i + 1; j < len; j++) {
if (array[j] < array[minIndex]) {
minIndex = j
}
}
[array[i], array[minIndex]] = [array[minIndex], array[i]]
}
return array
}
6. 堆排序
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质，即子结点的键值或索引总是小于（或者大于）它的父节点。堆的底层实际上就是一棵完全二叉树，可以用数组实现
根节点最大的堆叫作大根堆，根节点最小的堆叫作小根堆，你可以根据从大到小排序或者从小到大来排序，分别建立对应的堆就可以
function heap_sort(arr) {
var len = arr.length
var k = 0
function swap(i, j) {
var temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
function max_heapify(start, end) {
var dad = start
var son = dad * 2 + 1
if (son >= end) return
if (son + 1 < end && arr[son] < arr[son + 1]) {
son++
}
if (arr[dad] <= arr[son]) {
swap(dad, son)
max_heapify(son, end)
}
}
for (var i = Math.floor(len / 2) - 1; i >= 0; i--) {
max_heapify(i, len)
}
for (var j = len - 1; j > k; j--) {
swap(0, j)
max_heapify(0, j)
}
return arr
}
- 堆排序最核心的点就在于排序前先建堆
- 由于堆其实就是完全二叉树，如果父节点的序号为 n，那么叶子节点的序号就分别是 2n 和 2n+1
堆排序最后有两个循环：
第一个是处理父节点的顺序
第二个循环则是根据父节点和叶子节点的大小对比，进行堆的调整。通过这两轮循环的调整，最后堆排序完成
7. 归并排序
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并
function mergeSort(array) {
const len = array.length
if (len === 1) { return array }
const mid = Math.floor(len / 2)
const left = array.slice(0, mid)
const right = array.slice(mid, len)
return merge(mergeSort(left), mergeSort(right))
}
const merge = (left, right) => {
const result = []
let il = 0, ir = 0
while (il < left.length && ir < right.length) {
left[il] < right[ir]
? result.push(left[il++])
: result.push(right[ir++])
}
while (il < left.length) {
result.push(left[il++])
}
while (ir < right.length) {
result.push(right[ir++])
}
return result
}
通过 mid 可以把该数组分成左右两个数组，分别对这两个进行递归调用排序方法，最后将两个数组按照顺序归并起来
8. 总结
网友评论