排序算法
1、冒泡排序
时间复杂度O(N^2)
def bubblesort(nums):
if len(nums) < 2: #数组长度小于2没必要排序
return nums
for i in range(len(nums)): #外层遍历，遍历整个数据长度，循环一次确定一个最大的数字
for j in range(1, len(nums) - i): #内层遍历，遍历数组1到数组长度减外层遍历个数
if nums[j] < nums[j - 1]: #后面数字比前面小交换位置
temp = nums[j]
nums[j] = nums[j - 1]
nums[j - 1] = temp
return nums
2、选择排序
时间复杂度O(N^2)
def selectionsort(nums):
if len(nums) < 2: # 数组长度小于2没必要排序
return nums
for i in range(len(nums)):
minnum = i
for j in range(i + 1, len(nums)): # 从剩下的数组长度减i个数中选择最小的与i位置的数交换
minnum = j if nums[j] < nums[minnum] else minnum
temp = nums[minnum]
nums[minnum] = nums[i]
nums[i] = temp
return nums
3、插入排序
时间复杂度O(N^2)，跟数据情况有关系，最好O(N)
def insertionsort(nums):
if len(nums) < 2: # 数组长度小于2没必要排序
return nums
for i in range(1, len(nums)):
for j in range(i - 1, -1, -1): # i与i位置之前的有序数组比较，i小于之前的插入
if nums[i] < nums[j]:
temp = nums[j]
nums[j] = nums[i]
nums[i] = temp
i -= 1
else:
break
print(nums)
return nums
4、归并排序
时间复杂度O(N*logN)
def mergesort(nums):
if len(nums) < 2: # 数组长度小于2没必要排序
return nums
sortprocess(nums, 0, len(nums) - 1) #归并排序输入左右端点
return nums
def sortprocess(nums, L, R):
if L == R:
return
mid = L + (R - L) // 2 #左右端点一分为二，分别进行子过程排序
print('mid', mid)
sortprocess(nums, L, mid)
sortprocess(nums, mid + 1, R)
merge(nums, L, R, mid)
def merge(nums, L, R, mid): #对分成的两个有序数组进行融合
print(L, R, mid)
help = [0] * (R - L + 1)
i = 0
left = L
right = mid + 1
while left <= mid and right <= R:
if nums[left] < nums[right]:
help[i] = nums[left]
left += 1
else:
help[i] = nums[right]
right += 1
i += 1
while left <= mid:
help[i] = nums[left]
left += 1
i += 1
while right <= R:
help[i] = nums[right]
right += 1
i += 1
for i in range(i):
nums[i + L] = help[i]
归并排序应用：逆序对问题
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
def reversepairs(nums):
if len(nums) < 2: # 数组长度小于2没必要排序
return 0
return sortprocess(nums, 0, len(nums) - 1) # 返回总的逆序对
def sortprocess(nums, L, R):
if L == R:
return 0
mid = L + (R - L) // 2 # 左右端点一分为二，分别进行子过程排序
print('mid', mid)
return sortprocess(nums, L, mid) + sortprocess(nums, mid + 1, R) + merge(nums, L, R, mid)
def merge(nums, L, R, mid): # 对分成的两个有序数组进行融合
print(L, R, mid)
help = [0] * (R - L + 1)
i = 0
left = L
right = mid + 1
res = 0
while left <= mid and right <= R:
if nums[left] > nums[right]:
help[i] = nums[left]
left += 1
res += R - right + 1 #记录这一轮中，左侧数比右侧大的数目
else:
help[i] = nums[right]
right += 1
i += 1
while left <= mid:
help[i] = nums[left]
left += 1
i += 1
while right <= R:
help[i] = nums[right]
right += 1
i += 1
for i in range(i):
nums[i + L] = help[i]
return res
5、快速排序
时间复杂度O(NlogN)
def quicksort(nums):
if len(nums) < 2: # 数组长度小于2没必要排序
return nums
quick(nums, 0, len(nums) - 1)
return nums
def quick(nums, l, r):
if l < r:
less, more = partition(nums, l, r)
quick(nums, l, less - 1)
quick(nums, more + 1, r)
def partition(nums, l, r):
aim = nums[l]
less = l
more = r
cur = l
while cur <= more:
if nums[cur] < aim:
temp = nums[cur]
nums[cur] = nums[less]
nums[less] = temp
cur += 1
less += 1
elif nums[cur] > aim:
temp = nums[cur]
nums[cur] = nums[more]
nums[more] = temp
more -= 1
else:
cur += 1
return less, more
6、堆排序
时间复杂度O(NlogN)
def heapsort(nums):
if len(nums) < 2: # 数组长度小于2没必要排序
return nums
for i in range(len(nums)):
heapinsert(nums, i)
heapsize = len(nums)
while heapsize > 0:
temp = nums[0]
nums[0] = nums[heapsize - 1]
nums[heapsize - 1] = temp
heapsize -= 1
heapify(nums, 0, heapsize)
return nums
def heapinsert(nums, index):
while index > 0 and nums[index] > nums[(index - 1) // 2]:
temp = nums[index]
nums[index] = nums[(index - 1) // 2]
nums[(index - 1) // 2] = temp
index = (index - 1) // 2
def heapify(nums, index, heapsize):
left = 2 * index + 1
while left < heapsize:
large = left + 1 if left + 1 < heapsize and nums[left + 1] > nums[left] else left
large = large if nums[large] > nums[index] else index
if large == index:
break
temp = nums[index]
nums[index] = nums[large]
nums[large] = temp
index = large
left = 2 * index + 1
