专题21 冒泡排序 课件-2022届高三信息技术选考总复习

专题21 冒泡排序 一、什么是排序 排序的作用是把n个数据从小到大或从大到小重新排列，使得a(1)至a(n)中的数据有序。排序的方法有很多，重点掌握冒泡排序和选择排序。 1.n个数据一般需要经过______趟排序，变量i控制排序的趟数。第i趟排序时，前面i－1个数据已经有序，因此比较次数往往有n－(i－1)－1次，即______次。 2.变量j表示比较大小的元素位置，其中数组元素________表示第j－1个位置的数组元素，他位于a(j)的前面第一个元素，________位于a(j)的后面第一个元素。 n－1 n－i a(j－1) a(j＋1) 2 3.内部循环(j的循环)初值和终值决定了排序的区间和______。如果初值大于终值，初值往往是____，表示从____往____向后排序，若j的初值小于终值，初值往往是____，表示从____往____排序。第i趟排序中，待排序的数据个数有n－i＋1个，排序的次数即循环变量j的初值与终值差的绝对值为n－i。 4.冒泡排序是相邻两个元素进行比较，在判断是升序还是降序时，可以转换为前后两个元素的比较，如a(j)>a(j－1)表示他比他前面的数大，进行交换，因此是降序。如a(j)>a(j＋1)表示他比他后面的数大，进行交换，因此是升序。 方向 n 后 前 1 前 后 二、从后往前冒泡排序 (1)以n(n＝5)个元素从后往前冒泡升序排序为例，完成下列表格。 趟数 排序 区间 第1次 第2次 第3次 第4次 j终值 比较 次数 有序 区间 j j－1 j j－1 j j－1 j j－1 i＝1 ______ 5 4 4 3 3 2 2 1 2 4 ______ i＝2 ______ 5 4 4 3 3 2     3 3 ______ i＝3 ______ 5 4 4 3         4 2 ______ i＝4 ______ 5 4             5 1 ______ [1，n] [1，1] [2，n] [1，2] [3，n] [1，3] [4，n] [1，4] ①第i趟冒泡，把最大或最小的元素交换到第i位置，实现从第1个位置到第i个位置的元素有序。数组前面的元素先有序。 ②第i趟排序的区间是[i，n]，因此每趟排序的比较的位置(j的初值)为n。 (2)每趟排序的算法 第i趟的排序实现在区间