各种排序的时间复杂度和空间复杂度
以下
冒泡排序，选择排序，插入排序，合并排序，快速排序，希尔排序
1 冒泡排序（Bubble Sort）
冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。冒泡排序对n个项目需要O(n^2)的比较次数，且可以原地排序。尽管这个算法是最简单了解和实现的排序算法之一，但它对于包含大量的元素的数列排序是很没有效率的。
python支持对两个数字同时交换， a, b = b, a。就可以直接交换a和b的值了。
def bubble_sort(a_list):
exchange = True
pass_num = len(a_list)-1
while pass_num > 0 and exchange:
exchange = False
for i in range(pass_num):
if a_list[i] > a_list[i+1]:
exchange = True
a_list[i], a_list[i+1] = a_list[i+1], a_list[i]
pass_num = pass_num-1
if __name__ == '__main__':
a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
bubble_sort(a_list)
print a_list
2 选择排序
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。时间复杂度O(n^2)
def selection_sort(a_list):
for full_slot in range(len(a_list)-1, 0, -1):
pos_max = 0
for location in range(1, full_slot+1):
if a_list[location] > a_list[pos_max]:
pos_max = location
a_list[full_slot], a_list[pos_max] = a_list[pos_max], a_list[full_slot] if __name__ == '__main__':
a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
selection_sort(a_list)
print a_list
3 插入排序
插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O（1）的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
def insertion_sort(a_list):
for index in range(1, len(a_list)):
current = a_list[index]
position = index
while position > 0 and a_list[position-1] > current:
a_list[position] = a_list[position-1]
position = position -1
a_list[position] = current
a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
insertion_sort(a_list)
print a_list
4 合并排序
典型的是二路合并排序，将原始数据集分成两部分(不一定能够均分)，分别对它们进行排序，然后将排序后的子数据集进行合并，这是典型的分治法策略。时间复杂度O(nlogn)
def merge_sort(a_list):
print "Splitting", a_list
if len(a_list) > 1:
mid = len(a_list) //2
left_half = a_list[:mid]
right_half = a_list[mid:]
merge_sort(left_half)
merge_sort(right_half)
i = 0
j = 0
k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
a_list[k] = left_half[i]
i = i+1
else:
a_list[k] = right_half[j]
j = j+1
k = k+1
while i < len(left_half):
a_list[k] = left_half[i]
i = i+1
k = k+1
while j < len(right_half):
a_list[k] = right_half[j]
j = j+1
k = k+1
print "Merging", a_list a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
merge_sort(a_list)
print a_list
5 快速排序
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
def quick_sort(a_list):
quick_sort_helper(a_list, 0, len(a_list)-1) def quick_sort_helper(a_list, first, last):
if first < last:
split_point = partition(a_list, first, last)
quick_sort_helper(a_list, first, split_point - 1)
quick_sort_helper(a_list, split_point + 1, last) def partition(a_list, first, last):
pivot_value = a_list[first]
left_mark = first +1
right_mark = last
done = False
while not done:
while left_mark <= right_mark and a_list[left_mark] <= pivot_value:
left_mark = left_mark +1
while a_list[right_mark] >= pivot_value and right_mark >= left_mark:
right_mark = right_mark-1
if right_mark < left_mark:
done = True
else:
temp = a_list[left_mark]
a_list[left_mark] = a_list[right_mark]
a_list[right_mark] = temp
temp = a_list[first]
a_list[first] =a_list[right_mark]
a_list[right_mark] =temp
return right_mark a_list = [54, 26, 93, 17, 77, 31, 44, 50, 20]
quick_sort(a_list)
print a_list
6 希尔排序
类似合并排序和插入排序的结合体，二路合并排序将原来的数组分成左右两部分，希尔排序则将数组按照一定的间隔分成几部分，每部分采用插入排序来排序，有意思的是这样做了之后，元素很多情况下就差不多在它应该呆的位置，所以效率不一定比插入排序差。
def shell_sort(a_list):
#how many sublists, also how many elements in a sublist
sublist_count = len(a_list) // 2
while sublist_count > 0:
for start_position in range(sublist_count):
gap_insertion_sort(a_list, start_position, sublist_count)
print("After increments of size", sublist_count, "The list is", a_list)
sublist_count = sublist_count // 2 def gap_insertion_sort(a_list, start, gap):
#start+gap is the second element in this sublist
for i in range(start + gap, len(a_list), gap):
current_value = a_list[i]
position = i
while position >= gap and a_list[position - gap] > current_value:
a_list[position] = a_list[position - gap] #move backward
position = position - gap
a_list[position] = current_value a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20, 88]
shell_sort(a_list)
print(a_list)