# Python 排序算法

Python暑假玩了段时间，没怎么写过东西，加上算法好久没看，复习一下。

Insert Sort

```def insert_sort(list):
length = len(list)
if length < 2:
return list
for i in range(1,length):
num = list[i]
j = i - 1
while j>=0 and list[j]>num:
list[j+1] = list[j]
j-=1
list[j+1] = num
return list```

Bubble Sort

```def bubble_sort(list):
length = len(list)
if length < 2:
return list
for i in range(length-1):
for j in range(length-i-1):
if list[j] > list[j+1]:
list[j],list[j+1]=list[j+1],list[j]
return list```

Selection  Sort

```def selection_sort(list):
length = len(list)
if length < 2:
return list
for i in range(length-1):
smallest = list[i]
location = i
for j in range(i,length):
if list[j] < smallest:
smallest = list[j]
location = j
if i!=location:
list[i],list[location] = list[location],list[i]
return list```

Merge Sort

```class merge_sort(object):
def _merge(self, alist, p, q, r):
left = alist[p:q+1]
right = alist[q+1:r+1]
for i in range(p,r+1):
if len(left)>0 and len(right)>0:
if left[0]<=right[0]
alist[i] = left.pop(0)
else:
alist[i] = right.pop(0)
elif len(right)==0:
alist[i] = left.pop(0)
elif len(left)==0:
alist[i] = right.pop(0)

def _merge_sort(self, alist, p, r):
if p<r:
q = int((p+r)/2)
self._merge_sort(alist, p, q)
self._merge_sort(alist, q+1, r)
self._merge(alist, p, q, r)

def __call__(self, list):
self._merge_sort(list, 0, len(list)-1)
return list```

HeapSort

```def heap_sort(list):
build_heap(list)
length = len(list)
for i in reversed(range(1, length)):
list[0],list[i] = list[i],list[0]
heapify(list, 0, i - 1)

def build_heap(list):
length = len(list)
for i in reversed(range(0, (length - 1) / 2)):
heapify(list, i, length - 1)

def heapify(list, low, high):
left = low * 2 + 1
right = left + 1
current = low
tmp = list[low]
while left <= high:
if right <= high:
if list[left] < list[right]:
next = right
else:
next = left
else:
next = left
if tmp < list[next]:
list[current] = list[next]
current = next
left = current * 2 + 1
right = left + 1
else:
break
list[current] = tmp```

QuickSort

```class quick_sort(object):
def _partition(self, alist, p, r):
i = p-1
x = alist[r]
for j in range(p, r):
if alist[j]<=x:
i += 1
alist[i], alist[j] = alist[j], alist[i]
alist[i+1], alist[r] = alist[r], alist[i+1]
return i+1

def _quicksort(self, alist, p, r):
if p<r:
q = self._partition(alist, p, r)
self._quicksort(alist, p, q-1)
self._quicksort(alist, q+1, r)

def __call__(self, list):
self._quicksort(list, 0, len(list)-1)
return list```

ShellSort

```def shell_sort(list):
increment = 50
while increment > 1:
increment = increment / 3 + 1
shell_pass(list, increment)
print "increment:", increment, ", list:", list

def shell_pass(list, increment):
length = len(list)
for i in range(increment, length):
tmp = list[i]
k = i
while k >= increment and list[k - increment] > tmp:
list[k] = list[k - increment]
k -= increment
list[k] = tmp```