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

先看个好玩的视频：各个算法的声音
 

平均时间复杂度均为O(n^2)：插入，冒泡，选择

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

平均时间复杂度为O(nlogn)的算法：归并排序，堆排序和快速排序

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

平均时间复杂度为O(N*(logN)2)的：希尔

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

转载请注明：于哲的博客 » Python 排序算法