python 实现十大排序算法
最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
选择排序
选择排序是最稳定的排序了，不管什么情况都是O（n^2）,唯一的优点可能是in-place，想法非常简单，进行n-1趟排序，每次从没排好序的部分选一个最小的元素放到已经排好序的序列的末尾。
代码实现：
def selectSort(array):
'''
选择排序
'''
for i in range(len(array)-1):
maxindex = i
for j in range(i+1,len(array)):
if array[maxindex] > array[j]:
maxindex = j
array[i],array[maxindex] = array[maxindex],array[i]
return array
最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
插入排序
原理：每次将没有排好序列中的第一个插入到前面已经排好序列当中。
代码实现：
def insertion_sort(array):
#插入排序
for i in range(1,len(array)):
cur = array[i]
for j in range(i-1,-1,-1):
if array[j] > cur:
array[j+1] = array[j]
else:
j += 1
break
array[j] = cur
最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
希尔排序
第一个突破O（n^2）的算法，是插入排序的改进版。它与插入排序不同的是它会优先比较距离较远的元素。又被称为缩小增量排序。它的核心在于间隔序列的设定，既可以提前设置好间隔，也可以动态的定义间隔。
算法流程：
选择一个增量序列t1,t2……tk
按增量序列的个数K，对序列进行k趟插入排序
第i趟排序，以ti为间隔构造若干的序列，对这些序列分别进行插入排序。
代码如下:
def shellSort(array):
'''
希尔排序
'''
#构造增量序列 也可以动态构造
l = [5,2,1]
length = len(array)
for i in l:
for j in range(i):
temp = list(range(j,length,i))
#进行插入排序
for x in range(1,len(temp)):
cur = array[temp[x]]
for y in range(x-1,-1,-1):
if array[temp[y]] > cur:
array[temp[y+1]] = array[temp[y]]
else:
y = y + 1
break
array[temp[y]] = cur
最佳情况：T(n) = O(nlog2 n) 最坏情况：T(n) = O(nlog2 n) 平均情况：T(n) =O(nlog n)
归并排序
归并排序比选择排序性能要好很多，最差情况也是O（nlogn）,是使用了分治思想，2-分路，递归
代码如下：
def MergeSort(array):
if len(array) == 0:
return []
elif len(array) == 1:
return array
left = MergeSort(array[0:len(array)//2])
right = MergeSort(array[len(array)//2:])
result = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
while i < len(left):
result.append(left[i])
i += 1
while j < len(right):
result.append(right[j])
j += 1
return result
最佳情况：T(n) = O(n) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)
快速排序
找到一个基准，将比他大的排到它的右侧，比他小的排在左侧，然后分别对两边在进行快速排序，一个递归的过程。
代码实现：
import random
def quickSort(array):
if len(array) <= 1:
return array
#随机生成一个基准
index = random.randint(0,len(array)-1)
basic = array[index]
left = []
right = []
for i in range(0,index):
if array[i] < basic:
left.append(array[i])
else:
right.append(array[i])
for i in range(index+1,len(array)):
if array[i] < basic:
left.append(array[i])
else:
right.append(array[i])
left = quickSort(left)
right = quickSort(right)
result = []
result.extend(left)
result.append(basic)
result.extend(right)
最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)
堆排序
堆排序是完全二叉树，分为大顶堆（上面最大），小顶堆
完全二叉树：除了最后一层外，，每一层都被完全填充
满二叉树：除了叶子结点之外的每一个结点都有两个孩子，每一层(当然包含最后一层)都被完全填充。
完满二叉树：除了叶子结点之外的每一个结点都有两个孩子结点。
首先构建成大顶堆？
首先从最后的一个给叶子节点开始遍历，这个叶子节点如果比左右子节点小的话，就要进行‘’下沉‘’操作（这个过程递归的）
重复上述操作直至根节点，这样就构成了一个大顶堆
排序过程：
首先拿出根节点来，然后将最后一个叶子节点重新作为一个新的根节点，在对新的根节点进行“下沉”操作。
在堆当中，除了‘下沉’操作之外，与之对应的是‘上浮’操作，当插入一个新的节点中使用得到。
Left = 2 * index + 1
Right = 2 * index + 2
最后一个非叶子节点就是**(len(array) – 1)//2**
代码实现：
def Initheapmin(array):
#完全二叉树
#小顶堆
l = len(array)
for i in range((l - 1) // 2,-1,-1):
adjust_heap(array,i)
return array
def adjust_heap(array,i):
l = len(array)
left = 2 * i +1
right = 2 * i + 2
while left < l and right < l:
if array[i] <= array[left] and array[i] <= array[right]:
#满足条件的时候
break
elif array[i] <= array[left]:
#左节点满足，右节点不满足
array[i],array[right] = array[right],array[i]
i = right
elif array[i] <= array[right]:
array[i],array[left] = array[left],array[i]
else:
array[i],array[left] = array[left],array[i]
i = left
left = 2 * i +1
right = 2 * i + 2
if left < l and right >= l:
if array[i] > array[left]:
array[i],array[left] = array[left],array[i]
def heap_sort(array):
array = Initheapmin(array)
result = []
while len(array)>0:
result.append(array[0])
array[0] = array[-1]
del array[-1]
adjust_heap(array,0)
return result
最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)
计数排序
计数排序是一个线性时间内的排序，但是它要还使用一个额外的数组进行统计，它·排序的数组只能是确定范围的，并且它是稳定排序。
过程：
- 找出数据中最大的和最小的数据构建额外开辟的数组空间C内
- 统计
- 反向生成目标数组
-
代码：
def counting_sort(array):
minx = min(array)
maxx = max(array)
c = [0] * (maxx - minx + 1)
for i in array:
c[i - minx] += 1
index = 0
for i in range(len(c)):
for j in range(c[i]):
array[index] = i + minx
index += 1
return array
最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n+k)。
桶排序
桶排序是计数排序的升级版，他利用了函数的映射关系，排序的高效与否在于这个映射关系的选择。
假定数据服从均匀分布。
代码实现：
import math
class ListNode():
def __init__(self,x):
self.val = x
self.next = None
def bucket_sort(array):
minx = min(array)
maxn = max(array)
#构建桶
bucketSize = 5
bucketList = []
for i in range(bucketSize):
head = ListNode(0)
bucketList.append(head)
#利用映射函数将数据添加到各个桶中
group = math.ceil((maxn - minx) // bucketSize)
for data in array:
index = (data - minx) // group
if index >= bucketSize:
index -= 1
bucketList[index].val += 1
if bucketList[index].next == None:
bucketList[index].next = ListNode(data)
else:
pre = bucketList[index]
cur = bucketList[index].next
flag = True
while cur != None:
if data > cur.val:
pre = cur
if cur.next:
cur= cur.next
else:
break
else:
pre.next = ListNode(data)
pre.next.next = cur
flag = False
break
if flag:
cur.next = ListNode(data)
index = 0
for i in range(bucketSize):
cur = bucketList[i].next
while cur:
array[index] = cur.val
cur = cur.next
index += 1
return array
最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n2)
基数排序
基数排序对每一位进行排序，首先取得最大数的位数，然后从最后一位开始，使用计数排序进行排序，之后进行收集，然后在对高位进行上述操作。
代码实现：
def radix_sort(array):
maxn = max(array)
length = len(str(maxn))
for i in range(1,length+1):
print(i)
array = counting_sort(array,i)
return array
def counting_sort(array,l):
c = []
for i in range(10):
c.append([])
for i in array:
if len(str(i)) >= l:
c[int(str(i)[-l])].append(i)
else:
c[0].append(i)
index = 0
for i in range(10):
for j in c[i]:
array[index] = j
index += 1
return array
T(n) = O(n * k) 最差情况：T(n) = O(n * k) 平均情况：T(n) = O(n * k)
最后三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
• 基数排序：根据键值的每位数字来分配桶
• 计数排序：每个桶只存储单一键值
• 桶排序：每个桶存储一定范围的数值
时间空间复杂度
上一篇： Adobe Air应用软件推荐
下一篇： SQL Server2008 自动备份