(
课件网) 第五章 数据结构与算法 选修一《数据与数据结构》 5.3.2 常见的排序算法———冒泡排序 排序就是整理数据的序列，使其中元素按照某个值递增（或递减）的次序重新排列的操作。 排序是什么？ 太抽象了，无法理解 排序是什么？ 18 9 14 12 7 18 9 14 12 7 按数组形式进行存储 18 9 14 12 7 按链表形式进行存储 7 9 12 14 18 对数组进行升序排序 Python中的排序实现 第一种：列表自带的sort算法 列表自带的sort方法，只适用于列表，直接对列表进行排序，不会产生新的序列。 第二种：内建函数sorted方法 内建函数sorted方法，返回一个新的序列，原来序列依然存在。 a=[5,7,6,3,4,1,2] a.sort() print(a) #[1,2,3,4,5,6,7] a=[5,7,6,3,4,1,2] a.sort( reverse=True ) print(a) #[7,6,5,4,3,2,1] a=[5,7,6,3,4,1,2] b=sorted(a) print(a) #[5,7,6,3,4,1,2] print(b) #[1,2,3,4,5,6,7] 常见的排序算法 — 冒泡排序 冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上冒）”，较小的数“上冒（下沉）”的一种排序技术。 18 9 14 12 7 p[0] p[1] p[2] p[3] p[4] 9 18 14 12 7 9 14 18 12 7 9 14 12 18 7 9 14 12 7 18 冒泡排序算法对数组p做的第1遍加工 常见的排序算法 — 冒泡排序 9 14 12 7 18 9 14 12 7 18 9 12 14 7 18 9 12 7 14 18 冒泡排序算法对数组p做的第2遍加工 冒泡排序算法对数组p做的第3遍加工 9 12 7 14 18 9 12 7 14 18 9 7 12 14 18 常见的排序算法 — 冒泡排序 9 7 12 14 18 7 9 12 14 18 冒泡排序算法对数组p做的第4遍加工 对长度为5的数组p，一共需要4次加工 对长度为n的数组p ① 一共需要(n-1)次加工 ② 在第i遍加工当中，共需比较(n-i)次 ③ 总共需要比较次 ① 一共需要(n-1)次加工 常见的排序算法 — 冒泡排序 9 14 12 7 18 9 12 7 14 18 9 7 12 14 18 7 9 12 14 18 排好第1大的元素 排好第2大的元素 排好第4大的元素 排好第3大的元素 每一次加工，都是为了排好未排序数据当中最大的元素 常见的排序算法 — 冒泡排序 ② 在第i遍加工当中，共需比较(n-i)次 n=5 i=1 n-i=4 排好元素：i-1=0个 共有n-(i-1)=5个元素需要比较 两两比较需要比较4次 常见的排序算法 — 冒泡排序 ② 在第i遍加工当中，共需比较(n-i)次 n=5 i=2 n-i=3 排好元素：i-1=1个 共有n-(i-1)=4个元素需要比较 两两比较需要比较3次 常见的排序算法 — 冒泡排序 ② 在第i遍加工当中，共需比较(n-i)次 n=5 i=3 n-i=2 排好元素：i-1=2个 共有n-(i-1)=3个元素需要比较 两两比较需要比较2次 n=5 i=4 n-i=1 排好元素：i-1=3个 共有n-(i-1)=2个元素需要比较 两两比较需要比较1次 如果说一共有n个元素，第i遍加工当中 共有(n-i+1)个元素需要比较 两两比较需要比较(n-i)次 常见的排序算法 — 冒泡排序 ③ 总共需要比较次 第1遍加工：比较（n-1）次 第2遍加工：比较（n-2）次 … 第（n-2）遍加工：比较2次 第（n-1）遍加工：比较1次 ① 一共需要(n-1)次加工 Q：一共需要几次加工？ 算法时间复杂度为 总共需要比较次数S 冒泡排序算法实现 自主阅读课本第130页，思考一共需要几个变量？每个变量的作用是什么？ i：记录当前正进行的处理遍数 j：记录当前数组元素的下标。 每遍处理过程中， j总是从第一个数据元素，下标为0开始。 按每次加1的方式 直至j+1=n-i => j=n-i-1为止 每次比较p[j]与p[j+1]进行比较， 若p[j]>p[j+1]，则进行互换 i=2 j=0 j+1 j=1 j+1 j=2 j+1 j=3 j+1 i=1 i=1 i=1 i=1 j=0 j+1 j=1 j+1 j=2 j+1 i=2 i=2 i=3 i=3 i=4 j=0 j+1 j=1 j+1 j=0 j+1 每遍处理过程中， j总是从第一个数据元素，下标为0开始。 按每次加1的方式 直至j+1=n-i => j=n-i ... ...
