def bubble(alist):
'''bubble'''
length=len(alist)
count=len(alist)
while count>0:
for i in range(length-1):
if alist[i]>alist[i+1]:
alist[i],alist[i+1]=alist[i+1],alist[i]
count-=1
return alist
def bubble_sort(alist):
'''冒泡排序'''
n=len(alist)
for j in range(n-1):
count=0
for i in range(0,n-1-j):
if alist[i]>alist[j]:
alist[i],alist[i+1]=alist[i+1],alist[i]
count+=1
if 0==count:
return
def select_sort(alist):
'''选择排序'''
n=len(alist)
for j in range(n-1):
min_index=j
for i in range(j+1,n): #
if alist[min_index] > alist[i]:
min_index=i
alist[j],alist[min_index]=alist[min_index],alist[j]
def insert_sort(alist):
'''插入排序'''
n=len(alist)
for i in range(1,n):
while i>0:
if alist[i]<alist[i-1]:
alist[i],alist[i-1]=alist[i-1],alist[i]
i-=1
else:
break
def shell_sort(alist):
'''希尔排序——缩小增量排序'''
n=len(alist)
gap=n//2
while gap>0:
for j in range(gap,n):
i=j
while i >0:
if alist[i] < alist[i-gap]:
alist[i],alist[i-gap]=alist[i-gap],alist[i]
i-=gap
else:
break
gap//=2
def quick_sort(alist,first,last):
'''快速排序'''
if first>=last:
return
mid_value=alist[first]
low=first
high=last
while low<high:
while low < high and alist[high]>=mid_value:
high-=1
alist[low]=alist[high]
while low<high and alist[low]<mid_value:
low+=1
alist[high]=alist[low]
alist[low]=mid_value
quick_sort(alist,first,low-1)
quick_sort(alist,low+1,last)
#http://developer.51cto.com/art/201403/430986.htm（详细讲快排）
def QuickSort(myList,start,end):
'''快排2'''
#判断low是否小于high,如果为false,直接返回
if start < end:
i,j = start,end
#设置基准数
base = myList[i]
while i < j:
#如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现
while (i < j) and (myList[j] >= base):
j = j - 1
#如找到,则把第j个元素赋值给第个元素i,此时表中i,j个元素相等
myList[i] = myList[j]
#同样的方式比较前半区
while (i < j) and (myList[i] <= base):
i = i + 1
myList[j] = myList[i]
#做完第一轮比较之后,列表被分成了两个半区,并且i=j,需要将这个数设置回base
myList[i] = base
#递归前后半区
QuickSort(myList, start, i - 1)
QuickSort(myList, j + 1, end)
return myList
myList = [49,38,65,97,76,13,27,49]
print("Quick Sort: ")
QuickSort(myList,0,len(myList)-1)
print(myList)
#####http://yshblog.com/blog/170
def merge_sort(alist):
'''归并排序'''
n=len(alist)
if n<=1:
return alist
mid=n//2
left_li=merge_sort(alist[:mid])
right_li=merge_sort(alist[mid:])
left_pointer,right_pointer=0,0
result=[]
while left_pointer< len[left_li] and right_pointer <len(right_li):
if left_li[left_pointer] < right_li[right_pointer]:
result.append(left_li[left_pointer])
left_pointer+=1
else:
result.append(right_li[right_pointer])
right_pointer+=1
result+=left_li[left_pointer:]
result+=right_li[right_pointer:]
return result
def merge_sort( li ):
#归并2
2 #不断递归调用自己一直到拆分成成单个元素的时候就返回这个元素，不再拆分了
3 if len(li) == 1:
4 return li
5
6 #取拆分的中间位置
7 mid = len(li) // 2
8 #拆分过后左右两侧子串
9 left = li[:mid]
10 right = li[mid:]
11
12 #对拆分过后的左右再拆分 一直到只有一个元素为止
13 #最后一次递归时候ll和lr都会接到一个元素的列表
14 # 最后一次递归之前的ll和rl会接收到排好序的子序列
15 ll = merge_sort( left )
16 rl =merge_sort( right )
17
18 # 我们对返回的两个拆分结果进行排序后合并再返回正确顺序的子列表
19 # 这里我们调用拎一个函数帮助我们按顺序合并ll和lr
20 return merge(ll , rl)
21
22 #这里接收两个列表
23 def merge( left , right ):
24 # 从两个有顺序的列表里边依次取数据比较后放入result
25 # 每次我们分别拿出两个列表中最小的数比较，把较小的放入result
26 result = []
27 while len(left)>0 and len(right)>0 :
28 #为了保持稳定性，当遇到相等的时候优先把左侧的数放进结果列表，因为left本来也是大数列中比较靠左的
29 if left[0] <= right[0]:
30 result.append( left.pop(0) )
31 else:
32 result.append( right.pop(0) )
33 #while循环出来之后 说明其中一个数组没有数据了，我们把另一个数组添加到结果数组后面
34 result += left
35 result += right
36 return result
37
38 if __name__ == '__main__':
39 li = [5,4 ,3 ,2 ,1]
40 li2 = merge_sort(li)
41 print(li2)
###http://www.cnblogs.com/piperck/p/6030122.html
排序方法 时间复杂度（平均） 时间复杂度（最坏) 时间复杂度（最好) 空间复杂度 稳定性 复杂性
直接插入排序 O(n2) O(n2) O(n) O(1) 稳定 简单
希尔排序 O(nlog2n) O(n2) O(n) O(1) 不稳定 较复杂
直接选择排序 O(n2) O(n2) O(n2) O(1) 不稳定 简单
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定 较复杂
冒泡排序 O(n2) O(n2) O(n) O(1) 稳定 简单
快速排序 O(nlog2n) O(n2) O(nlog2n) O(nlog2n) 不稳定 较复杂
归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定 较复杂
基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(n+r) 稳定 较复杂
https://www.cnblogs.com/onepixel/articles/7674659.html
网友评论