一、冒泡排序
基本思想：
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
冒泡排序（Bubble sort）：时间复杂度O(n^2)
交换排序的一种。其核心思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序记录为止。
其实现细节可以不同，比如下面3种：
- 最简单排序实现:bubble_sort_simple
- 冒泡排序:bubble_sort
- 改进的冒泡排序:bubble_sort_advance
#!/usr/bin/python
#encoding:UTF-8
#选择排序：时间复杂度-O（n^2）
import numpy as np
sort_data = [3,1,5,7,2,4,9,6,8,1,5]
sort_array = np.array(sort_data)
length = len(sort_array)
print("冒泡排序开始：")
for i in range(length):
for j in range(length - i-1):
if(sort_array[j] > sort_array[j+1]):
t = sort_array[j];
sort_array[j] = sort_array[j+1];
sort_array[j+1] = t;
print(sort_array)
print("排序结束！！！")
1 #!/usr/bin/env python 2 # -*- coding:utf-8 -*- 3 # 冒泡排序算法 4 class SQList: 5 def __init__(self, lis=None): 6 self.r = lis 7 def swap(self, i, j): 8 """定义一个交换元素的方法，方便后面调用。""" 9 temp = self.r[i]; 10 self.r[i] = self.r[j]; 11 self.r[j] = temp; 12 def bubble_sort_simple(self): 13 """最简单的交换排序，时间复杂度O(n^2)""" 14 lis = self.r 15 length = len(self.r) 16 for i in range(length): 17 for j in range(i+1, length):#从前往后走,每次找出最小的 18 if(lis[i] > lis[j]): 19 self.swap(i, j) 20 def bubble_sort(self): 21 """冒泡排序，时间复杂度O(n^2)""" 22 lis = self.r 23 length = len(self.r) 24 for i in range(length): 25 #从后往前走 26 j = length - 1; 27 while j >= i: 28 if(lis[j-1] > lis[j]): 29 self.swap(j, j-1); 30 j -= 1; 31 def bubble_sort_advance(self): 32 """ 33 冒泡排序改进算法，时间复杂度O(n^2) 34 设置flag，当一轮比较中未发生交换动作，则说明后面的元素其实已经有序排列了。 35 对于比较规整的元素集合，可提高一定的排序效率。 36 """ 37 lis = self.r; 38 length = len(self.r); 39 flag = True; 40 i = 0; 41 while i < length and flag: 42 flag = False 43 j = length - 2 44 while j >= i: 45 if lis[j] > lis[j + 1]: 46 self.swap(j, j + 1) 47 flag = True 48 j -= 1 49 i += 1 50 51 if __name__ == '__main__': 52 sqlist = SQList([3,1,5,7,2,4,9,6,8,1,5]) #sqlist是一个对象 53 print "冒泡排序：" 54 print "排序前：", sqlist.r 55 #sqlist.bubble_sort_simple() 56 #sqlist.bubble_sort() 57 sqlist.bubble_sort_advance() 58 print "排序后：", sqlist.r
1 排序前： [3, 1, 5, 7, 2, 4, 9, 6, 8, 1, 5] 2 排序过程： 3 [1, 3, 1, 5, 7, 2, 4, 9, 6, 8, 5] 4 [1, 1, 3, 2, 5, 7, 4, 5, 9, 6, 8] 5 [1, 1, 2, 3, 4, 5, 7, 5, 6, 9, 8] 6 [1, 1, 2, 3, 4, 5, 5, 7, 6, 8, 9] 7 [1, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9] 8 [1, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9] 9 排序后： [1, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9]
二、简单选择排序
简单选择排序（simple selection sort）:时间复杂度O(n^2)
通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n)个记录进行交换。
通俗的说就是，对尚未完成排序的所有元素，从头到尾比一遍，记录下最小的那个元素的下标，也就是该元素的位置。再把该元素交换到当前遍历的最前面。其效率之处在于，每一轮中比较了很多次，但只交换一次。因此虽然它的时间复杂度也是O(n^2)，但比冒泡算法还是要好一点。
基本思想：
在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
1 #!/usr/bin/env python 2 # -*- coding:utf-8 -*- 3 # 简单选择排序：时间复杂度-O（n^2） 4 5 class SQList: 6 def __init__(self, lis=None): 7 self.r = lis 8 def swap(self, i, j): 9 """定义一个交换元素的方法，方便后面调用。""" 10 temp = self.r[i]; 11 self.r[i] = self.r[j]; 12 self.r[j] = temp; 13 def select_sort(self): 14 """简单选择排序，时间复杂度O(n^2)""" 15 lis = self.r; 16 length = len(lis); 17 for i in range(length): 18 minimum = i; 19 for j in range(i+1, length): 20 if(lis[minimum] > lis[j]): 21 minimum = j; 22 if i != minimum: 23 self.swap(minimum, i); 24 def __str__(self): 25 ret = "" 26 for i in self.r: 27 ret += " %s" % i 28 return ret 29 if __name__=='__main__': 30 sqlist = SQList([3,1,5,7,2,4,9,6,8,1,5]); 31 sqlist.select_sort(); 32 print sqlist.r 33 ''' 34 import numpy as np 35 to_insert_data = [3,1,5,7,2,4,9,6,8,1,5] 36 to_insert_array = np.array(to_insert_data) 37 length = len(to_insert_array) 38 print("选择排序法：") 39 for i in range(length): 40 minimum = i 41 for j in range(i+1, length): 42 if(to_insert_array[minimum] > to_insert_array[j]):#第i个元素之和最小的元素交换 43 minimum = j; 44 if(minimum != i): 45 t = to_insert_array[minimum]; 46 to_insert_array[minimum] = to_insert_array[i]; 47 to_insert_array[i] = t; 48 print(to_insert_array) 49 print("一切正常！！！") 50 '''
1 排序过程： 2 [1, 3, 5, 7, 2, 4, 9, 6, 8, 1, 5] 3 [1, 1, 5, 7, 2, 4, 9, 6, 8, 3, 5] 4 [1, 1, 2, 7, 5, 4, 9, 6, 8, 3, 5] 5 [1, 1, 2, 3, 5, 4, 9, 6, 8, 7, 5] 6 [1, 1, 2, 3, 4, 5, 9, 6, 8, 7, 5] 7 [1, 1, 2, 3, 4, 5, 9, 6, 8, 7, 5] 8 [1, 1, 2, 3, 4, 5, 5, 6, 8, 7, 9] 9 [1, 1, 2, 3, 4, 5, 5, 6, 8, 7, 9] 10 [1, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9] 11 [1, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9] 12 [1, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9] 13 [1, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9]
三、直接插入排序
直接插入排序（Straight Insertion Sort）:时间复杂度O(n^2)
基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。
1 #!/usr/bin/env python 2 # -*- coding:utf-8 -*- 3 #插入排序算法：时间复杂度-O（n^2） 4 class SQList: 5 def __init__(self, lis=None): 6 self.r = lis; 7 def insert_sort(self): 8 lis = self.r; 9 length = len(lis); 10 for i in range(1, length): 11 if(lis[i-1] > lis[i]): 12 temp = lis[i];#哨兵 13 j = i-1; 14 while(j>=0 and lis[j] > temp): 15 lis[j+1] = lis[j]; 16 j -= 1; 17 lis[j+1] = temp; 18 print lis; 19 def __str__(self): 20 ret = "" 21 for i in self.r: 22 ret += " %s" % i 23 return ret 24 if __name__ == '__main__': 25 sqlist = SQList([3,1,5,7,2,4,9,6,8,1,5]) 26 print "排序前", sqlist.r 27 print "-----------------" 28 print "排序过程如下:" 29 sqlist.insert_sort(); 30 print "-----------------" 31 print "排序结果",sqlist.r 32 print "OK"
执行过程：
1 排序前 [3, 1, 5, 7, 2, 4, 9, 6, 8, 1, 5] 2 ----------------- 3 排序过程如下: 4 [1, 3, 5, 7, 2, 4, 9, 6, 8, 1, 5] 5 [1, 3, 5, 7, 2, 4, 9, 6, 8, 1, 5] 6 [1, 3, 5, 7, 2, 4, 9, 6, 8, 1, 5] 7 [1, 2, 3, 5, 7, 4, 9, 6, 8, 1, 5] 8 [1, 2, 3, 4, 5, 7, 9, 6, 8, 1, 5] 9 [1, 2, 3, 4, 5, 7, 9, 6, 8, 1, 5] 10 [1, 2, 3, 4, 5, 6, 7, 9, 8, 1, 5] 11 [1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 5] 12 [1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 5] 13 [1, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9] 14 ----------------- 15 排序结果 [1, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9] 16 OK
参考文档：
http://www.cnblogs.com/feixuelove1009/p/6143539.html