雲林SONG: 5月 2017

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

維基百科上質數的定義為：

「指在大於1的自然數中，除了1和該數自身外，無法被其他自然數整除的數（也可定義為只有1與該數本身兩個因數的數）」

一個著名且有效率的方法：Sieve of Eratosthenes

用 Python 來實現 Sieve of Eratosthenes：

	def eratosthenes(n):
	P = [i for i in range(2, n+1)]
	p = 0
	while True:
	for i in P[p + 1:]:
	if i % P[p] == 0:
	P.remove(i)
	if P[p]**2 >= P[-1]:
	break
	p += 1
	return P

	aNumber = (int)(input("Enter a number:"));

	print (eratosthenes(aNumber))

view raw PrimeNumber.py hosted with ❤ by GitHub

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

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