0. 生成随机数
from random import randint
def generateRandomList(n, min, max):
nums = [ randint(min, max) for _ in range(n) ]
return nums
1. 选择排序
每次从待排序数组中选出最小的数字，放至待排序最前最前
# 选择排序
def selectionSort(nums: List[int]) -> None:
l = len(nums) # 放置最小值的位置
for flag in range(l):
min_index = l
# 找出剩余最小
for i in range(flag+1, l):
if nums[i] < nums[min_index]:
min_index = i
# 将最小值交换至flag处
nums[l], nums[min_index] = nums[min_index], nums[l]2. 插入排序
每次将下一个数字插入到左边已经排好序的数组中
def insertionSort(nums: List[int]) -> None:
l = len(nums)
for flag in range(1, l):
for i in range(flag-1, -1, -1):
if nums[flag] < nums[i]:
nums[flag], nums[i] = nums[i], nums[flag]
flag = i
else:
break3. 冒泡排序
一遍一遍地进行交换相邻两个元素
def bubbleSort(nums: List[int]) -> None:
l = len(nums)
swapped = True
while swapped:
swapped = False
for i in range(1, l):
if nums[i-1] > nums[i]:
nums[i-1], nums[i] = nums[i], nums[i-1]
swapped = True4. 归并排序
思路：
递归进行：将数组分成两段，对左段和有段分别进行排序，将左段和右段合并再排序
其中，当段长度分到小于15时，采用插入排序对其进行排序
对左右两个有序数组进行排序时，使用原地双指针排序
时间复杂度：总共需要切分logn次，合并logn次，合并时需要遍历每个成员（合并两个有序数组），所以是O(nlogn)
def mergeSort(alist):
n = len(alist)
__mergeSort(alist, 0, n-1)
# return alist
def __mergeSort(alist, start, end):
if start >= end:
return
if end - start <= 15:
insertionSortHelp(alist, start, end)
return
mid = start + ((end-start)>>1)
__mergeSort(alist, start, mid)
__mergeSort(alist, mid+1, end)
if alist[mid] > alist[mid+1]:
merge(alist, start, mid, end)
# 合并有序数列alist[start....mid] 和 alist[mid+1...end] 使之成为有序数列
def merge(alist, start, mid, end):
m = mid - start + 1
n = end - mid
nums1 = alist[start:mid+1] + [0] * (end-mid)
nums2 = alist[mid+1 : end+1]
p1, p2 = m-1, n-1
tail = m + n - 1
while p1 >= 0 or p2 >= 0:
if p1 == -1:
nums1[tail] = nums2[p2]
p2 -= 1
elif p2 == -1:
nums1[tail] = nums1[p1]
p1 -= 1
elif nums1[p1] < nums2[p2]:
nums1[tail] = nums2[p2]
p2 -= 1
else:
nums1[tail] = nums1[p1]
p1 -= 1
tail -= 1
alist[start:end+1] = nums1
def insertionSortHelp(nums: List[int], start: int, end: int) -> None:
for flag in range(start + 1, end + 1):
for i in range(flag-1, start - 1, -1):
if nums[flag] < nums[i]:
nums[flag], nums[i] = nums[i], nums[flag]
flag = i
else:
break5. 快速排序（Quick Sort）
分区：随机选择一根柱子，将大于柱子的放置到柱子右边，将小于柱子的放置到柱子左边
分别对左子区和右子区进行分区，迭代进行，直到某个分区只有一个元素则已经排好序
时间复杂度：O(nlogn)~O(n^2)之间，当每次选区的轴都恰好是中间时（左右成员数量对半分），那么需要选取logn次轴，每选一次轴，就需要遍历n个成员进行排序，所以是O(nlogn)，若每次选取的轴都是区间内的一个极小值，则需要选取n次轴，每次一次需要遍历n-1,n-2,n-3,...次进行排序，所以为O(n^2)
def quickSort(alist):
n = len(alist)
__quickSort(alist, 0, n-1)
def __quickSort(alist, l, r):
if l >= r:
return
p = partitionQS(alist, l, r)
__quickSort(alist, l, p-1)
__quickSort(alist, p+1, r)
def partitionQS(alist, l, r):
flag = alist[l]
pos = l + 1
for i in range(l+1, r+1):
if alist[i] < flag:
nums[pos], nums[i] = nums[i], nums[pos]
pos += 1
nums[l], nums[pos-1] = nums[pos-1], nums[l]
return pos-1评论 (0)
