引流软件下载站,wordpress主题下载,天津网站建设揭秘,cent os安装wordpress文章目录 一#xff0c;排序算法时间复杂度比较二#xff0c;插入排序三#xff0c;冒泡排序四#xff0c;快速排序五#xff0c;堆排序六#xff0c;二分归并排序 一#xff0c;排序算法时间复杂度比较
算法最坏情况下平均情况下插入排序O(n )O(n)冒泡排序O(n)O(n)快速… 文章目录 一排序算法时间复杂度比较二插入排序三冒泡排序四快速排序五堆排序六二分归并排序 一排序算法时间复杂度比较
算法最坏情况下平均情况下插入排序O(n² )O(n²)冒泡排序O(n²)O(n²)快速排序O(n²)O(nlogn)堆排序O(nlogn)O(nlogn)二分归并排序O(nlogn)O(nlogn)
二插入排序
假设原始序列为[5,7,1,3,6,2,4] 首先假设第一个元素5已经排好然后插入第二个元素7但是7比5大所以7放在5的右边接着是第三个元素11比7小所以再7左边并且1比5小所以放在5的左边。第四个元素3于7比较比7小在7左边并且比5小所以在5左边但是3比1小所以插入到1和5之间其他的类似。。。。
原始序列5713624插入零次5713624插入一次5713624插入二次1573624插入三次1357624插入四次1356724插入五次1235674插入六次1234567
a [5,7,1,3,6,2,4]
n len(a)
for i in range(1, n):key a[i] # 当前待插入元素j i - 1 # 已排序部分的最后一个元素的索引while j 0 and a[j] key:a[j 1] a[j] # 向后移动元素j - 1a[j 1] key # 插入元素到正确位置
print(a)
#[1, 2, 3, 4, 5, 6, 7]三冒泡排序
假设原始序列为[5,7,1,3,6,2,4] 首先5和7比较5比7小不交换顺序7和1比较7比1大交换顺序7和3比较7比3大交换顺序7和6比较7比6大交换顺序7和4比较7比4大交换顺序。以此类推
原始序列5713624冒泡一次5136247冒泡二次1352467冒泡三次1324567冒泡四次1234567
a [5,7,1,3,6,2,4]
n len(a)
for i in range(n):for j in range(0, n-i-1):if a[j] a[j1]:a[j], a[j1] a[j1], a[j]
print(a)
#[1, 2, 3, 4, 5, 6, 7]四快速排序
假设原始序列为[5,7,1,3,6,2,4] 首先以第一个元素5为划分的标准从前面找第一个比5大的从后面找第一个比5小的交换位置然后再找下一个比大的和比5小的交换位置。第二次交换是发生在两个相邻的元素之间做的所以说2前面的都比5小6后面的都比5大所以2的位置是第一个元素5的位置然后交换2和5的位置这样5的位置就定下来了再分别对两边递归调用同样的方法。
原始序列5713624交换一次5413627交换二次5413267划分2413567递归运行2413567
a [5,7,1,3,6,2,4]
def fast_sort(a):if len(a) 1:return abasis a[0]left_num [i for i in a[1::] if i basis]middle [i for i in a if i basis]right_num [i for i in a[1::] if i basis]return fast_sort(left_num) middle fast_sort(right_num)
print(fast_sort(a))
#[1, 2, 3, 4, 5, 6, 7]五堆排序
pass
六二分归并排序
它将待排序的列表递归地分成两个子列表直到每个子列表只包含一个元素。然后将这些子列表按照顺序合并形成一个有序的列表。 假设原始序列为[5,7,1,3,6,2,4] 首先先把序列一份为二 (标注和没标注的)然后对每个子列里面也分别进行二分归并排序然后把已经排好的子数合并两个序列的首元素比较哪个小就把哪个拿走知道一个数组空了就把另一个数组全部接在后面。
原始序列5713624归分5413627递归排序1345267开始组合1345267原345267新数组1原34567新数组12原4567新数组123原567新数组1234原67新数组12345原新数组1234567
a [5, 7, 1, 3, 6, 2, 4]def merge_sort(arr):if len(arr) 1:return arrmid len(arr) // 2left arr[:mid]right arr[mid:]left merge_sort(left)right merge_sort(right)return merge(left, right)def merge(left, right):merged []i j 0while i len(left) and j len(right):if left[i] right[j]:merged.append(left[i])i 1else:merged.append(right[j])j 1while i len(left):merged.append(left[i])i 1while j len(right):merged.append(right[j])j 1return mergedprint(merge_sort(a))
