深圳创意设计网站,英文网站建设技术,wordpress客户案例,网站开发合同 中英文排序算法
冒泡排序
一次比较相邻的两个数#xff0c;每轮之后末尾的数字是确定的。
时间复杂度为 O ( n 2 ) O(n^2) O(n2)#xff0c;空间复杂度为 O ( 1 ) O(1) O(1)#xff0c;稳定。
def BUB(nums):for i in range(len(nums)):count 0for j in range(len(nums)-i-1)…排序算法
冒泡排序
一次比较相邻的两个数每轮之后末尾的数字是确定的。
时间复杂度为 O ( n 2 ) O(n^2) O(n2)空间复杂度为 O ( 1 ) O(1) O(1)稳定。
def BUB(nums):for i in range(len(nums)):count 0for j in range(len(nums)-i-1):if nums[j] nums[j1]:nums[j], nums[j1] nums[j1], nums[j]count 1# count是为了记录该轮是否有修改的若没有修改则说明当前数组已经满足条件不需要再进行交换了。if count 0:breakreturn nums选择排序
选择排序是每轮在剩余的元素中找到最小的元素交换位置。
时间复杂度为 O ( n 2 ) O(n^2) O(n2)空间复杂度为 O ( 1 ) O(1) O(1)不稳定。
def selection(nums):for i in range(len(nums)-1):for j in range(i1, len(nums)):if nums[i] nums[j]:nums[i], nums[j] nums[j], nums[i]return nums插入排序
插入排序是默认前面的序列是有序的然后将后面的每个数字依次与前面有序的序列进行比较
时间复杂度为 O ( n 2 ) O(n^2) O(n2)空间复杂度为 O ( 1 ) O(1) O(1)稳定。
def insertSort(nums):for i in range(len(nums)-1):for j in range(i1, 0, -1):if nums[j] nums[j-1]:nums[j], nums[j-1] nums[j-1], nums[j]else:breakreturn nums希尔排序
希尔排序是对插入排序的优化它选择了一个增量(len(nums)//2)然后按照这个增量选取等差数列每轮对每个等差数列进行排序然后将增量缩小重复进行排列直到增量缩小为1。
时间复杂度为 O ( n l o g 2 n ) O(nlog_2^n) O(nlog2n)空间复杂度为 O ( 1 ) O(1) O(1)稳定。
def xier(nums):l len(nums)gap l//2while gap0:for i in range(gap, l):temp nums[i]j i# j-gap就相当于等差数列进行排序比较while j-gap0 and temp nums[j-gap]:nums[j] nums[j-gap]j j-gapnums[j]tempgap-1return nums归并排序
合并两个已经排好序的序列以得到结果。是一个递归的过程。
时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)空间复杂度为 O ( n ) O(n) O(n)稳定。
# 合并两个有序的数组
def merge_two(s1,s2,s):i, j 0, 0while (ij) len(s):# jlen(s2)时说明s2走完了或者s1没走完并且s1中该位置是最小的if jlen(s2) or (ilen(s1) and s1[i] s2[j]):s[ij] s1[i]i 1else:s[ij] s2[j]j 1
def merge(s):l len(s)if l2:returnmid l//2s1 s[0:mid]s2 s[mid:l]merge(s1)merge(s2)merge_two(s1, s2, s)快速排序
快速排序需要一个基准元素以及左右两个指针l,r首先从右端元素开始与基准元素进行比较找到比基准元素小的数字放到左端然后从左端开始寻找比右端大的元素放到r的位置。一轮之后基准元素左端都是比基准元素小的右端都是比基准元素大的。然后再依次遍历基准元素左边和右边的序列。
时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)空间复杂度为 O ( 1 ) O(1) O(1)不稳定。
def quick_sort(nums, start, end):if start end:returnpivot nums[start]l, r start, endwhile lr:while lr and nums[r] pivot:r-1nums[l] nums[r]while lr and nums[l] pivot:l1nums[r] nums[l]nums[l] pivotquick_sort(nums, start, l)quick_sort(nums, l1, end)
