def insert_sort(ary):
""" 插入法排序 """
""" 算法复杂度O(n平方)"""
""" 始终保证A[0,i]是有序的 """
""" 依次插入值,如果插入的值比左边的小,依次往左移动直至合适位置 """
sort_ary = [0 for i in range(len(ary))]
for i in range(len(ary)):
sort_ary[i] = ary[i]
for j in range(i, 0, -1):
if sort_ary[j] < sort_ary[j - 1]:
tmp = sort_ary[j - 1]
sort_ary[j - 1] = sort_ary[j]
sort_ary[j] = tmp
for i in range(len(sort_ary)):
ary[i] = sort_ary[i]
def median_sort(ary):
""" 中值法排序 """
""" 算法复杂度O(nlog(n)) """
""" 递归,分治思想 """
""" 找到中值元素,比中值小的放左边,大于或者等于中值的放右边 """
""" 递归中值左右子数组 """
median_sort_internal(ary, 0, len(ary) - 1)
def median_sort_internal(ary, left, right):
""" 递归函数 """
if right <= left:
return
else:
mid = (right - left + 1) / 2
select_kth(ary, left, right, mid)
median_sort_internal(ary, left, left + mid - 1)
median_sort_internal(ary, left + mid + 1, right)
def select_kth(ary, left, right, k):
""" 选择第k大的元素,并分区 """
idx = left
index = partition(ary, left, right, idx)
if (left + k) - 1 == index:
return index
else:
if (left + k - 1) < index:
return select_kth(ary, left, index - 1, k)
else:
return select_kth(ary, index + 1, right, k - (index - left + 1))
def partition(ary, left, right, index):
""" 分块函数,并返回index对应值在分块完成的下标 """
store = left
value = ary[index]
tmp = ary[right]
ary[right] = value
ary[index] = tmp
for i in range(left, right, +1):
if ary[i] < value:
tmp = ary[i]
ary[i] = ary[store]
ary[store] = tmp
store = store + 1
ary[right] = ary[store]
ary[store] = value
return store
def quick_sort(ary, left, right):
""" 快速排序 """
""" 快速排序和中值排序的方法几乎一样,区别在于快速排序可以随机选择枢纽值,而不是选择中值 """
if (left >= right):
return
""" 选择最右边的为枢纽值 """
key = ary[right]
i = left
j = left
for i in xrange(left, right):
if (ary[i] < key):
tmp = ary[i]
ary[i] = ary[j]
ary[j] = tmp
j = j + 1
tmp = ary[j]
ary[j] = key
ary[right] = tmp
quick_sort(ary, left, j - 1)
quick_sort(ary, j + 1, right)
def bubble_sort(ary):
""" 冒泡排序 """
""" 时间复杂度O(n平方) """
""" 如其名,像气泡一样网上冒 """
""" 如果a[i]大于a[i+1],则交换.需要进行n-1次扫描. """
""" 第一次扫描把最大值放到最后,第二次把第二大的值放到最大值前门,依次类推 """
length = len(ary)
for i in range(length - 1, -1, -1):
for j in range(i):
if ary[j] > ary[j + 1]:
tmp = ary[j]
ary[j] = ary[j + 1]
ary[j + 1] = tmp
def select_sort(ary):
""" 选择排序 """
""" 时间复杂度O(n平方) """
""" 不停选择最大值往最后放,先选完再交换 """
for i in range(len(ary)):
index = select_max(ary, len(ary) - i)
tmp = ary[len(ary) - i - 1]
ary[len(ary) - i - 1] = ary[index]
ary[index] = tmp
def select_max(ary, length):
""" 选择最大值,返回下标 """
max = ary[length - 1]
index = length - 1
for i in range(length):
if max < ary[i]:
max = ary[i]
index = i
return index
def heap_sort(ary):
""" 堆排序 """
""" 时间复杂度O(nlogn),最坏情况也是n(nlogn) """
""" 可以把堆当做完全二叉树 """
""" 利用堆的性质,不停添加有序区域,直至全部有序. """
""" 1. 构造大顶堆 """
""" 2. 取出根元素和最后一个元素互换. """
""" 3. 重复执行以上过程 """
build_heap(ary)
length = len(ary)
for i in range(length - 1, -1, -1):
tmp = ary[0]
ary[0] = ary[i]
ary[i] = tmp
""" 大根堆根顶元素互换,然后重新构造大根堆 """
heapify(ary, 0, i)
def build_heap(ary):
""" 初始化堆,从无序堆到大根堆 """
""" 假设完全二叉树的层级为n,从n-1层开始构造子大根堆,逐渐递减n.直到n为0. """
length = len(ary) / 2 - 1
for i in range(length, -1, -1):
heapify(ary, i, len(ary))
def heapify(ary, idx, max_len):
""" 调整堆 """
left = 2 * idx + 1
right = 2 * idx + 2
largest = idx
if left < max_len and ary[left] > ary[idx]:
largest = left
if right < max_len and ary[right] > ary[largest]:
largest = right
if not largest == idx:
tmp = ary[idx]
ary[idx] = ary[largest]
ary[largest] = tmp
heapify(ary, largest, max_len)
def counting_sort(ary):
""" 计数排序 """
""" 非比较排序,时间复杂度为线性. """
""" 适合于排序n个元素,元素的取值为[0, k],n远大于k """
k = ary[0]
for i in range(len(ary)):
if ary[i] > k:
k = ary[i]
k_ary = [0 for i in range(k + 1)]
tmp = 0
for i in range(len(ary)):
k_ary[ary[i]] += 1
for i in range(len(k_ary)):
if k_ary[i] > 0:
for j in range(k_ary[i]):
ary[tmp] = i
tmp += 1
def bucket_sort(ary):
""" 桶排序 """
""" 跟计数排序类似 """
""" 使用hash函数均匀的将n个元素分散到k个桶中,桶必须是有序的,i-1桶中的元素一定都要比i桶中的元素小 """
""" 每个桶使用插入排序 """
k = ary[0]
for i in range(len(ary)):
if ary[i] > k:
k = ary[i]
""" hash(x) = x / 3 """
bucket_ary = [[] for i in range(k / 3 + 1)]
for i in range(len(ary)):
index = ary[i] / 3
bucket_ary[index].append(ary[i])
tmp = 0
for i in range(len(bucket_ary)):
insert_sort(bucket_ary[i])
for j in range(len(bucket_ary[i])):
ary[tmp] = bucket_ary[i][j]
tmp += 1
ARRAY = [2, 5, 6, 8, 1, 3, 4, 2, 9, 7]
insert_sort(ARRAY)
print ARRAY
ARRAY = [2, 5, 6, 8, 1, 3, 4, 2, 9, 7]
quick_sort(ARRAY, 0, len(ARRAY) - 1)
print ARRAY
ARRAY = [2, 5, 6, 8, 1, 3, 4, 2, 9, 7]
median_sort(ARRAY)
print ARRAY
ARRAY = [2, 5, 6, 8, 1, 3, 4, 2, 9, 7]
select_sort(ARRAY)
print ARRAY
ARRAY = [2, 5, 6, 8, 1, 3, 4, 2, 9, 7]
bubble_sort(ARRAY)
print ARRAY
ARRAY = [2, 5, 6, 8, 1, 3, 4, 2, 9, 7]
heap_sort(ARRAY)
print ARRAY
ARRAY = [2, 5, 6, 8, 1, 3, 4, 2, 9, 7]
counting_sort(ARRAY)
print ARRAY
ARRAY = [2, 5, 6, 8, 1, 3, 4, 2, 9, 7]
bucket_sort(ARRAY)
print ARRAY