【leetcode系列】【算法】【中等】排序数组

科技前沿 • 2025-03-23 16:30 • 阅读 44

大家好，我是讯享网，很高兴认识大家。

题目：

讯享网

题目链接： https://leetcode-cn.com/problems/sort-an-array/

解题思路：

B站搬运油管上的视频，可视化展示15中排序算法，其中最后一种算法就是下面说的猴子排序：

https://www.bilibili.com/video/BV1Ws411f7aJ?from=search&seid=

1. 猴子排序

随机打乱数组顺序

如果打乱后符合排序要求，则停止

如果打乱后不符合排序要求，则继续排序

时间复杂度：平均O(N * N!)，最好O(N)，最差O(∞)即永远排不好

2. 睡眠排序

根据nums数组中的元素个数n，创建n个线程，每个线程sleep分派到的数字的秒数

醒来之后报数，根据报数排序

3. 指鹿为马排序

聚集N个人，依次对每个人展示当前数组，询问他当前数组是否是有序的

如果认为是无序的，则干掉

重复几次，直到所有人认为数组是有序的，则停止

最差时间复杂度为O(N)，N为人数，与数字个数无关

代码实现：

#快排 class Solution: def sortArray(self, nums: List[int]) -> List[int]: def qsort(nums, left, right): mid = random.randint(left, right) nums[right], nums[mid] = nums[mid], nums[right] i = left - 1 for left in range(left, right): if nums[left] >= nums[right]: continue i += 1 nums[i], nums[left] = nums[left], nums[i] i += 1 nums[i], nums[right] = nums[right], nums[i] return i def qsort_help(nums, left, right): if left >= right: return mid = qsort(nums, left, right) sort_help(nums, left, mid - 1) sort_help(nums, mid + 1, right) def bubble(nums): cycle_num, index, flag = 0, 0, True while flag: flag = False for index in range(1, len(nums) - cycle_num): if nums[index] < nums[index - 1]: flag = True nums[index], nums[index - 1] = nums[index - 1], nums[index] cycle_num += 1 def select(nums): for i in range(0, len(nums)): min_index = i for j in range(i + 1, len(nums)): if nums[j] < nums[min_index]: min_index = j if min_index != i: nums[i], nums[min_index] = nums[min_index], nums[i] def shell(nums): n = len(nums) gap = n // 2 while gap > 0: for i in range(gap, n): while i >= gap and nums[i] < nums[i - gap]: nums[i], nums[i - gap] = nums[i - gap], nums[i] i -= gap gap //= 2 def merge_sort(nums): if len(nums) <= 1: return nums mid = int(len(nums) / 2) left = merge_sort(nums[:mid]) right = merge_sort(nums[mid:]) return merge(left, right) def merge(left,right): r, l=0, 0 result=[] while l < len(left) and r < len(right): if left[l] <= right[r]: result.append(left[l]) l += 1 else: result.append(right[r]) r += 1 result += list(left[l:]) result += list(right[r:]) return result def max_heapify(heap, root, heap_len): p = root while p * 2 + 1 < heap_len: l, r = p * 2 + 1, p * 2 + 2 if heap_len <= r or heap[r] < heap[l]: nex = l else: nex = r if heap[p] < heap[nex]: heap[p], heap[nex] = heap[nex], heap[p] p = nex else: break def build_heap(heap): for i in range(len(heap) - 1, -1, -1): max_heapify(heap, i, len(heap)) def heap_sort(nums): build_heap(nums) for i in range(len(nums) - 1, -1, -1): nums[i], nums[0] = nums[0], nums[i] max_heapify(nums, 0, i) #快排 #qsort_help(nums, 0, len(nums) - 1) #冒泡 #bubble(nums) #选择 #select(nums) #希尔 #shell(nums) #归并 #nums = merge_sort(nums) #堆排序 #heap_sort(nums) return nums

讯享网

【leetcode系列】【算法】【中等】排序数组

题目：

解题思路：

代码实现：

相关推荐