排序算法的python实现（以及相关题目）(待更新)

您所在的位置：网站首页 › 排序算法选择规则怎么写 › 排序算法的python实现（以及相关题目）(待更新)

排序算法的python实现（以及相关题目）(待更新)

2024-06-08 23:22| 来源: 网络整理| 查看: 265

排序算法 1. 九种排序算法实现1 冒泡排序（Bubble Sort）2 选择排序（Selection Sort）3. 插入排序（Insertion Sort）4. 希尔排序（Shell Sort）5. 归并排序（Merge Sort）6. 快速排序（Quick Sort）7. 堆排序(Heap Sort)8. 计数排序(Counting Sort)9. 桶排序（Bucket Sort）9. 基数排序(Radix Sort) 2. 相关题目:剑指offer45.把数组排成最小的数.283.移动零.912.排序数组.506.相对名次75.颜色分类215.数组中的第K大元素1122.数组的相对排序908.最小差值

1. 九种排序算法实现

相关原理请点击此链接.

1 冒泡排序（Bubble Sort）注意事项：冒泡排序的平均时间复杂度为O(n**2)对于一般情况，这种方法是排序时间效率最低的一种方法是一种稳定排序法（元素交换是在相邻元素间进行，不会改变值相同元素的相对位置）代码实现 def bubbleSort(arr): for i in range(len(arr)): for j in range(len(arr) - i - 1): if arr[j] > arr[j + 1]: arr[i], arr[j + 1] = arr[j + 1], arr[j] return arr 2 选择排序（Selection Sort）

注意事项：

选择排序的时间复杂度为O(n**2)是一种不稳定排序（由于交换方式的不同可能会改变值相同元素的相对位置）

代码实现

def selectionSort(arr): for i in range(len(arr) - 1): # 记录一下最小数的索引 min_i = i for j in range(i+1, len(arr)): if arr[j] 0 and arr[j - 1] > temp: arr[j] = arr[j - 1] j -= 1 arr[j] = temp return arr 4. 希尔排序（Shell Sort）

注意:

按照若干间隔进行取值划分子序列，对每个子序列进行插入排序。逐渐缩小间隔的大小从而完成排序排序的总趟数为logn时间复杂度在O(nlogn)和O(n**2)之间是一种不稳定排序法

代码实现：

def shellSort(arr): size = len(arr) gap = size//2 while gap > 0: for i in range(gap, size): temp = arr[i] j = i while j >= gap and arr[j - gap] > temp: arr[j] = arr[j - gap] j-= gap arr[j] = temp gap = gap // 2 return arr 5. 归并排序（Merge Sort）注意：采用递归将序列分成两半，然后两两排序合并，最终合并为结果时间复杂度为O(nlogn)是一种稳定排序算法代码实现： def merge(left_arr, right_arr): arr = [] while left_arr and right_arr: if left_arr[0] b，这就是一个大小比较的策略，之后就按照一般的排序算法对其排序，最后拼接字符串即可

冒泡排序 class Solution: def minNumber(self, nums: List[int]) -> str: n = len(nums) for i in range(n): nums[i] = str(nums[i]) for i in range(n): for j in range(n - i - 1): if nums[j] + nums[j + 1] > nums[j + 1] + nums[j]: nums[j], nums[j + 1] = nums[j + 1], nums[j] return ''.join(nums) 1. 时间复杂度：O(n**2) 2. 空间复杂度：选择排序 class Solution: def minNumber(self, nums: List[int]) -> str: n = len(nums) for i in range(n): nums[i] = str(nums[i]) for i in range(n - 1): min_i = i for j in range(i + 1, n): if nums[min_i] + nums[j] > nums[j] + nums[min_i]: min_i = j if i != min_i: nums[min_i], nums[i] = nums[i], nums[min_i] return ''.join(nums) 插入排序 283.移动零.

思路：原本考虑的是排序算法，可是想到稳定排序算法只是不改变值相同元素间的相对位置，不符合题意。最后想到利用双指针算法来进行求解当右指针碰到非零元素时，交换左右指针对应元素，使得左指针和右指针之间的元素为0且不改变元素的相对位置

