β

用Python实现各种排序算法

姚广远的博客 107 阅读

原文链接:http://www.jianshu.com/p/3380ea152c44

1.冒泡排序

比较相邻的元素大小,将小的前移,大的后移,就像水中的气泡一样,最小的元素经过几次移动,会最终浮到水面上。

[code lang=”python”]
def bubble(list):
for i in range(len(list)):
for j in range(0,len(list)-1-i):
if list[j] > list[j+1]:
list[j],list[j+1]=list[j+1],list[j]
if name == ‘main’:
list1 = [2,3,5,7,8,9,6,54,1,42]
bubble(list1)
print(list1)
[/code]

2.插入排序

将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕。

[code lang=”python”]
def insertsort(list):
if list != None:
if len(list) == 1:
pass
else:
for i in range(1,len(list)):#start with second item.
temp = list[i]
for j in range(i):
if list[j]>list[i]:
for k in range(i,j,-1):#
list[k]= list[k-1]
list[j] = temp
if name == ‘main’:
list1 = [3,2,7,5,8,9,6,54,1,42]
insertsort(list1)
print(list1)
[/code]

3.快速排序

(1)这里实现第一轮排序,不妨称第一个元素为锚
(2)i,j分别指向待排序序列的第一和最后一个元素
(3)j与锚比较,若大于锚则左移,直到小于锚的元素停下,与i指向元素交换,i后移
(4)接着,i与锚比较,若小于则右移,直到大于锚的元素停下,与j指向的元素交换,j前移,
(5)i,j交替移动,i==j时,锚temp到达最终位置。

[code lang=”python”]
L = [90,89,78,67,56,45,34,23,12,0]
def first_sort(numbers,i,j):
temp = numbers[i]
while i!=j:
while i<j and numbers[j]>temp:
j = j – 1
if i < j
numbers[i] = numbers[j]
i = i + 1
while i < j and numbers[i]<temp:
i = i + 1
if i <j:
numbers[j] = numbers[i]
j = j – 1
numbers[i] = temp
return i
def quick_sort(numbers,i,j):
if i<j:
middle = first_sort(numbers,i,j)
quick_sort(numbers,i,middle-1)
quick_sort(numbers,middle+1,j)
if name==’main’:
quick_sort(L,0,len(L)-1)
print
[/code]

4.选择排序

从所有序列中先找到最小的,然后放到第一个位置。之后再看剩余元素中最小的,放到第二个位置……以此类推,就可以完成整个的排序工作。

[code lang=”python”]
def selectionsort(list):
if list != None:
for i in range(len(list)):
min = i
for j in range(i+1,len(list)):
if list[min] > list[j]:
min = j
if min != i:
list[min],list[i] = list[i],list[min]
if name == ‘main’:
list1 = [2,3,5,7,8,9,6,54,1,42]
selectionsort(list1)
print(list1)
[/code]

5.希尔排序

先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。

[code lang=”python”]
test=[9,2,3,5,7]
def ShellSort(data,flag):
”’
data: list,to be sorted
flag: 0->asc,1->desc
return a new sorted list
”’
retData=[]
#copy data to retData
for item in data:
retData.append(item)
#sort retData
count=len(retData)
step=count/2;
while step>0:
i=0
while i<count:
j=i+step
while j<count:
t=retData.pop(j)
k=j-step
#asc
if flag==0:
while k>=0:
if t>=retData[k]:
retData.insert(k+1, t)
break
k=k-step
if k < 0:
retData.insert(0, t)
#desc
elif flag==1:
while k>=0:
if t<=retData[k]:
retData.insert(k+1, t)
break
k=k-step
if k<0:
retData.insert(0, t)
j=j+step
i=i+1
step=step/2
return retData
data=ShellSort(test,0)
print ‘Asc:’,data
data=ShellSort(test,1)
print ‘Desc:’,data
[/code]

The post 用Python实现各种排序算法 appeared first on 姚广远 .

作者:姚广远的博客
心有多大世界就有多大
原文地址:用Python实现各种排序算法, 感谢原作者分享。