一： 排序的概念
1 排序与搜索
排序算法（英语：Sorting algorithm）是一种能将一串数据依照特定顺序进行排列的一种算法。
2 排序算法的稳定性
1 稳定性：稳定排序算法会让原本有相等键值的纪录维持相对次序。 1 8 3 8 5 6 7 2 (4,1) (3,1) (3,7) (5,6) (3,7)(3,1) 2 如果一个排序算法是稳定的，当有两个相等键值的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。 3 不稳定排序算法可能会在相等的键值中改变纪录的相对次序
二 冒泡排序
1 什么是冒泡排序
1 冒泡排序（Bubble Sort）是一种简单的排序算法。 2 它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。 3 遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。 4 冒泡排序算法的工作原理如下： 1）比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。 2） 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。 3）除了最后一个，所有的元素重复以上的步骤。 4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
2 冒泡排序的分析
交换过程
3 冒泡排序的实现
def bubble_sort(alist): # 外层循环控制比较几轮 n = len(alist) for j in range(n - 1): # 内存循环控制交换 # -j是不再换已经排好的 for i in range(n - 1 - j): # 若前一个比后一个大，则换 if alist[i] > alist[i + 1]: alist[i], alist[i + 1] = alist[i + 1], alist[i] if __name__ == '__main__': li = [33, 11, 26, 78, 3, 9, 40] print(li) bubble_sort(li) print(li)
优化有序的情况，最优时间复杂度O(n)
def bubble_sort(alist): # 外层循环控制比较几轮 n = len(alist) for j in range(n - 1): # 定义计数器 count = 0 # 内存循环控制交换 # -j是不再换已经排好的 for i in range(n - 1 - j): # 若前一个比后一个大，则换 if alist[i] > alist[i + 1]: alist[i], alist[i + 1] = alist[i + 1], alist[i] # 计数器 count += 1 if count == 0: return
4 时间复杂度
最优时间复杂度：O(n)
最坏时间复杂度：O(n²)
稳定性：稳定
5 评价
优点：稳定，简单
缺点：效率不很高，运行时间较长
三：选择排序
1 选择排序的概念
1 选择排序（Selection sort）是一种简单直观的排序算法。 2 选择排序算法的工作原理如下： 1）首先在序列中找到最小或最大元素，存放到排序序列的前或后。 2）然后，再从剩余元素中继续寻找最小或最大元素。 3）然后放到已排序序列的末尾。 4）以此类推，直到所有元素均排序完毕。
2 选择排序分析
排序过程
3 选择排序的实现
# alist = [3, 11, 26, 26,7, 3, 9, 4] # 选择排序把数据当成2部分 # alist = [3, 11, 26, 26,7, 9, 4] # alist = [3, 4 11, 26, 26,7, 9] # 怎么找到最小值？ 索引min = 0 # 最终min = 0 # min = 1开始 # min = 6 # alist[1] alist[6] def select_sort(alist): n = len(alist) # 外层控制比较几轮 for j in range(n - 1): min_index = j # 内层控制元素比较和更新索引 for i in range(j + 1, n): # 进行比较 if alist[min_index] > alist[i]: # 更新索引 min_index = i # 退出循环后，交换数据 alist[j], alist[min_index] = alist[min_index], alist[j] if __name__ == '__main__': li = [3, 11, 26, 26, 7, 3, 9, 4] print(li) select_sort(li) print(li)
4 时间复杂度
最优时间复杂度：O(n²)
最坏时间复杂度：O(n²)
稳定性：不稳定
5 评价
优点：移动次数少
缺点：比较次数多
四 插入排序
1 概念：
1 插入排序（Insertion Sort）是一种简单直观的排序算法。 2 插入排序算法的工作原理如下： 3 构建有序序列 4 在已排序序列中扫描未排序数据 5 找到相应位置并插入
2 插入排序的分析
排序过程：
3 插入排序的实现
# 插入排序 def insert_sort(alist): n = len(alist) # 外层循环控制从右边取多少元素 for j in range(1, n): # i = [1，2，3...] i = j # 内存循环 while i > 0: if alist[i] < alist[i - 1]: alist[i], alist[i - 1] = alist[i - 1], alist[i] # 控制循环结束 i -= 1 else: break if __name__ == '__main__': li = [54, 26, 93, 17, 77, 31, 44, 55, 20] print(li) insert_sort(li) print(li)
4 时间复杂度
最优时间复杂度：O(n)
最坏时间复杂度：O(n²)
稳定性：稳定
5 评价
优点：稳定，比较快
缺点：比较次数不确定，数据量越大，该算法越渣
五：希尔排序
1 概念
1 希尔排序（Shell Sort）是插入排序的一种，也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。 2 希尔排序是非稳定排序算法，是DL．Shell于1959年提出的。 3 希尔排序算法的工作原理如下： 1）把记录按下标的一定增量分组，对每组使用直接插入排序算法排序。 2）随着增量逐渐减少，每组包含的关键词越来越多。 3）当增量减至1时，整个文件恰被分成一组，算法便终止。
2 希尔排序分析
排序过程：
增量用gap代表，第一次增量3是将数据分3组
3 希尔排序的实现
#希尔排序 def shell_sort(alist): n=len(alist) #假如gap=n/2 gap=n//2 #控制gap不断缩小 #插入排序 #这里从gap开始到最后比较 for j in range(gap,n): # i=[gap,gap+1] i=j while i>0: if alist < alist[i-gap]: alist[i],alist[i-gap]=alist[i-gap],alist[i] i-=gap else: break gap //=2 if __name__ == '__main__': li=[54,26,93,17,77,31,44,55,20] print(li) shell_sort(li) print(li)
4 时间复杂度
最优时间复杂度：根据步长序列的不同而不同，最优是1.3，根据数学运算算出的gap
最坏时间复杂度：O(n²)
稳定性：不稳定
5 评价
优点：平均时间短，数据移动少
缺点：不稳定
六、快速排序
1 概念
1 快速排序（Quicksort），又称划分交换排序（partition-exchange sort）。 2 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。 3 整个排序过程可以递归进行，以此达到整个数据变成有序序列。 4 快速排序算法的工作原理如下： 1）从数列中挑出一个元素，称为"基准"（pivot）。 2）重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。 3）在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。 4）递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
2 快速排序分析
3 快排实现
# 快排 # first理解为第一个位置的索引，last是最后位置索引 def quick_sort(alist, first, last): # 递归终止条件 if first >= last: return # 设置第一个元素为中间值 mid_value = alist[first] # low指向 low = first # high high = last # 只要low小于high就一直走 while low < high: # high大于中间值，则进入循环 while low < high and alist[high] >= mid_value: # high往左走 high -= 1 # 出循环后，说明high小于中间值,low指向该值 alist[low] = alist[high] # high走完了，让low走 # low小于中间值，则进入循环 while low < high and alist[low] < mid_value: # low向右走 low += 1 # 出循环后，说明low大于中间值,high指向该值 alist[high] = alist[low] # 退出整个循环后，low和high相等 # 将中间值放到中间位置 alist[low] = mid_value # 递归 # 先对左侧快排 quick_sort(alist, first, low - 1) # 对右侧快排 quick_sort(alist, low + 1, last) if __name__ == '__main__': li = [54, 26, 93, 17, 77, 31, 44, 55, 20] print(li) quick_sort(li, 0, len(li) - 1) print(li)
4 时间复杂度
1 最优时间复杂度：O(nlogn) 1）遍历每个数是O(n)，访问每个数是O(logn)，最终是O(nlogn) 2）可以转换为求二叉树深度的思想 2 最坏时间复杂度：O(n²) 3 稳定性：不稳定
5 评价
优点：效率高，数据移动比较少，数据量越大，优势越明显
缺点：不稳定
七 归并排序
1 概念
1 归并排序（MergeSort）是采用分治法的一个非常典型的应用。 2 归并排序的思想就是先递归分解数组，再合并数组。 3 归并排序算法的工作原理如下： 1）将数组分解最小之后，然后合并两个有序数组。 2）比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。 3）然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
2 归并排序分析
排序过程
3 归并排序代码实现
# 归并排序 def merge_sort(alist): n = len(alist) # 递归结束条件 if n <= 1: return alist # 中间位置 mid = n // 2 # 递归拆分左侧 left_li = merge_sort(alist[:mid]) # 递归拆分右侧 right_li = merge_sort(alist[mid:]) # 需要2个游标，分别指向左列表和右列表第一个元素 left_point, right_point = 0, 0 # 定义最终返回的结果集 result = [] # 循环合并数据 while left_point < len(left_li) and right_point < len(right_li): # 谁小谁放前面 if left_li[left_point] <= right_li[right_point]: # 放进结果集 result.append(left_li[left_point]) # 游标移动 left_point += 1 else: result.append(right_li[right_point]) right_point += 1 # 退出循环时，形成左右两个序列 result += left_li[left_point:] result += right_li[right_point:] return result if __name__ == '__main__': li = [54, 26, 93, 17, 77, 31, 44, 55, 20] print(li) sort_li = merge_sort(li) print(li) print(sort_li)
4 时间复杂度
最优时间复杂度：O(nlogn)
最坏时间复杂度：O(nlogn)
稳定性：稳定
5 评价
优点：稳定，数据量越大越优秀 缺点：需要额外空间
6 常见的算法效率
1 快速排序消耗空间因为每次递归时，要保持一些数据
最优情况：每一次平均分组的情况 O(logn)
最坏情况：退化为冒泡排序的情况 O(n)
2 堆排序是结合二叉树去做的
八 搜索
1 搜索的引入
搜索是在一个数据集合中找到一个特定数据的算法
搜索通常的答案是真的或假的
搜索的常见方法有二分查找、哈希查找等
2 二分法查找
1 二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好。 2 缺点是要求待查表为有序表 3 因此，折半查找方法适用于不经常变动而查找频繁的有序列表。 4 二分查找的工作原理如下： 1）首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功。 2）否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。 3）重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功
3 二分法查找的实现
l 递归实现
# 递归的实现 def my_search(alist, item): n = len(alist) # 递归结束条件 if n > 0: # 折半 mid = n // 2 # 判断中间元素是否为要查的元素 if alist[mid] == item: return True # 判断中间元素与item的大小 elif item < alist[mid]: # 继续递归查找 return my_search(alist[:mid], item) else: return my_search(alist[mid + 1:], item) return False
if __name__ == '__main__': # 2个注意点：必须用有序的顺序表 li = [17, 20, 26, 31, 44, 54, 55, 77, 93] print(my_search(li, 17)) print(my_search2(li, 111))
l 非递归实现
# 非递归实现 def my_search2(alist, item): n = len(alist) # 起始，0 first = 0 # 结束位置 last = n - 1 while first <= last: # 折半 mid = (first + last) // 2 # 判断中间元素 if alist[mid] == item: return True elif item < alist[mid]: last = mid - 1 else: first = mid + 1 return False
if __name__ == '__main__': # 2个注意点：必须用有序的顺序表 li = [17, 20, 26, 31, 44, 54, 55, 77, 93] print(my_search(li, 17)) print(my_search2(li, 111))
4 时间复杂度
最优时间复杂度：O(1)
最坏时间复杂度：O(logn)