class Solution: def moveZeroes(self, nums: List[int]) -> None: left = 0 right = 0 n = len(nums) while right List[str]: ls = [] ls[:] = score n = len(score) ls.sort(reverse = True) for i in range(n): if ls.index(score[i]) == 0: score[i] = 'Gold Medal' elif ls.index(score[i]) == 1: score[i] = 'Silver Medal' elif ls.index(score[i]) == 2: score[i] = 'Bronze Medal' else: score[i] = str(ls.index(score[i])+1) return score 尝试使用归并排序 def merge(left_arr, right_arr): arr = [] while left_arr and right_arr: if left_arr[0] >= right_arr[0]: arr.append(left_arr.pop(0)) else: arr.append(right_arr.pop(0)) while left_arr: arr.append(left_arr.pop(0)) while right_arr: arr.append(right_arr.pop(0)) return arr def mergeSort(arr): size = len(arr) if size List[str]: ls = [] ls[:] = score n = len(score) ls = mergeSort(ls) for i in range(n): if ls.index(score[i]) == 0: score[i] = 'Gold Medal' elif ls.index(score[i]) == 1: score[i] = 'Silver Medal' elif ls.index(score[i]) == 2: score[i] = 'Bronze Medal' else: score[i] = str(ls.index(score[i])+1) return score 尝试使用希尔排序 def shellSort(arr): size = len(arr) gap = size // 2 while gap > 0 : for i in range(gap, size): temp = arr[i] j = i while j >= gap and arr[j - gap] List[str]: ls = [] ls[:] = score n = len(score) ls = shellSort(ls) for i in range(n): if ls.index(score[i]) == 0: score[i] = 'Gold Medal' elif ls.index(score[i]) == 1: score[i] = 'Silver Medal' elif ls.index(score[i]) == 2: score[i] = 'Bronze Medal' else: score[i] = str(ls.index(score[i])+1) return score 75.颜色分类思路：本质上就是一个排序算法，将数组中的元素按照升序的方式排列。具体代码：直接使用sort验证思路（思路正确,就不写代码了，这是一种作弊哈哈）堆排序（时间复杂度为O(1)）： def heapify(arr, index, end): left = 2 * index + 1 right = left + 1 max_index = index while left arr[max_index]: max_index = left if right arr[max_index]: max_index = right if max_index == index: break arr[index], arr[max_index] = arr[max_index], arr[index] index = max_index left = 2 * index + 1 right = left + 1 def buildMaxHeap(arr): size = len(arr) for i in range((size - 2) // 2, -1, -1): heapify(arr, i, size - 1) return arr class Solution: def sortColors(self, nums: List[int]) -> None: buildMaxHeap(nums) size = len(nums) for i in range(size): nums[0], nums[size - i - 1] = nums[size - i - 1], nums[0] heapify(nums, 0, size - i - 2) 对0，1，2计数，并重写数组（荷兰国旗问题） class Solution: def sortColors(self, nums: List[int]) -> None: ls = [0, 0, 0] for i in nums: ls[i] += 1 mid = [] for i in range(3): if ls[i] != 0: for j in range(ls[i]): mid.append(i) nums[:] = mid 单指针 class Solution: def sortColors(self, nums: List[int]) -> None: ptr = 0 n = len(nums) for i in range(n): if nums[i] == 0: nums[ptr], nums[i] = nums[i], nums[ptr] ptr += 1 for i in range(n): if nums[i] == 1: nums[ptr], nums[i] = nums[i], nums[ptr] ptr += 1 215.数组中的第K大元素思路：将数组进行排序，输出第k个（或者倒数第k个元素即可）代码实现：最大堆 def heapify(arr, index, end): left = 2 * index + 1 right = left + 1 while left arr[max_index]: max_index = left if right arr[max_index]: max_index = right if max_index == index: break arr[index], arr[max_index] = arr[max_index], arr[index] index = max_index left = 2 * index + 1 right = left + 1 def buildMaxHeap(arr): size = len(arr) for i in range((size - 2) // 2, -1, -1): heapify(arr, i, size - 1) return arr class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: buildMaxHeap(nums) size = len(nums) for i in range(size): nums[0], nums[size - i - 1] = nums[size - i - 1], nums[0] heapify(nums, 0, size - i - 2) return nums[-k] 最大堆的改进算法：我们只需要找出第k次选择删除的最大值即为最终答案，不需要我们对其进行完整的排序,所以，我们可以在中途直接跳出循环 def heapify(arr, index, end): left = 2 * index + 1 right = left + 1 while left arr[max_index]: max_index = left if right arr[max_index]: max_index = right if max_index == index: break arr[index], arr[max_index] = arr[max_index], arr[index] index = max_index left = 2 * index + 1 right = left + 1 def buildMaxHeap(arr): size = len(arr) for i in range((size - 2) // 2, -1, -1): heapify(arr, i, size - 1) return arr class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: buildMaxHeap(nums) size = len(nums) count = 0 for i in range(size): nums[0], nums[size - i - 1] = nums[size - i - 1], nums[0] count += 1 if count == k: return nums[size - i - 1] heapify(nums, 0, size - i - 2) 1122.数组的相对排序思路：由于给定了数组中的值在0和1000之间，所以可以尝试一下使用计数排序的方法来解决该问题代码实现：计数排序： class Solution: def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]: arr = [0 for i in range(1001)] for i in range(len(arr1)): arr[arr1[i]] += 1 ans = [] for i in range(len(arr2)): while arr[arr2[i]] > 0: ans.append(arr2[i]) arr[arr2[i]] -= 1 for i in range(1001): while arr[i] > 0: ans.append(i) arr[i] -= 1 return ans 908.最小差值思路：直接找打原数组的最大值和最小值，做差与2 * k比较，如果大于2k，返回与2k的差值，如果小于2*k，返回0代码实现： class Solution: def smallestRangeI(self, nums: List[int], k: int) -> int: num_min = min(nums) num_max = max(nums) ans = num_max - num_min if ans > 2 * k: return ans - 2 * k else: return 0

【本文地址】

排序算法的python实现（以及相关题目）(待更新)

排序算法的python实现（以及相关题目）(待更新)

今日新闻

推荐新闻