各种简单的排序算法(python版)

1.冒泡排序

#!/usr/bin/python
#coding=utf-8
import sys
a = [ int(i) for i in sys.argv[1:] ]
print a
n = len(a)
#注意range(1,n)产生的序列是 1..n-1
#第一次循环代表的是冒泡的次数
for i in range(1, n):
#注意range(0,n-i)产生的序列是0..n-i-1
#第二次循环代表的是还没排好序的元素的下标
for j in range(0, n-i):
if a[j] > a[j+1]:
tmp = a[j]
a[j] = a[j+1]
a[j+1] = tmp
print a

2.选择排序

#!/usr/bin/python
#coding=utf-8
import sys
a = [ int(i) for i in sys.argv[1:] ]
print a
n = len(a)
#第一次循环代表的是选择好以后要放的位置
for i in range(0, n):
min = i
#第二次循环代表的是在还没排好序的位置上选择
for j in range(i+1, n):
if a[min] > a[j]:
min = j
if not min == i:
tmp = a[min]
a[min] = a[i]
a[i] = tmp
print a

3.插入排序

#!/usr/bin/python
#coding=utf-8
import sys
a = [ int(i) for i in sys.argv[1:] ]
print a
n = len(a)
#第一次循环代表的是还没插入的位置;第0个位置是不用插入的
for i in range(1, n):
tmp = a[i]
j = i
#寻找适合的位置
while j > 0 and a[j-1] > tmp:
a[j] = a[j-1]
j -= 1
a[j] = tmp
print a

4.shell排序
和插入排序差不多.插入排序相当于一开始就把设gap=1的特殊情形.所以把插入排序中的1换成gap,再加一层关于gap的循环就可以了

#!/usr/bin/python
#coding=utf-8
import sys
a = [ int(i) for i in sys.argv[1:] ]
print a
n = len(a)
gap = n/2
while not gap == 0:
for i in range(gap, n, gap):
tmp = a[i]
j = i
while j >= gap and a[j-gap] > tmp:
a[j] = a[j-gap]
j -= gap
a[j] = tmp
gap /= 2
print a

5.快速排序
没有注释....
体会是,为什么python没有自增自减运算呢?

#!/usr/bin/python
#coding=utf-8
import sys
a = [ int(i) for i in sys.argv[1:] ]
print a
n = len(a)
def quicksort(a, left, right):
if left < right:
p = partition(a, left, right)
quicksort(a, left, p-1)
quicksort(a, p+1, right)
def partition(a, left, right):
p = left
for i in range(left+1, right+1):
if a[i] < a[left]:
p += 1
if not p == i:
tmp = a[p]
a[p] = a[i]
a[i] = tmp
tmp = a[left]
a[left] = a[p]
a[p] = tmp
return p
quicksort(a, 0, n-1)
print a