项目六 任务三 数组的排序与查找（课件）-《算法与程序设计--C#》（河北科学技术出版社）同步精品课堂

6.3 数组的排序与查找 算法与程序设计--C# 同步精品课堂 河北科学技术出版社 教学目标 一 掌握冒泡排序、插入排序、选择排序的原理 掌握排序算法和查找算法的C#实现代码 掌握二分查找法、顺序查找算法的原理 教学目标 01 02 03 掌握国家标准《机械制图》中有关图幅、比例、字体图线等基本规定。 教学重难点 二 教学难点 1、冒泡排序、插入排序、选择排序的原理及实现 2、二分查找法和顺序查找法的原理及实现 教学重点 插入排序和选择排序的区别 教学难点 导入新课 三 讨论： 生活中有很多需要排序和查找的情况，比如整理书架上的书籍、在电话簿中查找某个人的电话号码等。在计算机编程中，我们也经常需要对数组中的数据进行排序和查找。那么在编程语言中，有哪些排序算法和查找算法可以帮助我们来实现这些功能呢？ 任务一 1 数组的排序 新知讲授 四 数组排序 排序是编程中最常用的算法之一，排序的方法有很多种，可以使用算法对数组进行排序，常用的排序算法有选择法、冒泡法和插入法等 。 C#中的数组都是由System.Array类派生而来的引用对象，因此可以使用Array类中的各种属性或者方法对数组进行操作。 例如：Array类的Length属性，用来获取数组元素的长度； Array类的Rank属性，用来获取数组元素的维数； 设计菜单 新知讲授 四 选择排序法 第一次从待排序的元素中选出最小(或最大)的一个元素a，记录其位置的下标，然后将剩下的元素依次与元素a相比较，直到找到剩下的元素中最小的元素b(且元素b比元素a小)，二者交换位置(第一次循环结束)，以此类推，直到全部待排序的数据元素的个数为零。（以升序为例） ➽ 选择排序法的核心算法 void SelectionSort(int[] arr) { for (int i = 0; i < arr.Length - 1; i++) { 设计菜单 新知讲授 四 选择排序法 ➽ 选择排序法的核心算法 int minIndex = i; for (int j = i + 1; j < arr.Length; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } } 设计菜单 新知讲授 四 冒泡排序法 冒泡排序是一种最常用的排序算法，就像气泡一样越往上走越大，因此被人们形象地称为冒泡排序法。冒泡排序的过程很简单，首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第3个记录的关键字，依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止，上述过程称为第一趟冒泡排序，执行n-1次上述过程后，排序即可完成。 设计菜单 新知讲授 四 冒泡排序法 ➽ 冒泡排序法的核心算法 void BubbleSort(int[] arr) { for (int i = 0; i < arr.Length - 1; i++) { for (int j = 0; j < arr.Length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } 设计菜单 新知讲授 四 插入排序法 在待排序的数组里，从数组的第二个数字开始，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 ➽ 插入排序法的核心算法 void InsertionSort(int[] arr) { for (int i = 1; i < arr.Length; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } 设计菜单 新知讲授 四 顺序查找法 顺序查找是较简单的查找方法。思路也很简单，从数组的一边开始，逐个进行元素的比较，如果与给定的待查找元素相同，则查找成功，并返回其下标索引，如果整个扫描结束后，仍未找到相匹配的元素，则查找失败，返回-1。 int SequentialSearch(int[] arr, int target) { for (int i = 0; i < arr.Length; i++) { if (arr[i] == target) return i; } return -1; // 未找到 } ➽ 顺序查找法的核心算法 设计菜单 新知讲授 四 二分查找法 二分查找法是一种效率相对较高的查找方法。使用该算法的前提要求是有序数组，因为算法的核心思想是尽快的缩小搜索区间，这就需要保证在缩小范围的同时，不能有元素的遗漏。 二分查找的思想非常简单，有点类似分治的思想。二分查找针对的是一个有序的数据集合，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。 设计菜单 新知讲授 四 二分查找法 1、与mid值相等: 直接返回对应的位置 2、比mid值大: 由于元素有序，要查找的元素一定在左侧 (如有)，于是搜索区间变为左一半 3、比mid值小: 由于元素有序，要查找的元素一定在右侧 (如有)，于是搜索区间变为右一半 设计菜单 新知讲授 四 二分查找法 ➽ 二分查找法的核心算法 int BinarySearch(int[] arr, int target) { int left = 0, right = arr.Length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; else if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; // 未找到 } 师生互动 五 1、总结各种排序算法的原理和实现代码； 2、总结各种查找算法的原理和实现代码； 讨论 随堂练习 六 1、选择排序的基本思想是在未排序序列中找到________（或最大）元素，存放到排序序列的起始位置。 答案：最小 解析：选择排序每一轮都会找到最小值（最大值）。 2、插入排序将数组分为________和________两部分。 答案：已排序部分、未排序部分 解析：插入排序将数据分成已排序部分和未排序部分。 随堂练习 六 3、 以下关于冒泡排序算法的描述，正确的是（ ）​ A. 冒泡排序是一种不稳定的排序算法​ B. 冒泡排序在最好情况下的时间复杂度为 O (n)​ C. 冒泡排序每次比较相邻的两个元素，将较小的元素交换到后面​ D. 冒泡排序需要额外的存储空间来完成排序 答案：B 解析：冒泡排序是稳定排序算法；每次比较相邻元素，将较大元素交换到后面；冒泡排序空间复杂度为 O (1)，不需要额外大量存储空间；在数组已经有序时，冒泡排序只需要遍历一次数组，时间复杂度为 O (n)。 随堂练习 六 4、在插入排序中，已排序部分的初始状态是（ ） A. 空 B. 包含数组的第一个元素 C. 包含数组的最后一个元素 D. 包含数组的中间元素 答案：B 解析：插入排序分为已排序与未排序两部分，已排序包含数组的第一个元素。 随堂练习 六 5、 以下关于顺序查找算法的说法，错误的是（ ）​ A. 顺序查找算法适用于任何类型的数组，无论是否有序​ B. 顺序查找算法的时间复杂度始终为 O (n)​ C. 顺序查找算法从数组的第一个元素开始，逐个比较元素​ D. 顺序查找算法在找到目标元素后会立即返回 答案：B 解析：顺序查找算法在最好情况下，目标元素在数组第一个位置，时间复杂度为 O (1) ，平均和最坏情况下时间复杂度为 O (n) 。 随堂练习 六 6.冒泡排序算法在每一轮比较中都会确定一个元素的最终位置。（ ） 7.顺序查找法在查找失败时需要遍历整个数组。（ ） 答案：6. 对 7. 对 解析： 6.每一轮冒泡排序都会将未排序部分的最大（或最小，取决于排序顺序）元素交换到未排序部分的末尾（或开头），确定其最终位置。 7.顺序查找法最坏的情况下需要遍历整个数组。 课堂小结 七 谢谢 $$