浙江嘉兴网站建设,做app和网站怎样,动漫设计与制作是做什么的,如何自己编写一个程序算法是什么#xff1f;、 算法#xff08;Algorithm#xff09; 代表着用系统的方法描述解决问题的策略机制#xff0c;可以通过一定规范的 输入#xff0c;在有限时间内获得所需要的 输出。 一个算法的好坏是通过 时间复杂度 与 空间复杂度 来衡量的。 简单来说#xff… 算法是什么、 算法Algorithm 代表着用系统的方法描述解决问题的策略机制可以通过一定规范的 输入在有限时间内获得所需要的 输出。 一个算法的好坏是通过 时间复杂度 与 空间复杂度 来衡量的。 简单来说时间复杂度 就是执行算法的 时间成本 空间复杂度 则是执行算法的 空间成本 。 时间复杂度 与 空间复杂度 都是用 “大O” 来表示写作 O(*)。有一点值得注意的是我们谈论复杂度一般谈论的都是时间复杂度。 常见时间复杂度的 “大O表示法” 描述有以下几种 时间复杂度非正式术语O(1)常数阶O(n)线性阶O(n2)平方阶O(log n)对数阶O(n log n)线性对数阶O(n3)立方阶O(2n)指数阶一个算法在N规模下所消耗的时间消耗从大到小如下 O(1) O(log n) O(n) O(n log n) O(n2) O(n3) O(2n) 常见的排序算法 1.O(n²) 的排序算法 冒泡排序 选择排序 插入排序 希尔排序 2.O(n log n) 的排序算法 归并排序 快速排序 堆排序 3.线性的排序算法 计数排序 桶排序 基数排序 冒泡排序 冒泡排序之所以叫冒泡排序是因为它每一种元素都像小气泡一样根据自身大小一点一点往数组的一侧移动。 算法步骤如下 比较相邻的元素。如果第一个比第二个大就交换他们两个 对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。这步做完后最后的元素会是最大的数 针对所有的元素重复以上的步骤除了最后一个 持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。 const bubbleSort arr { const len arr.length - 1 for (let i 0; i len; i) { /* 外循环为排序趟数len个数进行len-1趟 */ for (let j 0; j len - i; j) { /* 内循环为每趟比较的次数第i趟比较len-i次 */ if (arr[j] arr[j 1]) { /* 相邻元素比较若逆序则交换升序为左大于右逆序反之 */ [arr[j], arr[j 1]] [arr[j 1], arr[j]] } } } return arr} 选择排序Selection sort 是一种简单直观的排序算法。 选择排序的主要优点与数据移动有关。 如果某个元素位于正确的最终位置上则它不会被移动。 选择排序每次交换一对元素它们当中至少有一个将被移到其最终位置上因此对 n 个元素的表进行排序总共进行至多 n - 1 次交换。在所有的完全依靠交换去移动元素的排序方法中选择排序属于非常好的一种。 选择排序的算法步骤如下 在未排序序列中找到最小大元素存放到排序序列的起始位置 然后再从剩余未排序元素中继续寻找最小大元素然后放到已排序序列的末尾 以此类推直到所有元素均排序完毕。 代码实现 const selectionSort arr { const len arr.length let min for (let i 0; i len - 1; i) { min i /* 初始化未排序序列中最小数据数组下标 */ for (let j i 1; j len; j) { /* 访问未排序的元素 */ if (arr[j] arr[min]) { /* 找到目前最小值 */ min j /* 记录最小值 */ } } [arr[i], arr[min]] [arr[min], arr[i]] /* 交换位置 */ } return arr} 插入排序 插入排序Selection sort 是一种简单直观的排序算法。 它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。 插入排序的算法步骤如下 从第一个元素开始该元素可以认为已经被排序 取出下一个元素在已经排序的元素序列中从后向前扫描 如果该元素已排序大于新元素将该元素移到下一位置 重复步骤3直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置后 重复步骤2~5。 const insertionSort arr { const len arr.length let j, temp for (let i 0; i len; i) { j i /* 存储当前索引便于后续与数组其他元素对比 */ while (j 0 arr[j - 1] temp) { arr[j] arr[j - 1] j-- } [arr[j], arr[i]] [arr[i], arr[i]] } return arr} 希尔排序 希尔排序也称 递减增量排序算法是 插入排序 的一种更高效的改进版本。希尔排序是非稳定排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的 插入排序在对几乎已经排好序的数据操作时效率高即可以达到 线性排序 的效率 但插入排序一般来说是低效的因为插入排序每次只能将数据移动一位。 步长的选择是希尔排序的重要部分。 只要最终步长为1任何步长序列都可以工作。 算法最开始以一定的步长进行排序。 然后会继续以一定步长进行排序最终算法以步长为1进行排序。 当步长为1时算法变为普通插入排序这就保证了数据一定会被排序。 插入排序的算法步骤如下 定义一个用来分割的步长 按步长的长度K对数组进行K趟排序 不断重复上述步骤。 const shellSort arr { let gaps [5, 3, 1] // 定义步长以及分割次数 let len arr.length for (let g 0, gLen gaps.length; g gaps.length; g) { for (let i gaps[g]; i len; i) { let j for (j i; j gaps[g] arr[j - gaps[g]] arr[i]; j - gaps[g]) { arr[j] arr[j - gaps[g]] } [arr[i], arr[j]] [arr[j], arr[i]] } } return arr} 快速排序 快速排序Quicksort又称 划分交换排序partition-exchange sort 。 快速排序Quicksort 在平均状况下排序 n 个项目要 O(n log n) 次比较。在最坏状况下则需要 O(n2) 次比较但这种状况并不常见。事实上快速排序 O(n log n) 通常明显比其他算法更快因为它的 内部循环inner loop 可以在大部分的架构上很有效率地达成。 快速排序使用 分治法Divide and conquer 策略来把一个序列分为较小和较大的2个子序列然后递归地排序两个子序列。 快速排序的算法步骤如下 挑选基准值从数列中挑出一个元素称为 “基准”pivot 分割重新排序序列所有比基准值小的元素摆放在基准前面所有比基准值大的元素摆在基准后面与基准值相等的数可以到任何一边。在这个分割结束之后对基准值的排序就已经完成 递归排序子序列递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。 递归到最底部的判断条件是序列的大小是零或一此时该数列显然已经有序。 选取基准值有数种具体方法此选取方法对排序的时间性能有决定性影响。 const quickSort arr { const len arr.length if (len 2) { return arr } const pivot arr[0] const left [] const right [] for (let i 1; i len; i) { if (arr[i] pivot) { right.push(arr[i]) } if (arr[i] pivot) { left.push(arr[i]) } } return [...quickSort(left), pivot, ...quickSort(right)]} 三路快排 const quickSort arr { const len arr.length if (len 2) { return arr } let left [] let center [] let right [] let pivot arr[0] for (let i 0; i len; i) { if (arr[i] pivot) { left.push(arr[i]) } else if (arr[i] pivot) { center.push(arr[i]) } else { right.push(arr[i]) } } return [...quickSort(left), ...center, ...quickSort(right)]} 归并排序 第一种是 自上而下的递归 算法步骤如下 申请空间使其大小为两个已经排序序列之和该空间用来存放合并后的序列 设定两个指针最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素选择相对小的元素放入到合并空间并移动指针到下一位置 重复步骤3直到某一指针到达序列尾 将另一序列剩下的所有元素直接复制到合并序列尾。 具体实现 const merge (left, right) { let resArr [] while (left.length right.length) { if (left[0] right[0]) { resArr.push(left.shift()) } else { resArr.push(right.shift()) } } return resArr.concat(left, right)}const mergeSort arr { if (arr.length 1) { return arr } let middle Math.floor(arr.length / 2) let left arr.slice(0, middle) let right arr.slice(middle) return merge(mergeSort(left), mergeSort(right))} 自下而上的迭代 由于 分治法 的具体算法基本都能用 递归 跟 迭代 来实现所有才有这种写法其主要步骤如下 将序列每相邻两个数字进行 归并操作 形成 ceil(n / 2) 个序列排序后每个序列包含两/一个元素 若此时序列数不是1个则将上述序列再次归并形成 ceil(n / 4) 个序列每个序列包含四/三个元素 重复步骤2直到所有元素排序完毕即序列数为1。 具体实现如下 const merge (arr, startLeft, stopLeft, startRight, stopRight) { /* 建立左右子序列 */ let rightArr new Array(stopRight - startRight 1) let leftArr new Array(stopLeft - startLeft 1) /* 给左右序列排序 */ let k startRight for (let i 0, len rightArr.length; i len - 1; i) { rightArr[i] arr[k] k } k startLeft for (let i 0, len leftArr.length; i len - 1; i) { leftArr[i] arr[k] k } //设置哨兵值当左子列或右子列读取到最后一位时即Infinity可以让另一个剩下的列中的值直接插入到数组中 rightArr[rightArr.length - 1] Infinity leftArr[leftArr.length - 1] Infinity let m 0 let n 0 // 比较左子列和右子列第一个值的大小小的先填入数组接着再进行比较 for (let c startLeft; c stopRight; c) { if (leftArr[m] rightArr[n]) { arr[c] leftArr[m] m } else { arr[c] rightArr[n] n } }}const mergeSort arr { if (arr.length 1) { return arr } //设置子序列的大小 let step 1 let left let right while (step arr.length) { left 0 right step while (right step arr.length) { merge(arr, left, left step, right, right step) left right step right left step } if (right arr.length) { merge(arr, left, left step, right, arr.length) } step * 2 } return arr} 鱼头注迭代比起递归还是安全很多太深的递归容易导致堆栈溢出。 堆排序 堆排序的算法步骤如下 把无序数列构建成二叉堆 循环删除堆顶元素替换到二叉堆的末尾调整堆产生新的堆顶。 /* 堆下沉调整 */const adjustHeap (arr, parentIndex, length) { let temp arr[parentIndex] /* temp保存父节点值用于最后赋值 */ let childIndex 2 * parentIndex 1 /* 保存子节点位置 */ while (childIndex length) { /* 如果有右子节点且右子节点大于左子节点的值则定位到右子节点 */ if (childIndex 1 length arr[childIndex 1] arr[childIndex]) { childIndex } /* 如果父节点小于任何一个子节点的值直接退出循环 */ if (temp arr[childIndex]) { break; } /* 无序交换单向赋值即可 */ arr[parentIndex] arr[childIndex] parentIndex childIndex childIndex 2 * childIndex 1 } arr[parentIndex] temp}const heapSort arr { /* 把无序数列构建成最大堆 */ for (let i Math.floor(arr.length / 2); i 0; --i) { adjustHeap(arr, i, arr.length - 1) } for (let i arr.length - 1; i 0; --i) { /* 交换最后一个元素与第一个元素 */ [arr[i], arr[0]] [arr[0], arr[i]] /* 调整最大堆 */ adjustHeap(arr, 0, i) } return arr} 计数排序 计数排序Counting sort 是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组来存储输入的元素计数排序要求输入的数据必须是有确定范围的整数。 当输入的元素是 n 个 0 到 k 之间的整数时它的运行时间是 O(n k) 。计数排序不是比较排序排序的速度快于任何比较排序算法。 计数排序的算法步骤如下 找出待排序的数组中最大和最小的元素 统计数组中每个值为 i 的元素出现的次数存入数组 C 的第 i 项 对所有的计数累加从数组 C 中的第一个元素开始每一项和前一项相加 反向填充目标数组将每个元素 i 放在新数组的第 C[i] 项每放一个元素就将 C[i] 减去1 具体实现如下 const countSort arr { const C [] for (let i 0, iLen arr.length; i iLen; i) { const j arr[i] if (C[j] 1) { C[j] } else { C[j] 1 } } const D [] for (let j 0, jLen C.length; j jLen; j) { if (C[j]) { while (C[j] 0) { D.push(j) C[j]-- } } } return D} 桶排序Bucket Sort 跟 计数排序Counting sort 一样是一种稳定的线性时间排序算法不过这次需要的辅助不是计数而是桶。 工作的原理是将数列分到有限数量的桶里。每个桶再个别排序。当要被排序的数组内的数值是均匀分配的时候桶排序使用线性时间 O(n)。 桶排序的算法步骤如下 设置一个定量的数组当作空桶子 寻访序列并且把项目一个一个放到对应的桶子去 对每个不是空的桶子进行排序 从不是空的桶子里把项目再放回原来的序列中。 const bucketSort arr { let bucketsCount 10 /* 默认桶的数量 */ const max Math.max(...arr) /* 序列最大数字 */ const min Math.min(...arr) /* 数列最小数字 */ const bucketsSize Math.floor((max - min) / bucketsCount) 1 /* 桶的深度 */ const __buckets [] /* 空桶 */ for (let i 0, len arr.length; i len; i) { const index ~~(arr[i] / bucketsSize) /* 骚操作取数列中最大或最小的序列 */ if (!__buckets[index]) { __buckets[index] [] /* 创建子桶 */ } __buckets[index].push(arr[i]) let bLen __buckets[index].length while (bLen 0) { /* 子桶排序 */ if (__buckets[index][bLen] __buckets[index][bLen - 1]) { [__buckets[index][bLen], __buckets[index][bLen - 1]] [__buckets[index][bLen - 1], __buckets[index][bLen]] } bLen-- } } let buckets [] /* 真实序列 */ for (let i 0, len __buckets.length; i len; i) { if (__buckets[i]) { buckets.push(...__buckets[i]) } } return buckets} 基数排序 基数排序Radix sort 是一种非比较型整数排序算法其原理是将整数按位数切割成不同的数字然后按每个位数分别比较。由于整数也可以表达字符串比如名字或日期和特定格式的浮点数所以基数排序也不是只能使用于整数。 工作原理是将所有待比较数值正整数统一为同样的数字长度数字较短的数前面补零。然后从最低位开始依次进行一次排序。这样从最低位排序一直到最高位排序完成以后数列就变成一个有序序列。 const LSDRadixSort arr { const max Math.max(...arr) /* 获取最大值 */ let digit ${max}.length /* 获取最大值位数 */ let start 1 /* 桶编号 */ let buckets [] /* 空桶 */ while (digit 0) { start * 10 /* 入桶 */ for (let i 0, len arr.length; i len; i) { const index (arr[i] % start) if (!buckets[index]) { buckets[index] [] } buckets[index].push(arr[i]) /* 往不同桶里添加数据 */ } arr [] /* 出桶 */ for(let i 0; i buckets.length; i) { if (buckets[i]) { arr arr.concat(buckets[i]) } } buckets [] digit -- } return arr} 鸡尾酒排序是 冒泡排序 的一种变形。此算法与 冒泡排序 不同的地方在于从低到高然后从高到低而 冒泡排序 则仅从低到高去比较序列里的每个元素。它可以得到比 冒泡排序 稍微好一点的性能原因是 冒泡排序 只从一个方向进行比对由低到高每次循环只移动一个项目。 步骤跟冒泡算法差不多区别在于从起点到终点遍历完之后会进行一次终点到起点的遍历。 const cocktailSort arr { let i let left 0 let right arr.length - 1 while (left right) { for (i left; i right; i) if (arr[i] arr[i 1]) { [arr[i], arr[i 1]] [arr[i 1], arr[i]] } right-- for (i right; i left; --i) if (arr[i - 1] arr[i]) { [arr[i], arr[i - 1]] [arr[i - 1], arr[i]] } left } return arr} 转载于:https://www.cnblogs.com/zhouyideboke/p/11164024.html
