Python 排序演算法範例 ( Sorting Algorithms in Python )

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

前陣子看到真人上演 Sorting Algorithms 的影片：
There are a tutorial video about sorting algorithms:

影片中介紹了Insertion Sort, Selection Sort, Merge Sort, Bubble Sort。筆者就用蟒蛇(Python)來示範這四個排序演算法吧！
The video introduces four sorting algorithms: Insertion Sort, Selection Sort, Merge Sort, Bubble Sort. Let me show you how to implement these algorithms in Python.

插入排序 Insertion Sort:

	import random;
	unsortData = random.sample(range(100), 10)
	def insertion_sort(lst):
	if len(lst) == 1:
	return lst
	for i in range(1, len(lst)):
	temp = lst[i]
	j = i - 1
	while j >= 0 and temp < lst[j]:
	lst[j + 1] = lst[j]
	j -= 1
	lst[j + 1] = temp
	return lst
	print "Original Data:", unsortData
	sortData = insertion_sort(unsortData);
	print "Sorted Data:", sortData

view raw InsertionSort.py hosted with ❤ by GitHub

選擇排序 Selection Sort:

	import random;
	unsortData = random.sample(range(100), 10)
	def selection_sort(L):
	N = len(L)
	exchanges_count = 0
	for i in range(N-1):
	min_index = i
	for j in range(i+1, N):
	if L[min_index] > L[j]:
	min_index = j
	if min_index != i:
	L[min_index], L[i] = L[i], L[min_index]
	exchanges_count += 1
	print('iteration #{}: {}'.format(i, L))
	print('Total {} swappings'.format(exchanges_count))
	return L
	print "Original Data:", unsortData
	sortData = selection_sort(unsortData);
	print "Sorted Data:", sortData

view raw SelectionSort.py hosted with ❤ by GitHub

合併排序 Merge Sort:

	import random
	from collections import deque
	unsortData = random.sample(range(100), 10)
	def merge_sort(lst):
	if len(lst) <= 1:
	return lst
	def merge(left, right):
	merged,left,right = deque(),deque(left),deque(right)
	while left and right:
	merged.append(left.popleft() if left[0] <= right[0] else right.popleft()) # deque popleft is also O(1)
	merged.extend(right if right else left)
	return list(merged)
	middle = int(len(lst) // 2)
	left = merge_sort(lst[:middle])
	right = merge_sort(lst[middle:])
	return merge(left, right)
	print "Original Data:", unsortData
	sortData = merge_sort(unsortData);
	print "Sorted Data:", sortData

view raw MergeSort.py hosted with ❤ by GitHub

泡沫排序 Bubble Sort:

	import random;
	unsortData = random.sample(range(100), 10)
	def bubble_sort(List):
	for j in range(len(List)-1,0,-1):
	flag = True
	for i in range(0, j):
	if List[i] > List[i+1]:
	flag = False
	List[i], List[i+1] = List[i+1], List[i]
	if flag:
	return List
	return List
	print "Original Data:", unsortData
	sortData = bubble_sort(unsortData);
	print "Sorted Data:", sortData

view raw BubbleSort.py hosted with ❤ by GitHub

參考資料：
[1] 插入排序
[2] 選擇排序
[3] 氣泡排序
[4] 合併排序