资源简介

备课组别 计算机 上课 日期 主备 教师 授课 教师
课题 插入和归并排序
教学 目标 掌握各种排序的算法分析
掌握排序的代码解析
学会排序应用
重点 排序的算法描述和演示
难点 排序的代码实现和应用
教法 讲授法、案例教学法、讨论法
教学设备 黑板 计算机 网络机房
教学 环节 教学活动内容及组织过程 个案补充
教 学 内 容 3、插入排序（Insertion Sort） 插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 3.1 算法描述 一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下： 从第一个元素开始，该元素可以认为已经被排序； 取出下一个元素，在已经排序的元素序列中从后向前扫描； 如果该元素（已排序）大于新元素，将该元素移到下一位置； 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置； 将新元素插入到该位置后； 重复步骤2~5。 3.2 动图演示 3.2 代码实现 function insertionSort(arr) { var len = arr.length; var preIndex, current; for (var i = 1; i < len; i++) { preIndex = i - 1; current = arr[i]; while (preIndex >= 0 && arr[preIndex] > current) { arr[preIndex + 1] = arr[preIndex]; preIndex--; } arr[preIndex + 1] = current;} return arr; } 4、归并排序（Merge Sort） 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 4.1 算法描述 把长度为n的输入序列分成两个长度为n/2的子序列； 对这两个子序列分别采用归并排序； 将两个排序好的子序列合并成一个最终的排序序列。 4.2 动图演示 4.3 代码实现 function mergeSort(arr) { var len = arr.length; if (len < 2) {return arr;} var middle = Math.floor(len / 2), left = arr.slice(0, middle), right = arr.slice(middle); return merge(mergeSort(left), mergeSort(right)); } function merge(left, right) {var result = []; while (left.length>0 && right.length>0) { if (left[0] <= right[0]) {result.push(left.shift());} else {result.push(right.shift()); } } while (left.length) result.push(left.shift()); while (right.length) result.push(right.shift()); return result; } 课后作业
板 书 设 计 考点分析 一、排序分类 二、算法分析和代码实现
教后札记

展开更多......

收起↑