[py]数据结构和算法-冒泡排序

用Python实现的数据结构与算法

数据结构和算法可以培养一个人的逻辑思维(推荐几本书)

逻辑思维培养

严蔚敏的数据结构(排序 查找 列表 堆栈 队列 树的简单部分) 大话数据结构 数据结构与算法分析 (豆瓣) 9.2分 算法 (豆瓣) 9.3分 算法导论 (豆瓣) 9.4分

等差数列
(首项+尾项) * (项数的一半)

复杂度: 评定算法之间对比的优劣 复杂度: 为了评定算法之间对比的优劣. 执行完算法所用的次数. 数组有n项,复杂度就是n*n 时间复杂度(执行完算法所需的时间,一般说的复杂度是指这个) 空间复杂度 冒泡算法

软件需要关注的算法(冒泡 快排) + 数据结构(list dict(hash表) 链表) + 网络(tcp三次握手 http常见状态 header) + 操作系统

冒泡排序 复杂度O(n^2)(一般指的时间复杂度, 空间复杂度指的是占用磁盘空间,一般我们不理睬) 稳定性: 冒泡是稳定的

实现效果: 第一次排序最大的归到最后一位, 第二次排序,次大的归到倒数第二位.
思路实现:

比较过程

实现冒泡排序并优化 arr = [3, 5, 1, 32, 4] for j in range(4): for i in range(4): if arr[i] < arr[i + 1]: arr[i + 1], arr[i] = arr[i], arr[i + 1] print arr -- [32, 5, 4, 3, 1] - 方法2 arr = [3, 5, 1, 32, 4] j = 0 while j < len(arr) - 1: for i in range(len(arr) - 1): if arr[i] > arr[i + 1]: arr[i + 1], arr[i] = arr[i], arr[i + 1] j += 1 print arr 最终冒泡-经过优化

算法复杂度: O(n^2)

- 方法3-优化,比较规范 arr = [3,2,11,13,9] l = len(arr) - 1 #为何要减去1呢,因为如果10个数字, 第九个数字和最后一个数字比是第九次, 为了优化,所以减去1 for i in range(l): for j in range(l-i): if arr[j] > arr[j+1]: arr[j],arr[j+1] = arr[j+1],arr[j] print(arr)