8000 python selectionSort 实现错误 · locenco/JS-Sorting-Algorithm@85ec055 · GitHub
[go: up one dir, main page]
Skip to content

Commit 85ec055

Browse files
corningsuncorningsun
committed
python selectionSort 实现错误
1 parent bf9e301 commit 85ec055

File tree

4 files changed

+97
-234
lines changed

4 files changed

+97
-234
lines changed

‎.gitignore

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -13,4 +13,5 @@ _book
1313
# eBook build output
1414
*.epub
1515
*.mobi
16-
*.pdf
16+
*.pdf
17+
\.idea/

‎2.selectionSort.md

Lines changed: 9 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -42,10 +42,15 @@ function selectionSort(arr) {
4242

4343
```python
4444
def selectionSort(arr):
45-
for i in range(len(arr)-1):
46-
for j in range(i+1, len(arr)):
47-
if arr[j] < arr[i]:
48-
arr[i], arr[j] = arr[j], arr[i]
45+
for i in range(len(arr) - 1):
46+
# 记录最小数的索引
47+
minIndex = i
48+
for j in range(i + 1, len(arr)):
49+
if arr[j] < arr[minIndex]:
50+
minIndex = j
51+
# i 不是最小数时，将 i 和最小数进行交换
52+
if i != minIndex:
53+
arr[i], arr[minIndex] = arr[minIndex], arr[i]
4954
return arr
5055
```
5156

‎src/pythonSortTest.py

Lines changed: 86 additions & 64 deletions
Original file line numberDiff line numberDiff line change
@@ -2,77 +2,89 @@
22
# Create by LokiSharp(loki.sharp#gmail) at 2017-1-22
33
'''
44

5-
TOTAL=5000
5+
TOTAL = 5000
6+
67

78
def sortTest(func, total=1000):
89
import random, copy, operator, math, time
9-
arrList = [i for i in range(-math.floor(total/2),math.ceil(total/2))]
10+
arrList = [i for i in range(-math.floor(total / 2), math.ceil(total / 2))]
1011
arrListR = copy.deepcopy(arrList)
11-
while operator.eq(arrList,arrListR):
12+
while operator.eq(arrList, arrListR):
1213
random.shuffle(arrListR)
13-
#print("--- [Origin List]", arrList, "Use", func.__name__,"with Total:", len(arrList))
14-
#print("--> [Random List]", arrListR, "Use", func.__name__,"with Total:", len(arrList))
14+
# print("--- [Origin List]", arrList, "Use", func.__name__,"with Total:", len(arrList))
15+
# print("--> [Random List]", arrListR, "Use", func.__name__,"with Total:", len(arrList))
1516
start = time.clock()
1617
arrListR = func(arrListR)
1718
end = time.clock()
18-
runtime = end-start
19-
#print("--> [Sorted List]", arrListR, "Use", func.__name__,"with Total:", len(arrList))
19+
runtime = end - start
20+
# print("--> [Sorted List]", arrListR, "Use", func.__name__,"with Total:", len(arrList))
2021
if operator.eq(arrList, arrListR):
21-
print("[Success]", func.__name__,"with Total:", len(arrList),"in %.5fs" % runtime)
22+
print("[Success]", func.__name__, "with Total:", len(arrList), "in %.5fs" % runtime)
2223
return True
2324
else:
24-
print("[Fail]", func.__name__,"with Total:", len(arrList),"in %.5fs" % runtime)
25+
print("[Fail]", func.__name__, "with Total:", len(arrList), "in %.5fs" % runtime)
2526
return False
2627

28+
2729
def bubbleSort(arr):
2830
for i in range(1, len(arr)):
29-
for j in range(0, len(arr)-i):
30-
if arr[j] > arr[j+1]:
31+
for j in range(0, len(arr) - i):
32+
if arr[j] > arr[j + 1]:
3133
arr[j], arr[j + 1] = arr[j + 1], arr[j]
3234
return arr
3335

36+
3437
def selectionSort(arr):
35-
for i in range(len(arr)-1):
36-
for j in range(i+1, len(arr)):
37-
if arr[j] < arr[i]:
38-
arr[i], arr[j] = arr[j], arr[i]
38+
for i in range(len(arr) - 1):
39+
# 记录最小数的索引
40+
minIndex = i
41+
for j in range(i + 1, len(arr)):
42+
if arr[j] < arr[minIndex]:
43+
minIndex = j
44+
# i 不是最小数时，将 i 和最小数进行交换
45+
if i != minIndex:
46+
arr[i], arr[minIndex] = arr[minIndex], arr[i]
3947
return arr
4048

49+
4150
def insertionSort(arr):
4251
for i in range(len(arr)):
43-
preIndex = i-1
52+
preIndex = i - 1
4453
current = arr[i]
4554
while preIndex >= 0 and arr[preIndex] > current:
46-
arr[preIndex+1] = arr[preIndex]
47-
preIndex-=1
48-
arr[preIndex+1] = current
55+
arr[preIndex + 1] = arr[preIndex]
56+
preIndex -= 1
57+
arr[preIndex + 1] = current
4958
return arr
5059

60+
5161
def shellSort(arr):
5262
import math
53-
gap=1
54-
while(gap < len(arr)/3):
55-
gap = gap*3+1
63+
gap = 1
64+
while (gap < len(arr) / 3):
65+
gap = gap * 3 + 1
5666
while gap > 0:
57-
for i in range(gap,len(arr)):
67+
for i in range(gap, len(arr)):
5868
temp = arr[i]
59-
j = i-gap
60-
while j >=0 and arr[j] > temp:
61-
arr[j+gap]=arr[j]
62-
j-=gap
63-
arr[j+gap] = temp
64-
gap = math.floor(gap/3)
69+
j = i - gap
70+
while j >= 0 and arr[j] > temp:
71+
arr[j + gap] = arr[j]
72+
j -= gap
73+
arr[j + gap] = temp
74+
gap = math.floor(gap / 3)
6575
return arr
6676

77+
6778
def mergeSort(arr):
6879
import math
69-
if(len(arr)<2):
80+
if (len(arr) < 2):
7081
return arr
71-
middle = math.floor(len(arr)/2)
82+
middle = math.floor(len(arr) / 2)
7283
left, right = arr[0:middle], arr[middle:]
7384
return merge(mergeSort(left), mergeSort(right))
7485

75-
def merge(left,right):
86+
87+
def merge(left, right):
7688
result = []
7789
while left and right:
7890
if left[0] <= right[0]:
@@ -85,38 +97,43 @@ def merge(left,right):
8597
result.append(right.pop(0));
8698
return result
8799

100+
88101
def quickSort(arr, left=None, right=None):
89-
left = 0 if not isinstance(left,(int, float)) else left
90-
right = len(arr)-1 if not isinstance(right,(int, float)) else right
102+
left = 0 if not isinstance(left, (int, float)) else left
103+
right = len(arr) - 1 if not isinstance(right, (int, float)) else right
91104
if left < right:
92105
partitionIndex = partition(arr, left, right)
93-
quickSort(arr, left, partitionIndex-1)
94-
quickSort(arr, partitionIndex+1, right)
106+
quickSort(arr, left, partitionIndex - 1)
107+
quickSort(arr, partitionIndex + 1, right)
95108
return arr
96109

110+
97111
def partition(arr, left, right):
98112
pivot = left
99-
index = pivot+1
113+
index = pivot + 1
100114
i = index
101-
while i <= right:
115+
while i <= right:
102116
if arr[i] < arr[pivot]:
103117
swap(arr, i, index)
104-
index+=1
105-
i+=1
106-
swap(arr,pivot,index-1)
107-
return index-1
118+
index += 1
119+
i += 1
120+
swap(arr, pivot, index - 1)
121+
return index - 1
122+
108123

109124
def swap(arr, i, j):
110125
arr[i], arr[j] = arr[j], arr[i]
111126

127+
112128
def buildMaxHeap(arr):
113129
import math
114-
for i in range(math.floor(len(arr)/2),-1,-1):
115-
heapify(arr,i)
130+
for i in range(math.floor(len(arr) / 2), -1, -1):
131+
heapify(arr, i)
132+
116133

117134
def heapify(arr, i):
118-
left = 2*i+1
119-
right = 2*i+2
135+
left = 2 * i + 1
136+
right = 2 * i + 2
120137
largest = i
121138
if left < arrLen and arr[left] > arr[largest]:
122139
largest = left
@@ -127,39 +144,44 @@ def heapify(arr, i):
127144
swap(arr, i, largest)
128145
heapify(arr, largest)
129146

147+
130148
def swap(arr, i, j):
131149
arr[i], arr[j] = arr[j], arr[i]
132150

151+
133152
def heapSort(arr):
134153
global arrLen
135154
arrLen = len(arr)
136155
buildMaxHeap(arr)
137-
for i in range(len(arr)-1,0,-1):
138-
swap(arr,0,i)
139-
arrLen -=1
156+
for i in range(len(arr) - 1, 0, -1):
157+
swap(arr, 0, i)
158+
arrLen -= 1
140159
heapify(arr, 0)
141160
return arr
142161

162+
143163
def countingSort(arr, maxValue=None):
144-
bucketLen = maxValue+1
145-
bucket = [0]*bucketLen
146-
sortedIndex =0
164+
bucketLen = maxValue + 1
165+
bucket = [0] * bucketLen
166+
sortedIndex = 0
147167
arrLen = len(arr)
148168
for i in range(arrLen):
149169
if not bucket[arr[i]]:
150-
bucket[arr[i]]=0
151-
bucket[arr[i]]+=1
170+
bucket[arr[i]] = 0
171+
bucket[arr[i]] += 1
152172
for j in range(bucketLen):
153-
while bucket[j]>0:
173+
while bucket[j] > 0:
154174
arr[sortedIndex] = j
155-
sortedIndex+=1
156-
bucket[j]-=1
175+
sortedIndex += 1
176+
bucket[j] -= 1
157177
return arr
158178

159-
sortTest(bubbleSort, TOTAL)
160-
sortTest(selectionSort, TOTAL)
161-
sortTest(insertionSort, TOTAL)
162-
sortTest(shellSort, TOTAL)
163-
sortTest(mergeSort, TOTAL)
164-
sortTest(quickSort, TOTAL)
165-
sortTest(heapSort, TOTAL)
179+
180+
if __name__ == '__main__':
181+
sortTest(bubbleSort, TOTAL)
182+
sortTest(selectionSort, TOTAL)
183+
sortTest(insertionSort, TOTAL)
184+
sortTest(shellSort, TOTAL)
185+
sortTest(mergeSort, TOTAL)
186+
sortTest(quickSort, TOTAL)
187+
sortTest(heapSort, 32E0 TOTAL)

0 commit comments

Comments
 (0)
0