1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
```c
def BinarySearch(Arr,c):
if len(Arr)==0:
return -1
left=0
right=len(Arr)-1
while right>left
mid=(left+right)//2
if Arr[mid]<c:
left=mid+1
elif Arr[mid]>x:
right=mid-1
else:
return mid
return -1
def bubbleSort(nums):
for i in range(len(nums) - 1): # 遍历 len(nums)-1 次
for j in range(len(nums) - i - 1): # 已排好序的部分不用再次遍历
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j] # Python 交换两个数不用中间变量
return nums
def countingSort(nums):
bucket = [0] * (max(nums) + 1) # 桶的个数
for num in nums: # 将元素值作为键值存储在桶中，记录其出现的次数
bucket[num] += 1
i = 0 # nums 的索引
for j in range(len(bucket)):
while bucket[j] > 0:
nums[i] = j
bucket[j] -= 1
i += 1
return nums
def shellSort(nums):
step = len(nums)
while True:
step = int(step / 3 + 1)#增量序列依次减少
for n in range(step): #希尔排序即在每个分组内用插入排序，增量从1变为step
for i in range(n + step, len(nums), step):
temp=nums[i]
j=i-step
while j>=n and temp<nums[j]:
nums[j+step]=nums[j]
j=j-step
nums[j+step]=temp
print(nums) #插入排序
if step <= 1:
break
def selectionSort(nums):
for i in range(len(nums)-1):#遍历len（nums）-1次
minIndex=i #最小值的下表
for j in range(i+1,len(nums))#在i到len（nums）之间找到最小值
if nums[j]<num{minIndex]
minIndex=j
nums[i],nums[minIndex]=nums[minIndex],nums[i]# 把最小值放在i位置之后i+1
return nums
def quicksort(nums, ipos, epos):
if epos - ipos <= 1:
return nums
beg = ipos
end = epos
while ipos < epos:
while nums[ipos] < nums[epos]:
epos -= 1
nums[ipos], nums[epos] = nums[epos], nums[ipos]
while nums[epos] > nums[ipos]:
ipos += 1
nums[ipos], nums[epos] = nums[epos], nums[ipos]
quicksort(nums, beg, ipos)
quicksort(nums, ipos + 1, end)
def MergeSort(lists):
if len(lists) <= 1:
return lists
num = int( len(lists) / 2 )
left = MergeSort(lists[:num])
right = MergeSort(lists[num:])
return Merge(left, right)
def Merge(left,right):
r, l=0, 0
result=[]
while l<len(left) and r<len(right):
if left[l] <= right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result += list(left[l:])
result += list(right[r:])
return result
def insertionSort(lst):
if len(lst) == 1:
return lst
for i in range(1, len(lst)):#插入排序i从1开始到len-1
temp = lst[i]
j = i - 1 #而j从0开始，从而对lit[0]也参与排序
while j >= 0 and temp < lst[j]:
lst[j + 1] = lst[j]#将list[j]往后移
j -= 1
lst[j + 1] = temp#因为j=j-1，所以每次循环相当于新的j与temp换位置,直到排序完成（即相当于将list[i]大的数依次往后移使list[i]完成插入）
print(lst)
return lst```
|
