冒泡排序
- 比拟所有相邻元素，如果第一个比第二个大，则替换它们
- 一轮下来，能够保障最初一个数是最大的
- 执行n-1轮，就能够实现排序
- 工夫复杂度O(n^2)
Array.prototype.bubbleSort = function() { const len = this.length for(let i = 0; i < len - 1; i++) { for(let j = 0; j < len - i - 1; j++) { // 从前往后遍历 if (this[j] > this[j + 1]) { const temp = this[j] this[j] = this[j + 1] this[j + 1] = temp } } } // 与下面等同 // for(let i = 0; i < len - 1; i++) { // for(let j = i; j >= 0; j--) { // 从后往前遍历 // if (this[j] > this[j + 1]) { // const temp = this[j] // this[j] = this[j + 1] // this[j + 1] = temp // } // } // }}const arr = [6,3,8,2,1]console.log('排序前', arr)arr.bubbleSort()console.log('排序后', arr)抉择排序
- 找到数组中的最小值，选中它并将其搁置在第一位
- 接着找到第二小的值，选中它并将其放在第二位
- 执行n-1轮
- 工夫复杂度O(n^2)
Array.prototype.selectionSort = function () { let len = this.length let minIndex, temp for(let i = 0; i < len - 1; i++) { minIndex = i for(j = i + 1; j < len; j++) { if (this[j] < this[minIndex]) { // 寻找最小的数 minIndex = j // 保留最小数的索引 } } temp = this[i] // 将最小数与第i个数替换 this[i] = this[minIndex] this[minIndex] = temp }}const arr = [6,3,8,2,1]console.log('排序前', arr)arr.selectionSort()console.log('排序后', arr)插入排序
- 从第二个数往前比
- 比它大就往后排
- 以此类推进行到最初一个数
- 工夫复杂度O(n^2)
Array.prototype.insertionSort = function() { const len = this.length let preIndex, current for(let i = 1; i < len; i++) { preIndex = i - 1 current = this[i] while(preIndex >= 0 && this[preIndex] > current) { this[preIndex + 1] = this[preIndex] preIndex-- } this[preIndex + 1] = current }}const arr = [7,0,6,3,4,2,5,1]console.log('排序前', arr)arr.insertionSort()console.log('排序后', arr)归并排序
- 分：把数组劈成两半，再递归对子数组进行“分”的操作，直到分成一个个独自的数
- 合：把两个数合并成有序数组，再对有序数组进行合并，直到全副数组合并为一个残缺数组
- 工夫复杂度O(n*logN)
Array.prototype.mergeSort = function() { // 分（递归） const rec = (arr) => { if (arr.length === 1) return arr const mid = Math.floor(arr.length / 2) const left = arr.slice(0, mid) const right = arr.slice(mid, arr.length) const orderLeft = rec(left) const orderRight = rec(right) return merge(orderLeft, orderRight) } // 合 const merge = (orderLeft, orderRight) => { const res = [] while(orderLeft.length && orderRight.length) { if (orderLeft[0] < orderRight[0]) { res.push(orderLeft.shift()) } else { res.push(orderRight.shift()) } } while(orderLeft.length) { res.push(orderLeft.shift()) } while(orderRight.length) { res.push(orderRight.shift()) } return res } const res = rec(this) res.forEach((n, i) => this[i] = n)}const arr = [7,0,6,3,4,2,5,1]console.log('排序前', arr)arr.mergeSort()console.log('排序后', arr)疾速排序
- 分区：从数组中任意抉择一个“基准”，所有比基准小的元素放在基准后面，比基准大的元素放在基准前面。
- 递归：递归地对基准前后的子数组进行分区。
- 工夫复杂度O(n*logN)
Array.prototype.quickSort = function() { const rec = (arr) => { if (arr.length < 2) return arr const left = [] const right = [] const mid = arr[0] for(let i = 1; i < arr.length; i++) { if (arr[i] < mid) left.push(arr[i]) else right.push(arr[i]) } return [...rec(left), mid, ...rec(right)] } const res = rec(this) res.forEach((n, i) => this[i] = n)}const arr = [7,0,6,3,4,5,2,1]console.log('排序前', arr)arr.quickSort()console.log('排序后', arr)