算法入门 | 排序算法-冒泡排序、选择排序、快速排序、两道力扣Easy排序题
最近在b站上看Python数据结构与算法的课程，梳理一下常见的排序算法。
冒泡排序：通过两两对比的方式将无序区的最大值不断填充到有序区。可以通过判断是否发生两两交换来优化程序，提前终止。
时间复杂度：O(N2)
def bubble_sort(li):for i in range(len(li)-1):REPLACE = Falsefor j in range(len(li)-1-i):if li[j] > li[j+1]:li[j], li[j+1] = li[j+1], li[j]REPLACE = Trueif not REPLACE: break # 当没发生交换的时候直接终止循环print(li)li = [3,1,9,8,4,6,2,7,5]print('begin')print(li)bubble_sort(li)print('end')print(li)
打印结果：
begin
[3, 1, 9, 8, 4, 6, 2, 7, 5]
[1, 3, 8, 4, 6, 2, 7, 5, 9]
[1, 3, 4, 6, 2, 7, 5, 8, 9]
[1, 3, 4, 2, 6, 5, 7, 8, 9]
[1, 3, 2, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
end
[1, 2, 3, 4, 5, 6, 7, 8, 9]
选择排序：从无序区内每次选择一个最小值，填充到有序区内。
时间复杂度：O(N2)
def select_sort(li):for i in range(len(li)-1):min_loc = ifor j in range(i, len(li)):if li[min_loc] > li[j]:min_loc = jli[min_loc], li[i] = li[i], li[min_loc]print(li)li = [3,1,9,8,4,6,2,7,5]print('begin')print(li)select_sort(li)print('end')print(li)
打印结果：
begin
[3, 1, 9, 8, 4, 6, 2, 7, 5]
[1, 3, 9, 8, 4, 6, 2, 7, 5]
[1, 2, 9, 8, 4, 6, 3, 7, 5]
[1, 2, 3, 8, 4, 6, 9, 7, 5]
[1, 2, 3, 4, 8, 6, 9, 7, 5]
[1, 2, 3, 4, 5, 6, 9, 7, 8]
[1, 2, 3, 4, 5, 6, 9, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 9, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
end
[1, 2, 3, 4, 5, 6, 7, 8, 9]
插入排序：类似于打扑克牌的时候，每抽到一张牌就把这张牌按顺序插入到有序区内，但我认为这种排序方法比较繁琐且不具有优势，就不记具体代码了。
快速排序：快速排序是最常见、必须牢记的方法。核心思路为哨兵划分和递归。每次选择一个基准数，划分为左边是小于基准数，右边是大于基准数，然后不断递归。
时间复杂度：O(NlogN)，最差情况为O(N2)
# 该写法为选定最左边的为基准数def partition(li, l, r):i, j = l, rwhile i<j:while i<j and li[j] >= li[l]: j -= 1while i<j and li[i] <= li[l]: i += 1li[i], li[j] = li[j], li[i]li[i], li[l] = li[l], li[i]return idef quick_sort(li, l, r):if l >= r: returnmid = partition(li, l, r)quick_sort(li, l, mid-1)quick_sort(li, mid+1, r)li = [3,1,9,8,4,6,2,7,5]print('begin')print(li)quick_sort(li, 0, len(li)-1)print('end')print(li)
快速排序的常见优化方式有Tail Call和随机基准数两种。
随机基准数：由于普通快速排序每轮选取「子数组最左元素」作为「基准数」，在输入数组 完全有序 或 完全倒序 时， partition() 每轮只划分一个元素，时间复杂度退化到O(N2)。可采用随机基准数来极大程度上避免出现最差情况，当然最差复杂度还是O(N2)，因为是可能每次选择的基准数都是最左元素，但这种情况已经概率非常小了。
仅需改写partition函数
import randomdef partition(li, l, r):# 选取随机基准索引，并且将ra放到最左边ra = random.randrange(l, r+1)li[ra], li[l] = li[l], li[ra]# 下面与之前相同i, j = l, rwhile i<j:while i<j and li[j] >= li[l]: j -= 1while i<j and li[i] <= li[l]: i += 1li[i], li[j] = li[j], li[i]li[i], li[l] = li[l], li[i]return i
Tail Call：当数组完全倒序的时候，partition() 的递归深度会达到 N ，即 最差空间复杂度 为 O(N)。
每轮递归时，仅对 较短的子数组 执行哨兵划分 partition() ，就可将最差的递归深度控制在 O(logN) （每轮递归的子数组长度都 ≤ 当前数组长度 / 2），即实现最差空间复杂度 O(logN) 。
仅需改写quick_sort函数
def quick_sort(li, l, r):while l < r:mid = partition(li, l, r)if mid-l <= r-mid:quick_sort(li, l, mid-1)l = mid + 1else:quick_sort(li, mid+1, r)r = mid - 1
剑指 Offer 45. 把数组排成最小的数
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: "102"
示例 2:
输入: [3,30,34,5,9]
输出: "3033459"
提示:
0 < nums.length <= 100
说明:
输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
思路：重点是两个数的组合怎么样才是最大的？比较两个数的字符串相加，若A+B>B+A，则A>B(即A放在B前面会使得组合更大）。
有了这个思路之后，用快排即可
class Solution:def minNumber(self, nums: List[int]) -> str:def quick_sort(nums, l, r):if l >= r: returnra = random.randrange(l, r+1)nums[ra], nums[l] = nums[l], nums[ra]i, j = l, rwhile i<j:while i<j and nums[j]+nums[l]>=nums[l]+nums[j]: j -= 1while i<j and nums[i]+nums[l]<=nums[l]+nums[i]: i += 1nums[i], nums[j] = nums[j], nums[i]nums[i], nums[l] = nums[l], nums[i]quick_sort(nums, l, i-1)quick_sort(nums, i+1, r)nums = [str(num) for num in nums]quick_sort(nums, 0, len(nums)-1)return ''.join(nums)
剑指 Offer 61. 扑克牌中的顺子
从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
示例 1:
输入: [1,2,3,4,5]
输出: True
示例 2:
输入: [0,0,1,2,5]
输出: True
限制：
数组长度为 5
数组的数取值为 [0, 13] .
思路：两种方法，核心思路是根据最大值与最小值的差是否小于5来确定是否是顺子。
①遍历数组，用set存储所有值，如果有重复，则直接返回False。判断最大值与最小值的差是否小于5。
②排序+遍历。首先排序，然后遍历判断是否有nums[i]==nums[i+1]（需排除0的情况），最后判断最大值与最小值的差是否小于5。
这里给出第二种方法的实现
class Solution:def isStraight(self, nums: List[int]) -> bool:nums.sort()joker = 0for i in range(4):if nums[i] == 0: joker += 1elif nums[i] == nums[i+1]: return Falsereturn nums[4] - nums[joker] < 5