常考排序
- 快速排序
def quickSort(iList):
if len(iList) <= 1:
return iList
mid = len(iList) // 2
left = []
right = []
for i in range(1,len(iList)):
if iList[0] < iList[i]:
right.append(iList[i])
else:
left.append(iList[i])
return quickSort(left) + [iList[0]] + quickSort(right)
n = int(input())
nums = list(map(int,input().split()))
def quick_sort(q, l, r):
if l >= r:
return
mid = (l + r) // 2
x = q[mid]
i = l - 1
j = r + 1
while i < j:
while True:
i += 1
if q[i] >= x:
break
while True:
j -= 1
if q[j] <= x:
break
if i < j:
q[i], q[j] = q[j], q[i]
quick_sort(q, l, j)
quick_sort(q, j + 1, r)
quick_sort(nums,0,n-1)
print(' '.join(list(map(str, nums))))
- 归并排序
def mergeSort(nums):
if len(nums) <=1 :
return nums
mid = len(nums) // 2
left = mergeSort(nums[:mid])
right = mergeSort(nums[mid:])
return merge(left,right)
def merge(left,right):
i,j,temp = 0,0,[]
while i < len(left) and j < len(right):
if left[i] > right[j]:
temp.append(right[j])
j += 1
else:
temp.append(right[i])
i += 1
temp = temp + left[i:]
temp = temp + right[j:]
return temp
- 归并排序求逆序数对
class Solution(object):
def reversePairs(self, nums) -> int:
if not nums:
return 0
self.count = 0
def merge(nums):
if len(nums) == 1:
return nums
mid = len(nums) // 2
left = nums[:mid]
right = nums[mid:]
left = merge(left)
right = merge(right)
return mergeSort(left, right)
def mergeSort(left,right):
temp = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
temp.append(left[i])
i += 1
else:
temp.append(right[j])
self.count += len(left) - i ###!!!!!
j += 1
temp += left[i:]
temp += right[j:]
return temp
merge(nums)
return self.count
- 堆排序
堆排序是指利用堆这种数据结构所设计的一种排序算法。
堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:子结点的键值或索引总是小于(或者大于)它的父节点。
直接使用 from heapq import heapify 实现最小堆。
def heapSort(nums):
n = len(nums)
for i in range(n,-1,-1):
heapify(nums,n,i)
for i in range(n-1,0,-1):
nums[0],nums[i] = nums[i],nums[0]
heapify(nums,n,0)
def heapify(nums,n,i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and nums[i] < nums[l]:
largest = l
if r < n and nums[largest] < nums[r]:
largegst = r
if largest != i:
nums[i], nums[largest] = nums[largest], nums[i]
heapify(nums,n,largest)
参考资料:
https://www.runoob.com/python3/python-heap-sort.html
https://greyireland.gitbook.io/algorithm-pattern/ji-chu-suan-fa-pian/sort
网友评论