目录
写在前面:
参考文章: 本文的逻辑顺序基于从第一篇参考博文上借鉴过来的图,并且都是按照升序排序写的程序,程序语言采用python。
冒泡排序
思路:
冒泡排序的基本思想就是让小的数逐渐‘浮上来’。也就是说:
第一次冒泡:将最小的数调换到最前面;
第二次冒泡:将第二小的数调换到最小的数的后面,也就是数组中的第二位;
第三次冒泡,将第三小的数调换到数组中的第三位;
... ...
代码如下:
def bubble_sort(nums): # 让小的数一步一步‘浮’上来 n = len(nums) for i in range(n-1): for j in range(i+1,n): if nums[i]>nums[j]: nums[i],nums[j] = nums[j],nums[i] return nums
时间复杂度: O(n^2),实际上是n-1 + n-2 + n-3 + ...,所以是平方的量级。
空间复杂度: O(l),没有借助额外空间。
快速排序
思路
快速排序的基本思路就是在一遍快排中,以基准值为基础,将比基准值小的数放到基准值的左边,比基准值大的数放在基准值的右边。然后在递归的快排基准值的左边和右边。至于基准值的取法,理论上来讲是无所谓的。
先来一个比较简单直接的吧。它的思路就是遍历一遍数组,用两个空的数组来存储比基准值大和比基准值小的数,代码如下:
def quick_sort1(nums): n = len(nums) if n ==1 or len(nums)==0: return nums left = [] right = [] for i in range(1,n): if nums[i] <= nums[0]: left.append(nums[i]) else: right.append(nums[i]) return quick_sort1(left)+[nums[0]]+quick_sort1(right)
上面的使用了额外的空间,空间复杂度比较高,下面是基于双指针的想法的代码,比较常见:
def quick_sort2(nums,left,right): l,r = left,right-1 while l < r: if nums[r] < nums[l]: nums[r], nums[l] = nums[l], nums[r] l += 1 while l < r: if nums[l] > nums[r]: nums[r],nums[l] = nums[l], nums[r] r -= 1 break else: l += 1 else: r -= 1 if l-left > 1: quick_sort2(nums, left, l) if right - r > 1: quick_sort2(nums, l+1, right) return nums