一、算法信息
- 直接插入排序 O(n^2),O(1),稳定
- 折半插入排序 O(n^2),O(1),稳定
- 希尔排序 时间复杂度与增量序列有关,O(1)
- 冒泡排序 O(n^2),O(1),稳定
- 快速排序 O(nlogn),O(1),不稳定
- 简单选择排序 O(n^2),O(1),不稳定
- 堆排序(大根堆) O(nlogn),O(1)
- 递归排序 O(nlogn),O(n),稳定
- 基数排序 O(d(n+k)),O(n+k),稳定
- 计数排序 O(n+k),O(n+k),稳定,(k是辅助计数数组的长度)
- 桶排序
二、真题测试
Leetcode 912. 排序数组
三、代码
3.1.直接插入排序
class Solution:def sortArray(self, nums: List[int]) -> List[int]:# 1.直接插入排序 O(n^2),O(1),稳定,超时print("直接插入排序")n = len(nums)for i in range(1, n):if nums[i] < nums[i - 1]:tmp = nums[i]j = i - 1while j >= 0 and nums[j] > tmp:nums[j + 1] = nums[j]j -= 1nums[j + 1] = tmpreturn nums
3.2.折半插入排序
class Solution:def sortArray(self, nums: List[int]) -> List[int]:# 2.折半插入排序 O(n^2),O(1),稳定,超时print("折半插入排序")n = len(nums)for i in range(1, n):if nums[i] < nums[i - 1]:tmp = nums[i]l, r = 0, i - 1# 找到第一个大于nums[i]的位置，左右闭区间，最后的l即为要求的while l <= r:mid = (r - l) // 2 + lif nums[mid] > tmp:r = mid - 1else:l = mid + 1j = i - 1while j >= l:nums[j + 1] = nums[j]j -= 1nums[j + 1] = tmpreturn nums
3.3.希尔排序
class Solution:def sortArray(self, nums: List[int]) -> List[int]:# 3.希尔排序 时间复杂度与增量序列有关,O(1),不稳定print("希尔排序")n = len(nums)d = n // 2while d >= 1:for i in range(d, n):if nums[i] < nums[i - d]:tmp = nums[i]j = i - dwhile j >= 0 and nums[j] > tmp:nums[j + d] = nums[j]j -= dnums[j + d] = tmpd = d // 2return nums
3.4.冒泡排序
class Solution:def sortArray(self, nums: List[int]) -> List[int]:# 4.冒泡排序 O(n^2),O(1),稳定,超时print("冒泡排序")n = len(nums)for i in range(n - 1):flag = Falsefor j in range(n - 1, i, -1):if nums[j] < nums[j - 1]:nums[j], nums[j - 1] = nums[j - 1], nums[j]flag = Trueif not flag:breakreturn nums
3.5.快速排序
class Solution:def sortArray(self, nums: List[int]) -> List[int]:# 5.快速排序 O(nlogn),O(1),不稳定print("快速排序")random.shuffle(nums) # 快速排序分布均匀的元素，对于有序的排序非常不适合def partition(arr:List[int], low:int, high:int):if low < high:pivot = arr[low]while low < high:while low < high and arr[high] >= pivot:high -= 1arr[low] = arr[high]while low < high and arr[low] <= pivot:low += 1arr[high] = arr[low]arr[low] = pivotreturn lowdef quickSort(arr:List[int], low:int, high:int):if low < high:pivotIndex = partition(arr, low, high)quickSort(arr, low, pivotIndex - 1)quickSort(arr, pivotIndex + 1, high)quickSort(nums, 0, len(nums) - 1)return nums
3.6.简单选择排序
class Solution:def sortArray(self, nums: List[int]) -> List[int]:# 6.简单选择排序 O(n^2),O(1),不稳定print("简单选择排序")n = len(nums)for i in range(n - 1):minIndex = ifor j in range(i + 1, n):if nums[j] < nums[minIndex]:minIndex = jif i != minIndex:nums[i], nums[minIndex] = nums[minIndex], nums[i]return nums
3.7.堆排序
# ==> 基于大根堆的优先队列
class PriorityQueue:def __init__(self, arr:List[int]):self.arr = arrself.size = len(arr)# 初始化，将arr转为大根堆self.build()# 基本函数：上滤（以挖坑法的思维进行理解）def up(self, index:int):tmp = self.arr[index] # 记录根结点的值p = (index - 1) // 2 # 父结点while index - 1 >= 0 and self.arr[p] < tmp:self.arr[index] = self.arr[p]index = pp = (index - 1) // 2self.arr[index] = tmp# 基本函数：下滤（以挖坑法的思维进行理解）def down(self, index:int):tmp = self.arr[index] # 记录根结点的值i = 2 * index + 1 # 左子结点while i < self.size:# > 使i指向更大的子结点if i + 1 < self.size and self.arr[i] < self.arr[i + 1]:i += 1if tmp >= self.arr[i]:breakelse:# > 结点向下移动，坑位向上移动self.arr[index] = self.arr[i]index = ii = 2 * index + 1# > 根结点移动到最终的坑位self.arr[index] = tmpdef build(self):for i in range(self.size // 2, -1, -1):self.down(i)# 队尾增加元素def push(self, x:int):if len(self.arr) == self.size:self.arr.append(0)self.arr[self.size] = xself.size += 1self.up(self.size - 1)# 队首弹出元素def pop(self):tmp = self.arr[0]self.arr[0] = self.arr[self.size - 1]self.size -= 1self.down(0)return tmpclass Solution:def sortArray(self, nums: List[int]) -> List[int]:# 7.堆排序(大根堆) O(nlogn),O(1),不稳定print("堆排序")n = len(nums)pq = PriorityQueue(nums)for i in range(n):val = pq.pop()nums[n - i - 1] = valreturn nums
3.8.递归排序
class Solution:def sortArray(self, nums: List[int]) -> List[int]:# 8.递归排序 O(nlogn),O(n),稳定print("递归排序")n = len(nums)arr2 = [0] * ndef merge(arr:List[int], low:int, mid:int, high:int):i, j, k = low, mid + 1, lowfor p in range(low, high + 1):arr2[p] = arr[p]while i <= mid and j <= high:if arr2[i] < arr2[j]:arr[k] = arr2[i]i += 1k += 1else:arr[k] = arr2[j]j += 1k += 1while i <= mid:arr[k] = arr2[i]i += 1k += 1while j <= high:arr[k] = arr2[j]j += 1k += 1def mergeSort(arr:List[int], low:int, high:int):if low < high:mid = (high - low) // 2 + lowmergeSort(arr, low, mid)mergeSort(arr, mid + 1, high)merge(arr, low, mid, high)mergeSort(nums, 0, n - 1)return nums
3.9.基数排序
class Solution:def sortArray(self, nums: List[int]) -> List[int]:# 9.基数排序 O(d(n+k)),O(n+k),稳定[这里是通不过的，因为这个只能用于全正数]n = len(nums)result = [0] * nbase = 1maxVal = max(nums)while maxVal >= base:# 统计该位上的各个数字的频数cnts = [0] * 10for num in nums:a = (num // base) % 10cnts[a] += 1# 计算cnts的前缀和数组，表示当前位上小于等于a的个数（这里可以直接用cnts数组进行原地修改，但是另开一个数组思路更加清晰）preSums = [0]for i in range(10):preSums.append(preSums[i] + cnts[i])# 逆序根据preSums将数放到指定的位置for j in range(n - 1, -1, -1):index = (nums[j] // base) % 10result[preSums[index + 1] - 1] = nums[j]preSums[index + 1] -= 1base *= 10return result
3.10.计数排序
class Solution:def sortArray(self, nums: List[int]) -> List[int]:# 10.计数排序 O(n+k),O(n+k),稳定,(k是辅助计数数组的长度)n = len(nums)nums2 = nums.copy()maxVal = max(nums2)minVal = min(nums2)cnts = [0] * (maxVal - minVal + 1)for num in nums:cnts[num - minVal] += 1# 计算数字频数的前缀和for i in range(1, len(cnts)):cnts[i] += cnts[i - 1]for j in range(n - 1, -1, -1):nums[cnts[nums2[j] - minVal] - 1] = nums2[j]cnts[nums2[j] - minVal] -= 1return nums
3.11.桶排序
class Solution:def sortArray(self, nums: List[int]) -> List[int]:# 11.桶排序print("桶排序")minVal, maxVal = min(nums), max(nums)if minVal == maxVal:return nums# 选择桶的数量bucketCnt = int(sqrt(maxVal - minVal))bucketWidth = (maxVal - minVal) // bucketCnt# 创建桶buckets = [[] for _ in range(bucketCnt)]# 遍历，将数据加入各个桶中for num in nums:bucketIndex = (num - minVal) // bucketWidthbucketIndex = bucketIndex if bucketIndex < bucketCnt else bucketCnt - 1buckets[bucketIndex].append(num)# 桶内排序并输出result = []for i in range(bucketCnt):buckets[i].sort()result += buckets[i]return result