摘要:排序算法主要针对的是数组,所以,在开始学习之前,我们先自己新建一种数据结构来方便我们的学习。统计执行次数冒泡排序比较相邻两个数的大小,如果前面的数大于后面,则交换这两个数的位置。所以我们把数列分割成不超过两个元素的数组,然后将其合并。
排序算法主要针对的是数组,所以,在开始学习之前,我们先自己新建一种数据结构来方便我们的学习。
function ArrayData () { let ret = [] this.times = 0 // 统计执行次数 this.push = (item) => { ret.push(item) } this.toString = () => { return ret.join() } } const arr = [34, 11, 45, 22, 31, 99, 68, 54]冒泡排序
比较相邻两个数的大小,如果前面的数大于后面,则交换这两个数的位置。要排序n个数字,需要经历n-1次的遍历。
按照字面要求,我们写出来的代码是这样的
function ArrayData () { // ...... this.bubbleSort = function () { let length = ret.length; for (let i = 0; i < length; i++) { for (let j = 0; j < length - 1; j++) { this.times++ if (ret[j] > ret[j + 1]) { [ret[j], ret[j + 1]] = [ret[j + 1], ret[j]] } } } } } let tmp = new ArrayData() arr.forEach((item) => { tmp.push(item) }) tmp.bubbleSort() console.log(tmp.times) // 56
显然这种简单粗暴的排序方式有很大的提升空间,比如,我们可以检测每次排序,如果顺序已经排列成功,就没必要执行之后的循环了。
function ArrayData () { // ...... this.bubbleSort = function () { let length = ret.length; for (let i = 0; i < length; i++) { let change = false for (let j = 0; j < length - 1; j++) { this.times++Ï if (ret[j] > ret[j + 1]) { [ret[j], ret[j + 1]] = [ret[j + 1], ret[j]] change = true } } if (!change) { break } } } } let tmp = new ArrayData() arr.forEach((item) => { tmp.push(item) }) tmp.bubbleSort() console.log(tmp.times) // 21
其实还是有优化的空间的。举个例子,假设一共8个数,第一轮循环,会把最大的数冒泡排到第8位,第二轮循环,会把第二大的数排到第7位,所以,本轮循坏其实没必要考虑最后一位了。同理,下一轮循环就不需要考虑后两位。改进后的代码如下:
function ArrayData () { // ...... this.bubbleSort = function () { let length = ret.length; for (let i = 0; i < length; i++) { let change = false for (let j = 0; j < length - 1 - i; j++) { this.times++ if (ret[j] > ret[j + 1]) { [ret[j], ret[j + 1]] = [ret[j + 1], ret[j]] change = true } } if (!change) { break } } } } let tmp = new ArrayData() arr.forEach((item) => { tmp.push(item) }) tmp.bubbleSort() console.log(tmp.times) // 18选择排序
遍历数组,找出最小的数排在第一位,第二轮循环找出第二小的数放在第二位,以此类推。
function ArrayData () { // ...... this.selectionSort = function () { let length = ret.length for (let i = 0; i < length - 1; i++) { let minIndex = i for (let j = i; j < length; j++) { if (ret[j] < ret[minIndex]) { minIndex = j } } if (i !== minIndex) { [ret[i], ret[minIndex]] = [ret[minIndex], ret[i]] } } } } let tmp = new ArrayData() arr.forEach((item) => { tmp.push(item) }) tmp.selectionSort()插入排序
把数组分成前后两部分,前面的一部分是排好序的,然后分别把后面一部分的数字插入到前面排好序的数组中。所以,刚开始时设定第一个元素为排好序的部分,分别把后面的数字插入进来。
function ArrayData () { // ...... this.insertSort = function () { let length = ret.length let j for (let i = 1; i < length; i++) { let currentNumber = ret[i] for (j = i - 1; j >= 0 && ret[j] > currentNumber; j--) { ret[j + 1] = ret[j] } ret[j + 1] = currentNumber } } } let tmp = new ArrayData() arr.forEach((item) => { tmp.push(item) }) tmp.insertSort()快速排序
选一个数作为基准数,遍历数列,把比它
放到他前面,比他小的放到他后面,然后再对基准数前后的数列递归上述操作,直到数列长度为1。
function ArrayData () { // ...... this.quickSort = function () { quick(ret, 0, ret.length - 1); function quick(array, left, right) { let index if (array.length > 1) { index = partition(array, left, right) if (left < index - 1) { quick(array, left, index - 1) } if (right > index) { quick(array, index, right) } } return array } function partition(array, left, right) { let pivot = array[Math.floor((right + left) / 2)], i = left, j = right; while (i <= j) { while (array[i] < pivot) { i++ } while (array[j] > pivot) { j-- } if (i <= j) { swap(array, i, j); i++; j--; } } return i } function swap(array, i, j) { [array[i], array[j]] = [array[j], array[i]] } } } let tmp = new ArrayData() arr.forEach((item) => { tmp.push(item) }) tmp.quickSort()
一句话实现快速排序。选择第一个元素作为参考元素,利用filter把数组分成大于参考元素和小于参考元素的两个数组,并对这两个数组递归调用快排函数。
function quickSort(arr) { return arr.length <= 1 ? arr : quickSort(arr.slice(1).filter((item) => item <= arr[0])).concat(arr[0], quickSort(arr.slice(1).filter((item) => item > arr[0]))) }希尔排序
希尔排序是把数组按下标的一定增量分组,对每组进行插入排,随着增量逐渐减少,每个数组的长度越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
function ArrayData () { // ...... this.shellSort = function () { let length = ret.length for (let step = Math.floor(length / 2); step > 0; step = Math.floor(step / 2)) { for (let i = 0; i < step; i++) { shellInsertSort(i, step) } } function shellInsertSort(index, step) { let length = ret.length let j for (let i = index; i < length; i += step) { let currentNumber = ret[i] for (j = i - step; j >= 0 && ret[j] > currentNumber; j -= step) { ret[j + step] = ret[j] } ret[j + step] = currentNumber } } } } let tmp = new ArrayData() arr.forEach((item) => { tmp.push(item) }) tmp.shellSort()归并排序
归并排序采用分治的思想,将已有序的子序列合并,得到完全有序的序列。所以我们把数列分割成不超过两个元素的数组,然后将其合并。
function ArrayData () { // ...... this.mergeSort = function () { ret = mergeSortFun(ret) function mergeSortFun(arr) { let length = arr.length if (length <= 1) { return arr } let mid = Math.floor(length / 2), left = arr.slice(0, mid), right = arr.slice(mid, length) return mengeConnect(mergeSortFun(left), mergeSortFun(right)) } function mengeConnect(left, right) { let leftIndex = 0, rightIndex = 0, result = [] while (leftIndex < left.length && rightIndex < right.length) { result.push(left[leftIndex] < right[rightIndex] ? left[leftIndex++] : right[rightIndex++]) } while (leftIndex < left.length) { result.push(left[leftIndex++]) } while (rightIndex < right.length) { result.push(right[rightIndex++]) } return result } } } let tmp = new ArrayData() arr.forEach((item) => { tmp.push(item) }) tmp.mergeSort()
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/95585.html
摘要:探讨判断横竖屏的最佳实现前端掘金在移动端,判断横竖屏的场景并不少见,比如根据横竖屏以不同的样式来适配,抑或是提醒用户切换为竖屏以保持良好的用户体验。 探讨判断横竖屏的最佳实现 - 前端 - 掘金在移动端,判断横竖屏的场景并不少见,比如根据横竖屏以不同的样式来适配,抑或是提醒用户切换为竖屏以保持良好的用户体验。 判断横竖屏的实现方法多种多样,本文就此来探讨下目前有哪些实现方法以及其中的优...
摘要:栈被称为一种后入先出的数据结构。散列使用的数据结构叫做散列表。这些操作需要求助于其他数据结构,比如下面介绍的二叉查找树。 前言 在过去的几年中,得益于Node.js的兴起,JavaScript越来越广泛地用于服务器端编程。鉴于JavaScript语言已经走出了浏览器,程序员发现他们需要更多传统语言(比如C++和Java)提供的工具。这些工具包括传统的数据结构(如链表,栈,队列,图等),...
阅读 3219·2021-10-21 17:50
阅读 3223·2021-10-08 10:05
阅读 3345·2021-09-22 15:04
阅读 545·2019-08-30 14:00
阅读 1916·2019-08-29 17:01
阅读 1477·2019-08-29 15:16
阅读 3206·2019-08-26 13:25
阅读 829·2019-08-26 11:44