介绍自己做衣服的网站,怎么下载网站的视频,盐城seo优化,wordpress获取文章评论一、插入排序
插入排序是一种简单直观的排序算法。它的原理是通过构建有序序列#xff0c;对于未排序数据#xff0c;在已排序序列中从后向前扫描#xff0c;找到相应位置并插入。 #mermaid-svg-v2YbPqchr8qWCPvn {font-family:trebuchet ms,verdana,arial,san…一、插入排序
插入排序是一种简单直观的排序算法。它的原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。 #mermaid-svg-v2YbPqchr8qWCPvn {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-v2YbPqchr8qWCPvn .error-icon{fill:#552222;}#mermaid-svg-v2YbPqchr8qWCPvn .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-v2YbPqchr8qWCPvn .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-v2YbPqchr8qWCPvn .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-v2YbPqchr8qWCPvn .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-v2YbPqchr8qWCPvn .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-v2YbPqchr8qWCPvn .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-v2YbPqchr8qWCPvn .marker{fill:#333333;stroke:#333333;}#mermaid-svg-v2YbPqchr8qWCPvn .marker.cross{stroke:#333333;}#mermaid-svg-v2YbPqchr8qWCPvn svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-v2YbPqchr8qWCPvn .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-v2YbPqchr8qWCPvn .cluster-label text{fill:#333;}#mermaid-svg-v2YbPqchr8qWCPvn .cluster-label span{color:#333;}#mermaid-svg-v2YbPqchr8qWCPvn .label text,#mermaid-svg-v2YbPqchr8qWCPvn span{fill:#333;color:#333;}#mermaid-svg-v2YbPqchr8qWCPvn .node rect,#mermaid-svg-v2YbPqchr8qWCPvn .node circle,#mermaid-svg-v2YbPqchr8qWCPvn .node ellipse,#mermaid-svg-v2YbPqchr8qWCPvn .node polygon,#mermaid-svg-v2YbPqchr8qWCPvn .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-v2YbPqchr8qWCPvn .node .label{text-align:center;}#mermaid-svg-v2YbPqchr8qWCPvn .node.clickable{cursor:pointer;}#mermaid-svg-v2YbPqchr8qWCPvn .arrowheadPath{fill:#333333;}#mermaid-svg-v2YbPqchr8qWCPvn .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-v2YbPqchr8qWCPvn .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-v2YbPqchr8qWCPvn .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-v2YbPqchr8qWCPvn .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-v2YbPqchr8qWCPvn .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-v2YbPqchr8qWCPvn .cluster text{fill:#333;}#mermaid-svg-v2YbPqchr8qWCPvn .cluster span{color:#333;}#mermaid-svg-v2YbPqchr8qWCPvn div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-v2YbPqchr8qWCPvn :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 有元素 无元素 无元素 初始数组 未排序区间 选择一个待插入元素 已排序区间 插入元素到已排序区间 重新确定未排序区间 排序完成 这个流程图描述了插入排序的过程。初始数组经过选择一个待插入元素的步骤并判断是否有元素。如果有元素则将它插入到已排序区间并重新确定未排序区间。如果没有元素则排序完成。
js实现
function insertionSort(arr) {// 循环每个元素从第二个元素开始for (let i 1; i arr.length; i) {// 当前元素let current arr[i];// 设置当前元素的前一个元素的下标let j i - 1;// 当前元素与它前面的元素比较如果前面的元素较大则向右移动while (j 0 arr[j] current) {arr[j 1] arr[j];j--;}// 将当前元素插入到正确的位置arr[j 1] current;}// 返回排序后的数组return arr;
}let array [5, 3, 8, 2, 1, 4];
console.log(insertionSort(array)); // 输出[1, 2, 3, 4, 5, 8]这里使用插入排序算法对数组 [5, 3, 8, 2, 1, 4] 进行排序。首先第一个元素 5 被标记为已排序序列从第二个元素开始依次与已排序序列中的元素比较找到合适的位置插入。在每一轮循环中当前元素会与已排序序列中的元素从后向前依次比较直到找到插入位置。
初始数组[8, 3, 5, 1, 4]
插入元素过程描述排序后的数组8初始状态[8, 3, 5, 1, 4]3将3插入到前面比它大的数之前[3, 8, 5, 1, 4]5将5插入到前面比它大的数之前[3, 5, 8, 1, 4]1将1插入到前面比它大的数之前[1, 3, 5, 8, 4]4将4插入到前面比它大的数之前[1, 3, 4, 5, 8]
最终排序结果[1, 3, 4, 5, 8]
插入排序的过程可以类比现实生活中整理扑克牌的过程。初始时我们手里有一摞乱序的扑克牌。我们从第二张牌开始将其与前面的牌依次比较找到合适的位置插入。重复这个过程直到所有的牌都被按照顺序放置在手上。每次比较时左手持有的牌都是已排序的右手持有的牌都是未排序的。这个过程就是插入排序的模拟。
二、使用二分法优化插入排序
可以使用二分法优化上述插入排序算法。二分法优化的思想是将插入排序中的线性查找部分改为二分查找从而减少比较的次数提高排序效率。
以下是使用二分法优化的插入排序算法
function insertionSort(arr) {for (let i 1; i arr.length; i) {let current arr[i];let left 0; // 排序部分的起始位置let right i - 1; // 排序部分的结束位置// 使用二分查找找到插入位置while (left right) {let mid Math.floor((left right) / 2);if (arr[mid] current) {right mid - 1;} else {left mid 1;}}// 将大于current的元素右移for (let j i - 1; j left; j--) {arr[j 1] arr[j];}// 插入到正确的位置arr[left] current;}return arr;
}使用二分法优化后排序效率会有所提高但在数据量较小时可能没有明显的优势。因此在实际应用中需要根据具体情况选择是否使用二分法优化。
