算法的稳定性
冒泡排序
# 冒泡排序
# 1 思想: 相邻位置两个元素比较, 前面的元素比后面的元素大则交换, 把最大的数给找到
# 经过一轮一轮的比较最终把序列给排序
# 2 关键点1: 两层for循环 外层循环控制多少轮 内层for循环控制比较次数
# 3 关键点2: 若遍历一遍没有数字交换 说明序列有序,退出本轮
# 4 稳定性: 相邻两元素若相等则不交换,说明能保持原有序列的顺序 所以是算法是稳定的
# 5 算法复杂度: O(n^2), 最差时间复杂度O(n^2), 最优时间复杂度O(n)# 冒泡从小到大排序,实现步骤
# 1 数列长度 n
# 2 外层循环控制 轮次 j / n-1
# 3 内层循环控制 比较次数(相邻位置2个元素比较次数) i / n-j-1
# 4 若遍历一遍没有数字交换 说明序列有序 退出本轮次def bubble_sort(alist):length=len(alist)count=0for j in range(length-1):for i in range(length-j-1):if alist[i]>alist[i+1]:alist[i],alist[i+1]=alist[i+1],alist[i]count+=1if count==0:breakreturn alistif __name__=='__main__':bubble_sort([2,6,7,5,8,9])print(bubble_sort([2,6,7,5,8,9]))
选择排序
# 选择排序
# 1 思想: 第1个轮次: 序列中选择一个最小的放在第1个位置
# 第2轮次: 序列中选择一个第2小最的元素放在第2个位置
# 经过一轮一轮的比较最终把序列给排序# 2 关键点1: 两层for循环 外层循环控制多少轮 内层for循环控制比较次数
# 3 稳定性: 不稳定算法(数值相等的数据 前后位置可能会互换)
# 4 算法复杂度: O(n^2), 最差时间复杂度O(n^2), 最优时间复杂度O(n^2)# 选择从小到大排序,实现步骤
# 1 数列长度 n
# 2 外层循环控制 轮次 j / n-1
# 3 内层循环控制 比较次数(相邻位置2个元素比较次数) i / (j+1, n)
# 4 若假定的最小值下标发生变化, 就进行交换 min_index!=j
def select_sort(alist):"""选择排序"""# 列表的长度n = len(alist)# 外层循环 控制比较轮数for j in range(0, n-1):# 假定的最小值的下标min_index = j# 内层循环 控制比较次数for i in range(j+1, n):# 进行比较获得最小值if alist[i] < alist[min_index]:min_index = i# 若假定的最小值下标发生变化, 就进行交换if min_index != j:alist[j], alist[min_index] = alist[min_index], alist[j]if __name__ == '__main__':alist = [5, 3, 4, 7, 2]select_sort(alist)print(alist)def select_sort3(alist):n = len(alist)for i in range(0, n-1):for j in range(i+1, n):if alist[j] < alist[i]:alist[i], alist[j] = alist[j], alist[i]def select_sort2(alist):n = len(alist)for j in range(0, n-1):for i in range(j+1, n):if alist[i] < alist[j]:alist[i], alist[j] = alist[j], alist[i]
插入法排序
# 选择排序
# 1 思想: 有2个序列,有序序列和无序序列, 将无序序列中的每一个元素插入到有序序列
# 经过一轮一轮的比较最终把序列给排序# 2 关键点1: 有序序列遍历是从后向前
# 3 稳定性: 稳定算法(数值相等的数据 前后位置不互换)
# 4 算法复杂度: O(n^2), 最差时间复杂度O(n^2), 最优时间复杂度O(n)# 插入法从小到大排序,实现步骤
# 1 数列长度 n
# 2 外层循环控制 轮次 j / (1,n)
# 3 内层循环控制 插入位置 for i in range(j, 0, -1): if alist[i] < alist[i-1]:
# 4 若待插入数据小于有序数据,则插入; 若待插入数据大于有序数据,则breakdef insert_sort(alist):n = len(alist)#外层控制循环轮数for j in range(1,n):#第一个元素作为有序序列，从第二个元素开始进行比较for i in range(j,0,-1):# alist[i]为待插入的数据# 若待插入数据小于有序数据,则插入; 若待插入数据大于有序数据,则breakif alist[i]<alist[i-1]:#大于或者小于号控制降序或者升序# alist[i-1],alist[i]=alist[i],alist[i-1]#同样的效果，就是互换位置alist[i], alist[i - 1] = alist[i - 1], alist[i]else:breakif __name__ == '__main__':alist = [1, 100, 99, 20, 5, 1000]insert_sort(alist)print(alist)
快速排序
# start作用: 从左向右找比 mid 值更大的，往右面放
# end作用: 从右往左找比 mid 值小的，往左放# 快速排序思路
# 1 准备界限值
# 2 从右边寻找大于界限值的值, 找到后赋值给右边
# 3 从左边寻找大于界限值的值, 找到后赋值给右边
# 4 右边和右边的游标都发生变化了 判断是否重叠# 若不重叠 重复23,直到重叠# 若不重叠 1个轮次完毕 边界值加入序列
# 5 递归调用 # 界限值左边序列递归 界限值右边序列递归# 编程具体步骤:
# 1 准备界限值
# 1-1递归结束条件 if start >= end: 1-2界限值 mid = alist[start] 1-3左右游标left right
# 2 从右边寻找大于界限值的值, 找到后赋值给右边
# 2-1 while alist[right] >= mid and : right -= 1 / 2-2 alist[left] = alist[right]
# 3 从左边寻找大于界限值的值, 找到后赋值给右边
# 3-1 while alist[left] < mid and : left += 1 /3-2 alist[right] = alist[left]# 4 右边和右边的游标都发生变化了 判断是否重叠; 若不重叠 重复23, 直到重叠, 1个轮次完毕
# 不重叠4-1while left < right: / 挑出循环 4-2 alist[left] = mid# 5 递归调用
# 界限值左边序列递归 5-1 quick_sort(alist, start, left-1)
# 界限值右边序列递归 5-2 quick_sort(alist, right+1, end)# 降序排列
# def quick_sort(alist, start, end):
# # 1 准备界限值
# # 1-1递归结束条件 if start >= end: 1-2界限值 mid = alist[start] 1-3左右游标left right
# if start>=end:
# return
# mid=alist[start]
# left=start
# right=end
# while left<right:
# while alist[right]<mid and left<right:
# right-=1
# alist[left]=alist[right]
# while alist[left]>mid and left<right:
# left+=1
# alist[right]=alist[left]
# alist[left]=mid
#
# quick_sort(alist,start,left-1)
# quick_sort(alist,right+1,end)
#
#
# if __name__ == '__main__':
# # alist = [1,2,100,50,1000,0,1,1]
# # alist = [5, 8, 2, 1, 9, 6, 7, 4, 13]
# alist = [5, 8, 2, 1, 9, 6, 7, 4, 3]
# quick_sort(alist, 0, len(alist)-1)
# print(alist)
def quick_sort(alist, start, end):# 1 准备界限值# 1-1递归结束条件 if start >= end: 1-2界限值 mid = alist[start] 1-3左右游标left rightif start >= end:returnmid = alist[start]left = startright = endwhile left < right:# 2 从右边寻找大于界限值的值, 找到后赋值给右边# 2-1 while alist[right] >= mid and : right -= 1 / 2-2 alist[left] = alist[right]while alist[right] >= mid and left < right:right -= 1alist[left] = alist[right]# 3 从左边寻找大于界限值的值, 找到后赋值给右边# 3-1 while alist[left] < mid and : left += 1 /3-2 alist[right] = alist[left]while alist[left] < mid and left < right:left += 1alist[right] = alist[left]alist[left] = mid# 5 递归调用# 界限值左边序列递归 5-1 quick_sort(alist, start, left-1)# 界限值右边序列递归 5-2 quick_sort(alist, right+1, end)quick_sort(alist, start, left-1)quick_sort(alist, right+1, end)if __name__ == '__main__':# alist = [1,2,100,50,1000,0,1,1]# alist = [5, 8, 2, 1, 9, 6, 7, 4, 13]alist = [5, 8, 2, 1, 9, 6, 7, 4, 3]quick_sort(alist, 0, len(alist)-1)print(alist)
