算法排序之Python实现
算法排序之Python实现
前言
排序是最经典的问题，基本上玩算法入门就是排序。
python本身有sorted函数。不过下面我们自己实现一下。
以下数据均是在我的同一台macbook上测试的。从结果也可以看出算法的重要性。
排序按模型分类有：
- 每次比较只有2个元素。包括插入排序，快速排序，堆排序，归并排序，冒泡排序。他们最好的效率只能到O(nlgn).可以通过画决策树证明。 一共有n!个节点。高度h的数最多有\(2^h\)个节点。所以有\(2^h \geq n!\)。通过斯特林公式\(n!=\sqrt{2πn}(\frac{n}{e})^n(1+\Theta(\frac{1}{n}))\) 可以得证。
- 对数据做些操作。譬如计数排序。
1.插入排序
这个算法和打牌很像，玩过牌的应该能很快理解。不多解释，看python的简单实现。
其最坏情况是( \Theta(n^2) )
#升序
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. 选择排序
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
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. 归并排序
归并排序描述起来好简单。就是把规模分成两组，一组都小于某个数n, 另一组都大于等于n。于是规模为n的问题，变成了2个n/2规模的问题。一次次这样划分下去，直到只剩下一个元素,一个元素当然是排好充的,然后再两两合并,直到得到原始问题的解。
其最坏情况是( \Theta(nlgn) )
这个思想是分治法
下面是python的实现：
#升序
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
之所以divide写的不那么好看，是为了一定要把问题分解。否则遇到 [1, 1 ,1]这样的数据就悲剧了。
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. 堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
时间效率是(O(n\lg{n}))，但实践中不如快速排序。不过用来实现优先级队列非常好。
#!/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:]
算法描述里索引是从1开始的，我这里取了个巧。补了个无用的0，来达到索引从1开始的目的。
6. 快速排序
快速排序和归并排序差不多。区别是归并排序只是把一个规模为n的问题划分成2个规模为n/2的子问题。
而快速排序划分的两个子问题，本身是有序的。即子问题A中的数都要小于等于子问题B中的数，这样在合并问题时更简单。
由于python的特性。做切片操作其实是做的复制工作。
我这里会提供二个快速排序的实现。供参考。
实现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)
实现二的改进是原地排序
这种方式少了copy的代价，占用的空间更少，少了合并的步骤，效率也会更高。
我有个问题没有想清楚，这个程序和上面的程序差不多，都是递归实现，但是上面的程序可以排序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. 计数排序
这个有个前提条件。必须是整数范围，同时最大的数不能太大。因为效率是O(n+k), 所以k不能太大。
远远小于n时，效率非常高，为线性排序。
参考实现：
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. 基数排序
基数排序要用到计数排序。先对最后一位排序，再对前一位排序，直到排序完成。
同样要求是整数。好的是要求的数字大小范围没有计数排序那么小。
理论上这是最佳的排序算法，但是在实践中，最优秀的是快速排序
其时间复杂度为(O(n\log_rm))，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
上面实现的计数排序是偷懒的做法。因为是新生成的元素，而这里只是对某位排序，需要保留原数字，故要实现完整版的计数排序。
# -*- coding:utf-8 -*-
#!/usr/bin/env python
import sys
import random
def radix_sort(data, length):
'''
这个是简单版本，只实现了十进制的。
'''
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
9. 桶排序
About The Author
bjmayor
程序员，码农，php,python,ios,android,go，产品经理，创业。