一、冒泡排序 Bubble Sort
思想: 持续比较相邻元素，大的挪到后面，一次比较之后最后一个元素便是所有元素中最大的
步骤:
- 比较相邻的元素，如果第一个比第二个大，交换二者的位置，
- 对第0到第n-1个数据重复上述步骤，此时最大元素位于n-1处
- 每次对所有非排序元素(位于后面的元素)重复上述步骤，直到没有数字可以用来比较
def bubble_sort(array):
n = len(array)
for i in range(n):
for j in range(1, n-i):
if array[j-1] > array[j]: # if former larger than the latter, swap two elements
array[j-1], array[j] = array[j], array[j-1]
return array
if __name__ == "__main__":
array = [1,4,5,2,11,2,20,9]
sorted_array = bubble_sort(array)
print("after sort:\n", sorted_array)
print("after sort:\n", array)
二、选择排序 Selection Sort
步骤:
- 遍历数组选择其中最小的元素放大数组第一个位置
- 在剩下了的元素中选择最小的元素放在第二个位置，直到没有剩下的元素
import time
import random
def selection_sort(array):
n = len(array)
for i in range(n):
min_index = i # index for min element
for j in range(i+1, n):
if array[j] < array[min_index]:
min_index = j
array[min_index], array[i] = array[i], array[min_index] # swap the current element with the minium element
return array
if __name__ == "__main__":
n = 1000
array = []
for i in range(n):
array.append(random.randint(0, n))
sorted_array = selection_sort(array)
三、插入排序 Insertion Sort
原理: 对于每个未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
步骤:
- 去除第一个元素，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果被扫描的元素（已排序）大于新元素，将该元素后移一位
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
import random
import time
def insertion_sort1(array):
n = len(array)
for i in range(n-1):
temp = array[i+1]
index = i
for j in range(i, -1, -1):
if array[j] > temp:
array[j+1] = array[j]
index = j
else:
break
array[index] = temp
return array
def insertion_sort2(array):
n = len(array)
for i in range(n-1):
if array[i] > array[i+1]:
temp = array[i+1]
index = i
for j in range(i, -1, -1):
if array[j] > temp:
array[j+1] = array[j]
index = j
else:
break
array[index] = temp
return array
if __name__ == "__main__":
n = 1000
array = []
for i in range(n):
array.append(random.randint(0, n))
t0 = time.time()
sorted_array1 = insertion_sort1(array)
t1 = time.time()
print("insertion_sort1 time:", t1 - t0)
t0 = time.time()
sorted_array2 = insertion_sort2(array)
t1 = time.time()
print("insertion_sort2 time:", t1 - t0)
sorted_array = sorted(array, reverse=False) # ascending sorting
assert(sorted_array2 == sorted_array1 == sorted_array)
四、归并排序 Merge Sort
思想: 归并排序是采用分治法的典型算法。先递归分解数组，再合并数组。
先考虑合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
再考虑递归分解，基本思路是将数组分解成left和right，如果这两个数组内部数据是有序的，那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的？可以再二分，直至分解出的小组只含有一个元素时为止，此时认为该小组内部已有序。然后合并排序相邻二个小组即可。
import time
import random
def merge_sort(array):
if len(array) <= 1:
return array
mid = len(array) // 2
left = merge_sort(array[:mid])
right = merge_sort(array[mid:])
return merge(left, right)
def merge(left, right):
l = 0
r = 0
array = []
while(l < len(left) and r < len(right)):
if left[l] < right[r]:
array.append(left[l])
l += 1
else:
array.append(right[r])
r += 1
array += left[l:]
array += right[r:]
return array
if __name__ == "__main__":
n = 10
array = []
for i in range(n):
array.append(random.randint(0, n))
print("Array to sorted:", array)
merge_sorted_array = merge_sort(array)
print("Merge Sorted array:", merge_sorted_array)
sorted_array = sorted(array, reverse=False) # ascending sorting
assert(merge_sorted_array == sorted_array)
五、快速排序 Quick Sort
思想:分而治之
步骤:
- 随机选取一个元素为基准元素
- 所有比基准元素小的置于基准元素左侧，所有比基准元素大的置于基准元素右侧
- 对基准元素左右区间递归调用此过程
import time
import random
def quick_sort(array):
return qsort(array,0,len(array)-1)
def qsort(array,left,right):
if left >= right : return array
key = array[left] # left as key for comparaing
lp = left # left index
rp = right # right index
while lp < rp :
while array[rp] >= key and lp < rp :
rp -= 1
while array[lp] <= key and lp < rp :
lp += 1
print(array[lp])
array[lp],array[rp] = array[rp],array[lp]
print("lp:{0}, rp:{1}".format(lp, rp))
print(array)
array[left],array[lp] = array[lp],array[left]
qsort(array,left,lp-1)
qsort(array,rp+1,right)
return array
def quick_sort2(array):
if len(array) <= 1:
return array
key = array[0]
return quick_sort2([x for x in array[1:] if x < key]) + [key] + quick_sort2([x for x in array[1:] if x >= key])
if __name__ == "__main__":
# n = 10
# array = []
# for i in range(n):
# array.append(random.randint(0, n))
array = [6,5,3,1,8,7,2,4]
print("Array to sorted:", array)
quick_sorted_array = quick_sort(array)
quick_sorted_array2 = quick_sort2(array)
print("Quick Sorted array:", quick_sorted_array)
sorted_array = sorted(array, reverse=False) # ascending sorting
assert(quick_sorted_array == sorted_array == quick_sorted_array2)
六、堆排序
思想: 构建最大二叉堆，然后每次去除最大堆的根节点
步骤:
- 创建最大堆
- 移除位于根节点，做最大堆调整的运算
最主要在如何实现max_heapify()函数来调整最大堆上。
采取自底向上的方式构建最大堆，数组后半部分想象为堆最下面的节点，由于是单个节点故满足二叉堆定义。因此可以从中间节点向前逐步构建二叉堆。
下面这个图说明的很清楚了:
Screen Shot 2019-02-16 at 7.46.38 PM.png
# -*- coding: utf-8 -*-
import time
import heapq
import random
def heap_sort(array):
n = len(array)
first = n // 2 - 1 # the last non leaf node
for start in range(first, -1, -1):
print("enter")
max_heapify(array, start, n-1)
for end in range(n-1,0,-1): # 堆排序，将大根堆转换成有序数组
array[end],array[0] = array[0],array[end]
max_heapify(array, 0, end-1)
return array
def max_heapify(ary, start, end):
"""
最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
start为当前需要调整最大堆的位置，end为调整边界
"""
root = start
while True:
print(root)
child = root*2 + 1 # 调整节点的子节点 对于完全二叉树 左子节点为父节点的2*index + 1
if child > end: break
if child+1 <= end and ary[child] < ary[child+1] : # 如果右子节点大于左子节点
child = child+1 # 取较大的子节点
if ary[root] < ary[child]: # 较大的子节点成为父节点
ary[root], ary[child] = ary[child], ary[root] # 交换
root = child # 交换之后可能会破坏child子树的结构，child子树需要重新遍历
else:
break
def heap_sort2(array):
h = []
for i in array:
heapq.heappush(h, i)
return [heapq.heappop(h) for i in range(len(h))]
if __name__ == "__main__":
n = 10
array = []
for i in range(n):
array.append(random.randint(0, n))
# array = [6,5,3,1,8,7,2,4]
print("Array to sorted:", array)
start = time.time()
heap_sorted_array = heap_sort(array)
end = time.time()
print("Time for heap_sort:", end - start)
start = time.time()
heap_sorted_array2 = heap_sort2(array)
end = time.time()
print("Time for heap_sort using heapq:", end - start)
# print("Heap Sorted array:", heap_sorted_array)
# print("Heap Sorted array2:", heap_sorted_array2)
sorted_array = sorted(array, reverse=False) # ascending sorting
assert(heap_sorted_array == sorted_array)
七、计数排序
思想: 通过对元素进行计数，从而知道元素在已排序元素中应该处于什么位置
步骤:
- 定义计数数组，数组大小为代排序元素中最大元素
- 统计待排序数组中值为i元素的次数，每出现一次在计数数组的i处加一
- 对计数数组进行逐项求和，依次每一项的新值为原始值和它前一项的值之和，这一步是为了确定待排序数组的元素在新数组中的位置
- 将每个元素i放在新数组的C(i)处，每放一个元素C(i)减去1
如输入是:1, 4, 1, 2, 7, 5, 2
计数数组:
index: 0, 1, 2, 3, 4, 5, 6, 7
value: 0, 2, 2, 0, 1, 1, 0, 1
计数数组求和:
index: 0, 1, 2, 3, 4, 5, 6, 7
value: 0, 2, 4, 4, 5, 6, 6, 7
对于输入数组:1, 4, 1, 2, 7, 5, 2
1, 的index为1, 在新数组1处存1, 计数数组在1处减1:[0, 1, 4, 4, 5, 6, 6, 7]
[0, 1, 0, 0, 0, 0, 0, 0]
4, 的index为4, 在新数组5处存4, 计数数组在4处减1:[0, 1, 4, 4, 4, 6, 6, 7]
[0, 1, 0, 0, 0, 4, 0, 0]
...
最后得到:
1, 1, 2, 2, 4, 5, 7
def counting_sort(arr):
max_num = max(arr)
min_num = min(arr)
output = [0 for _ in range(max_num+1)]
count = [0 for _ in range(max_num+1)]
for i in arr:
count[i] += 1
for i in range(1, max_num+1):
count[i] += count[i-1]
for i in arr:
output[count[i]] = i
count[i] -= 1
return output[min_num:]
if __name__ == "__main__":
arr = [1, 4, 1, 2, 7, 5, 2]
print(counting_sort(arr))
八、基数排序
思想: 使用一定的基数把元素的位数按照重要性从小到大排序
步骤:
以常见的10为基数为列:
个位，十位，百位排序...
如:
170, 45, 75, 90, 802, 24, 2, 66
个位排序:
170, 90, 802, 2, 24, 45, 75, 66
十位:
802, 2, 24, 45, 66, 170, 75, 90
百位:
2, 24, 45, 66, 75, 90, 170, 802
"""
implementing counting sort algorithm
@author vincent
2019.2.16
"""
def counting_sort(arr, exp):
n = len(arr)
output = [0]*(n)
count = [0]*(10)
for i in range(0, n):
index = arr[i] // exp
count[index%10] += 1
for i in range(1, 10):
count[i] += count[i-1]
i = n-1
while i > 0:
index = arr[i] / exp
output[ count[ (index)%10 ] - 1] = arr[i]
count[index%10] -= 1
i -= 1
for i in range(0, len(arr)):
arr[i] = output[i]
def radix_sort(arr):
max_num = max(arr)
exp = 1
while max_num/exp > 0:
counting_sort(arr, exp)
exp *= 10
if __name__ == "__main__":
arr = [ 170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print(arr)
- Todo:
九、桶排序
Reference
- http://wuchong.me/blog/2014/02/09/algorithm-sort-summary/
- 常见算法可视化网站，有助于辅助理解: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
- Data Structures and Algorithms in Python GoodRich
