python实现各种排序

1、冒泡排序：

 1 # -*- coding: utf-8 -*- 
 2 def BubbleSort(a):
 3     n=len(a)
 4     for i in range(0,n-1):
 5         swapped=False
 6         for j in range(0,n-i-1):
 7             if a[j]>a[j+1]:
 8                 a[j],a[j+1]=a[j+1],a[j]
 9                 swapped=True
10         if not swapped: break
11     print a
12 a=[10,8,3,2,4,6,9]
13 BubbleSort(a)
14 input()

代码不难，但是需要注意的几个地方：

注意循环的嵌套以及循环的作用域，break是对第一个for循环起作用的；还有a[j],a[j+1]=a[j+1],a[j]实现互换了两个元素，举例：a=1 b=2 a,b=b,a+b 结果a=2,b=3,b是有原来的a,b相加得到的，并不是用的新的a值。

一个冒泡的变种，就是每次把最小的值放在前面：

 1  1 # -*- coding: utf-8 -*- 
 2  2 def BubbleSort(a):
 3  3     n=len(a)
 4  4     for i in range(0,n-1):
 5  5         for j in range(n-1,i,-1):
 6  6             if a[j]<a[j-1]:
 7  7                 a[j],a[j-1]=a[j-1],a[j]
 8  8     print a
 9  9 a=[10,8,3,2,4,6,9]
10 10 BubbleSort(a)
11 11 input()

注意一点，range(0,n)和range(n,0,-1)，都是左边的值能取到，如range(0,10)得到0-9这10个数，range(10,0,-1)得到10-1这10个数，这与数组的下标要对应好。

2、插入排序：

 1 def InsertSort(a):
 2     n=len(a)
 3     for i in range(1,n):
 4         for j in range(i,0,-1):
 5             if a[j]<a[j-1]:
 6                 a[j],a[j-1]=a[j-1],a[j]
 7             else: break
 8     print a
 9 a=[3,7,5,8,9,1,10]
10 InsertSort(a)
11 input()

这种方法是如果满足条件每次都交换前后两个值，感觉效率不是很高。

另一种方式：

 1 def InsertSort(a):
 2     n=len(a)
 3     for i in range(1,n):
 4         k=a[i]
 5         j=i-1
 6         while j>=0 and a[j]>k:
 7             a[j+1]=a[j]
 8             j=j-1
 9         a[j+1]=k
10     print a
11 a=[3,7,5,8,9,1,10]
12 InsertSort(a)
13 input()

插入排序的改进版，希尔排序：

 1 def ShellSort(a):
 2     n=len(a)
 3     span=n/2
 4     while span>=1:
 5         for i in range(span,n):
 6             k=a[i]
 7             j=i-span
 8             while j>=0 and a[j]>k:
 9                 a[j+span]=a[j]
10                 j=j-span
11             a[j+span]=k
12         span=span/2
13     print a
14 a=[3,7,5,8,9,1,10]
15 ShellSort(a)
16 input()

3、选择排序：

 1 def SelectSort(a):
 2     n=len(a)
 3     for i in range(0,n-1):
 4         min=i
 5         for j in range(i+1,n):
 6             if a[j]<a[min]:
 7                 min=j
 8         a[i],a[min]=a[min],a[i]
 9     print a
10 a=[3,7,5,8,9,1,10]
11 SelectSort(a)
12 input()

上面方法是每次选择最小的元素插在前面，还可以每次选择最大的元素插在后面。

 1 def SelectSort(a):
 2     n=len(a)
 3     for i in range(n-1,0,-1):
 4         max=i
 5         for j in range(0,i):
 6             if a[j]>a[max]:
 7                 max=j
 8         a[i],a[max]=a[max],a[i]
 9     print a
10 a=[3,7,5,8,9,1,10,2]
11 SelectSort(a)
12 input()

4、快速排序：

def QuickSort(a,begin,end):
    b=begin
    e=end
    if b>=e:
        return
    m=a[b]
    while b<e:
        while b<e and a[e]>=m:
            e=e-1
        a[b]=a[e]
        while b<e and a[b]<=m:
            b=b+1
        a[e]=a[b]
    a[b]=m
    QuickSort(a,begin,b-1)
    QuickSort(a,b+1,end)
a=[5,3,8,7,2,6,9,1]
QuickSort(a,0,7)
print a
input()

经典的快速排序，用到了递归的方法，算法很经典，认真分析会有很大的收获的。

未完待续。。。