常用排序算法(python)

常用排序算法(python)

常用排序算法(python)

冒泡排序

1
2
3
4
5
6
7
def bubbleSort(alist):
for i in range(len(alist)):
for j in range(len(alist)-i-1):
if alist[j]>alist[j+1]:
tmp = alist[j]
alist[j] = alist[j+1]
alist[j+1] = tmp

选择排序

1
2
3
4
5
6
7
8
9
def selectSort(alist):
for i in range(len(alist)):
minPos = i
for j in range(i+1, len(alist)):
if alist[i]>alist[j]:
minPos = j
tmp = alist[i]
alist[i] = alist[minPos]
alist[minPos] = tmp

插入排序

1
2
3
4
5
6
7
8
def insertSort(alist):
for i in range(1, len(alist)):
current = alist[i]
pos = i
while pos>0 and current<alist[pos-1]:
alist[pos] = alist[pos-1]
pos-=1
alist[pos] = current

希尔排序

1
2
3
4
5
6
7
8
9
10
11
def shellSort(alist):
gap = len(alist)//2
while gap>0:
for i in range(gap, len(alist)):
j = i
current = alist[i]
while j-gap>0 and current<alist[j-gap]:
alist[j] = alist[j-gap]
j = j - gap
alist[j] = current
gap = gap // 2

归并排序

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
def mergeSort(alist):
if len(alist)>1:
mid = len(alist) // 2
left = alist[:mid]
right = alist[mid:]

mergeSort(left)
mergeSort(right)

i,j,k = 0,0,0
while i<len(left) and j<len(right):
if left[i]<right[j]:
alist[k] = left[i]
i+=1
else:
alist[k] = right[j]
j+=1
k+=1
while i<len(left):
alist[k] = left[i]
k+=1
i+=1
while j<len(right):
alist[k] = right[j]
k+=1
j+=1

快速排序

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
def quickSort(alist):
quickSortHelper(alist, 0, len(alist)-1)

def quickSortHelper(alist, first, last):
if first<last:
splitpoint = partition(alist, first, last)
quickSortHelper(alist, first, splitpoint-1)
quickSortHelper(alist, splitpoint + 1, last)

def partition(alist, first, last):
pivot = alist[first]
leftmark = first + 1
rightmark = last
done = False
while not done:
while leftmark <= rightmark and alist[leftmark] <= pivot:
leftmark += 1
while rightmark >= leftmark and alist[rightmark] >= pivot:
rightmark -= 1
if rightmark < leftmark:
done = True
else:
tmp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = tmp
tmp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = tmp
return rightmark
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×