def bubbleSort(arr):
for i in range(1, len(arr)):
for j in range(0, len(arr) - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
def selectionSort(arr):
for i in range(len(arr) - 1):
# 记录最小数索引
minIndex = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[minIndex]:
minIndex = j
# i 不是最小数时，将i和最小数交换
if i != minIndex:
arr[i], arr[minIndex] = arr[minIndex], arr[i]
return arr
def insertionSort(arr):
for i in range(len(arr)):
preIndex = i - 1
current = arr[i]
while preIndex >= 0 and arr[preIndex] > current:
arr[preIndex + 1] = arr[preIndex]
preIndex -= 1
arr[preIndex + 1] = current
return arr
def shellSort(arr):
gap = 1
while gap < len(arr) // 3:
gap = gap * 3 + 1
while gap > 0:
for i in range(gap, len(arr)):
temp = arr[i]
j = i - gap
while j >= 0 and arr[j] > temp:
arr[j + gap] = arr[j]
j -= gap
arr[j + gap] = temp
gap = gap // 3
return arr
def mergeSort(arr):
if len(arr) < 2:
return arr
middle = len(arr) // 2
# 注意:写法虽简单，但传递整个数组，在数组很大时，空间消耗
left, right = arr[:middle], arr[middle:]
return merge(mergeSort(left), mergeSort(right))
def merge(left, right):
res = []
while left and right:
if left[0] <= right[0]:
res.append(left.pop(0))
else:
res.append(right.pop(0))
while left:
res.append(left.pop(0))
while right:
res.append(right.pop(0))
return res
def MergeSort(lst):
def merge(arr, left, mid, right):
temp = []
i = left
j = mid + 1
while i <= mid and j <= right:
if arr[i] <= arr[j]:
temp.append(arr[j])
i += 1
else:
temp.append((arr[j]))
j += 1
while i <= mid:
temp.append(arr[i])
i += 1
while j <= right:
temp.append(arr[j])
j += 1
for i in range(left, right + 1):
arr[i] = temp[i - left]
def mSort(arr, left, right):
if left >= right:
return
mid = (left + right) // 2
mSort(arr, left, mid)
mSort(arr, mid + 1, right)
merge(arr, left, mid, right)
n = len(lst)
if n <= 1:
return lst
mSort(lst, 0, n - 1)
return lst
def quickSort(arr, left=None, right=None):
left = 0 if not isinstance(left, (int, float)) else left
right = len(arr) - 1 if not isinstance(right, (int, float)) else right
if left < right:
partitionIndex = partition(arr, left, right)
quickSort(arr, left, partitionIndex - 1)
quickSort(arr, partitionIndex + 1, right)
return arr
def partition(arr, left, right):
pivot = left
index = pivot + 1
i = index
while i <= right:
if arr[i] < arr[pivot]:
swap(arr, i, index)
index += 1
i += 1
swap(arr, pivot, index - 1)
return index
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def heapSort(arr):
global arrLen
arrLen = len(arr)
buildMaxHeap(arr)
for i in range(len(arr) - 1, 0, -1):
swap(arr, 0, i)
arrLen -= i
heapify(arr, 0)
return arr
def buildMaxHeap(arr):
for i in range(len(arr) // 2, -1, -1):
heapify(arr, i)
def heapify(arr, i):
left = 2 * i + 1
right = 2 * i + 2
largest = i
if left < arrLen and arr[left] > arr[largest]:
largest = left
if right < arrLen and arr[right] > arr[largest]:
largest = right
if largest != i:
swap(arr, i, largest)
heapify(arr, largest)
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def countingSort(arr, maxValue):
bucketLen = maxValue + 1
bucket = [0] * bucketLen
sortedIndex = 0
arrLen = len(arr)
for i in range(arrLen):
if not bucket[arr[i]]:
bucket[arr[i]] = 0
bucket[arr[i]] += 1
for j in range(bucketLen):
while bucket[j] > 0:
arr[sortedIndex] = j
sortedIndex += 1
bucket[j] -= 1
return arr
def bucket_sort(arr, n):
'''
1.创建n个空桶
2.把arr[i] 插入到bucket[n*array[i]]
3.桶内排序
4.产生新的排序后的列表
'''
bucket_list = [[] for _ in range(n)]
for data in arr:
index = int(data * n)
bucket_list[index].append(data)
for i in range(n):
bucket_list.sort()
index = 0
for i in range(n):
for j in range(len(bucket_list[i])):
arr[index] = bucket_list[i][j]
index += 1
return arr
def radix_sort(s):
# 记录当前正在排哪一位，最低位为1
i = 0
max_num = max(s)
j = len(str(max(s))) # 记录最大值的位数
while i < j:
bucket_list = [[] for _ in range(10)]
for x in s:
bucket_list[int(x / (10 ** i)) % 10].append(x) # 找到位置放入桶数组
s.clear()
for x in bucket_list: # 放回原数组
for y in x:
s.append(y)
i += 1
return s