------------------希尔排序-------------
一直没搞懂希尔排序怎么搞得
def Shell_sort(L):
step = len(L)/2
while step > 0:
for i in range(step,len(L)): #在索引为step到len（L）上，比较L[i]和L[i-step]的大小
while(i >= step and L[i] < L[i-step]): #这里可以调整step从小到大或者从大到小排列
L[i],L[i-step] = L[i-step],L[i]
i -= step
step /= 2
print L
Shell_sort(L)
------------------插入排序-------------
一个有序数列，一个无序数列，遍历无序数列，把数据插入到有序数列的相应位置
def insertion_sort(A):
length=len(A)
for i in range(1,length):
key=A[i]
j=i-1
while j>0 and A[j]>key:
A[j+1]=A[j]
j=j-1
A[j+1]=key
return A
------------------冒泡排序-------------
比较相邻的两个元素，保证每次遍历到最后的元素是最大的
def bubble_sort(A):
length=len(A)
for i in range(length-1):
for j in range(length-i-1):
if A[j]>A[j+1]:
A[j],A[j+1]=A[j+1],A[j]
return A
------------------选择排序-------------
从未排序的数列中找到最小的元素放在起始位置
def selection_sort(A):
length=len(A)
for i in range(length):
min_=i
for j in range(i+1,length):
if A[j]<A[min_]:
min_=j
A[i],A[min_]=A[min_],A[i]
return A
------------------快速排序-------------
一个元素作为基准，比基准数大的放右边，小的放左边，再对左右区间递归
def quik_sort(A):
def qsort(A,left,right):
if left>right:
return A
l=left
r=right
key=A[l]
while l<r:
while A[r]>=key and l<r:
r-=1
while A[l]<=key and l<r:
l+=1
A[l],A[r]=A[r],A[l]
A[left],A[l]=A[l],A[left]
qsort(A,left,l-1)
qsort(A,r+1,right)
return A
return qsort(A,0,len(A)-1)
------------------归并排序-------------
递归分解数组，再合并
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 += left[l:]
result += right[r:]
return result
------------------堆排序-------------
将无序列表看成二叉树，每次调整二叉树成为最大堆，即根节点是最大的元素，然后把根节点和最后一个元素互换，递归调整剩余元素
#建堆
def build_max_heap(A):
lastnode=math.floor((len(A))/2-1)
for i in range(lastnode,-1,-1):
max_heapify(A,i)
return A
#维护最大堆
def max_heapify(A,i):
length=len(A)
max_index=i
if (2*i+1)<length:
left=2*i+1
if A[left]>A[i]:
max_index=left
if (2*i+2)<length:
right=2*i+2
if A[right]>A[max_index]:
max_index=right
if max_index!=i:
A[max_index],A[i]=A[i],A[max_index]
max_heapify(A,max_index)
return A
#堆排序
def heapsort(A):
length=len(A)
A=build_max_heap(A)
for i in range(length-1,-1,-1):
A[0],A[i]=A[i],A[0]
A[:i]=max_heapify(A[:i],0)
return A