1 冒泡排序
class BubbleSort:
def bubbleSort(self, A, n):
# write code here
for i in range(n-1):
for j in range(n-1-i):
if A[j] > A[j+1]:
A[j], A[j+1] = A[j+1], A[j]
return A
2 选择排序
class SelectionSort:
def selectionSort(self, A, n):
# write code here
for i in range(n-1):
e = A[i]
k = i
for j in range(i+1,n):
if A[j] < A[i]:
A[i] = A[j]
k = j
if k != i:
A[k] = e
return A
3 插入排序
class InsertionSort:
def insertionSort(self, A, n):
# write code here
for i in range(1, n):
x = A[i]
j = i
while j > 0 and A[j-1] > x:
A[j] = A[j-1]
j -= 1
A[j] = x
return A
4 归并排序
class MergeSort:
def mergeSort(self, A, n):
# write code here
if len(A) == 1:
return A
num = len(A)//2
left = self.mergeSort(A[:num], num)
right = self.mergeSort(A[num:], num)
i, j = 0, 0
result = []
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
5 快速排序
class QuickSort:
def quickSort(self, A, n):
# write code here
self.qsort(A, 0, n-1)
return A
def qsort(self, A, l, r):
if l >= r:
return
pivot = A[l]
i = l
j = r
while i < j:
while i < j and A[j] > pivot:
j -= 1
if i < j:
A[i] = A[j]
i += 1
while i < j and A[i] < pivot:
i += 1
if i < j:
A[j] = A[i]
j -= 1
A[i] = pivot
self.qsort(A, l, i-1)
self.qsort(A, i+1, r)
6 堆排序
class HeapSort:
def heapSort(self, A, n):
# write code here
def siftdown(A, e, begin, end):
i, j = begin, begin*2+1
while j<=end:
if j+1 <= end and A[j+1]<A[j]:
j += 1
if e < A[j]:
break
A[i] = A[j]
i, j = j, 2*j+1
A[i] = e
end = n
for i in range((end-1)/2, -1, -1):
siftdown(A, A[i], i, end-1)
for i in range(end-1, 0, -1):
e = A[i]
A[i] = A[0]
siftdown(A, e, 0, i-1)
return A[::-1]
