LC打怪录 912.排序数组

本文主要是介绍LC打怪录 912.排序数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.3 插入排序 | 菜鸟教程

def insertionSort(arr):for i in range(len(arr)):preIndex = i-1current = arr[i]while preIndex >= 0 and arr[preIndex] > current:arr[preIndex+1] = arr[preIndex]preIndex-=1arr[preIndex+1] = currentreturn arr

def insertion_sort(nums: list[int]):"""插入排序"""# 外循环：已排序区间为 [0, i-1]for i in range(1, len(nums)):base = nums[i]j = i - 1# 内循环：将 base 插入到已排序区间 [0, i-1] 中的正确位置while j >= 0 and nums[j] > base:nums[j + 1] = nums[j]  # 将 nums[j] 向右移动一位j -= 1nums[j + 1] = base  # 将 base 赋值到正确位置

class Solution:def sortArray(self, nums: List[int]) -> List[int]:if len(nums) <= 1:return nums# 随机取数 避免因为pivot区分度不强造成的算法退化pivot = random.choice(nums)# O(n)划分left  = self.sortArray([x for x in nums if x < pivot])right = self.sortArray([x for x in nums if x > pivot])# 相同值保留 避免因为大量相同元素造成的算法退化mid  = [x for x in nums if x == pivot]return left + mid + right 

思路五：插入排序
类似打扑克牌的时候，每次会把新摸的牌插入到已经排好序的牌里

从第2个元素开始遍历，和前面的数字比较
将比当前数大的元素依次后移，然后把当前数放在最后一个比它大的数字的原位置
对从第2个元素开始每个数都进行以上操作

class Solution:def sortArray(self, nums: List[int]) -> List[int]:n = len(nums)for i in range(1, n):tmp = nums[i]j = iwhile j > 0 and nums[j - 1] > tmp:nums[j] = nums[j - 1]j -= 1nums[j] = tmpreturn nums

这篇关于LC打怪录 912.排序数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---