# 前言

python本身有sorted函数。不过下面我们自己实现一下。

1. 每次比较只有2个元素。包括插入排序，快速排序，堆排序，归并排序，冒泡排序。他们最好的效率只能到O(nlgn).可以通过画决策树证明。 一共有n!个节点。高度h的数最多有$$2^h$$个节点。所以有$$2^h \geq n!$$。通过斯特林公式$$n!=\sqrt{2πn}(\frac{n}{e})^n(1+\Theta(\frac{1}{n}))$$ 可以得证。
2. 对数据做些操作。譬如计数排序。

# 1.插入排序

#升序
def insert_sort(literal):
if not literal or len(literal) == 1:
return literal

sorted = literal[:1]

for i in range(1, len(literal)):
v = literal[i]
sorted.append(0)
for j in range(i-1, -1, -1):
if v < sorted[j]:
sorted[j+1] = sorted[j]
else:
sorted[j+1] = v
break

return sorted


python insert_sort.py 6.66s user 0.45s system 98% cpu 7.192 total

# 2. 选择排序

def select_sort(data):
def swap(i, j):
temp = data[i]
data[i] = data[j]
data[j] = temp

for i in range(len(data)):
min = data[i]
index = i
for j in range(i, len(data)):
if data[j] < min:
min = data[j]
index = j
swap(i, index)
return data


# 3. 归并排序

#升序
def merge_sort(literal):

def divide(literal):
end = int(len(literal)/2)
return (literal[:end], literal[end:])

def conquer(literal):
return merge_sort(literal)

def merge(literal1, literal2):
ret = []
len1 = len(literal1)
len2 = len(literal2)
i1 = 0
i2 = 0
while len1 or len2:
if not len1 and len2:
ret.extend(literal2[i2:])
return ret
if not len2 and len1:
ret.extend(literal1[i1:])
return ret

v1 = literal1[i1]
v2 = literal2[i2]
if v1 <= v2:
ret.append(v1)
len1 -= 1
i1 += 1
else:
ret.append(v2)
len2 -= 1
i2 += 1
return ret

if not literal or len(literal) == 1:
return literal

literal1, literal2 = divide(literal)
literal1 = conquer(literal1)
literal2 = conquer(literal2)
return  merge(literal1, literal2)


python merge_sort.py 0.22s user 0.02s system 84% cpu 0.283 total

# 4. 冒泡排序

#!/usr/bin/env python
import sys
import random
def bubble_sort(data):
def swap(i, j):
temp = data[i]
data[i] = data[j]
data[j] = temp

exchanged = False
for i in range(len(data)):
for j in range(len(data)-1, i, -1):
if data[j] < data[j-1]:
swap(j, j-1)
exchanged = True
if not exchanged:
return data
return data


# 5. 堆排序

#!/usr/bin/env python
import sys
import random

def heap_sort(data):
datalength = len(data)
data.insert(0, 0)

def parent_index(i):
return i >> 1

def left_index(i):
return i << 1

def right_index(i):
return left_index(i)+1

def max_heapfy(heap_size, i):
left = left_index(i)
right = right_index(i)
max = data[i]
key = i
if left <= heap_size and data[left] > max:
max = data[left]
key  = left

if right <= heap_size and data[right] > max:
max = data[right]
key = right
if key != i:
swap(i, key)
max_heapfy(heap_size, key)

def build_heap():
for i in range(int(datalength/2), 0, -1):
max_heapfy(datalength, i)

def swap(i, j):
temp = data[i]
data[i] = data[j]
data[j] = temp

build_heap()
for i in range(datalength, 0, -1):
swap(i, 1)
max_heapfy(i-1, 1)

return data[1:]


# 6. 快速排序

## 实现1

def quick_sort(literal):

def divide(literal):
v1 = literal[0]
v2 = literal[1]
v = max(v1, v2)
literal1 = []
literal2 = []
if v1 == v2:
literal1.append(v1)
literal2.append(v2)
for i in literal[2:]:
if i < v:
literal1.append(i)
else:
literal2.append(i)
else:
for i in literal:
if i < v:
literal1.append(i)
else:
literal2.append(i)

return (literal1, literal2)

def conquer(literal):
return quick_sort(literal)

def merge(literal1, literal2):
ret = []
ret.extend(literal1)
ret.extend(literal2)
return ret

if not literal or len(literal) == 1:
return literal

literal1, literal2 = divide(literal)
literal1 = conquer(literal1)
literal2 = conquer(literal2)
return  merge(literal1, literal2)


## 实现二的改进是原地排序

我有个问题没有想清楚，这个程序和上面的程序差不多，都是递归实现，但是上面的程序可以排序100万个数都没问题，这个程序排序到2万个数就报堆栈溢出了。暂时放个问号？？？？

#升序, 原地排序
def quick_sort(literal, start, end):
def swap(i, j):
temp = literal[i]
literal[i] = literal[j]
literal[j] = temp

def divide(start, end):
i = start
key = literal[start]

for j in range(start+1, end):
if literal[j] <= key:
swap(j,i+1)
i += 1
swap(i, start)
return i+1

if not literal or len(literal) <= 1:
return
if (end-start) <= 1:
return
index = divide(start, end)
quick_sort(literal, start, index)
quick_sort(literal, index, end)
return literal


# 7. 计数排序

def count_sort(alist, k):
'''
要求元素都比较小。时间效率是O(k+n),k为最大值。
'''
countList = [0 for _ in range(k+1)]
for v in alist:
countList[v] += 1
retList = [0 for _ in range(len(countList))]
for i, v in enumerate(countList):
retList.extend([i for _ in range(v)])
return retList


# 8. 基数排序

理论上这是最佳的排序算法，但是在实践中，最优秀的是快速排序

# -*- coding:utf-8 -*-
#!/usr/bin/env python
import sys
import random

'''
这个是简单版本，只实现了十进制的。
'''
def count_sort(alist, p):
'''
要求元素都比较小。时间效率是O(k+n),k为最大值。p为要排序的位置
'''
def get_position_value(v, p):
for i in range(1, p+1):
left = v % 10
v = v/10
return left
countList = [0 for _ in range(10)]
for v in alist:
countList[get_position_value(v, p)] += 1
sum = 0
#calculate the position
for i in range(10):
sum += countList[i]
countList[i] = sum

retList = [0 for _ in range(len(alist))]
for v in alist[::-1]:
index = countList[get_position_value(v, p)]
retList[index-1] = v
countList[get_position_value(v, p)] -= 1
return retList

for i in range(1, length+1):
data = count_sort(data, i)

return data


Tags: