冒泡排序：?
1 #coding:utf-8 2 ''' 3 比較相鄰的元素，每一趟交換后，最后的元素是最大的。 4 第一次比較n-1次，第二次比較n-2次。。。第n-1次比較1次 5 進行n-1次冒泡次數 6 最優時間復雜度O(n),最壞時間復雜度O(n^2) 7 ''' 8 9 def bubble_sort(b_list): 10 n = len(b_list) 11 for j in range(0, n-1): 12 count = 0 13 for i in range(0, n-1-j): 14 if b_list[i] > b_list[i+1]: 15 count += 1 16 t = b_list[i+1] 17 b_list[i+1] = b_list[i] 18 b_list[i] = t 19 if count == 0: 20 break
?
簡單選擇排序
1 #coding:utf-8 2 ''' 3 找到最小的放到最前面，接著從剩余的繼續找最小的，放到第二個。 4 一共找n-1次，最優O(n^2),最壞O(n^2)，不穩定 5 ''' 6 7 def select_sort(s_list): 8 n = len(s_list) 9 for j in range(0, n-1): 10 min_v = j 11 for i in range(j+1, n): 12 if s_list[i] < s_list[min_v]: 13 min_v = i 14 t = s_list[j] 15 s_list[j] = s_list[min_v] 16 s_list[min_v] = t
?
插入排序
1 #coding:utf-8 2 ''' 3 從第二個開始 和前面的有序序列比較，比較大小插進去 4 最優O(n),最壞O(n^2) 5 ''' 6 7 def insert_sort(i_list): 8 n = len(i_list) 9 for j in range(1, n): 10 i = j 11 while i > 0: 12 if i_list[i] < i_list[i-1]: 13 t = i_list[i] 14 i_list[i] = i_list[i-1] 15 i_list[i-1] = t 16 i = i - 1 17 else: 18 break
?
快速排序
1 #coding:utf-8 2 ''' 3 取第一個數為比較值 4 一個指針左l，一個指針右r，從右邊開始 5 O(nlogn) 6 ''' 7 8 def quick_sort(q_list, left, right): 9 if left >= right: 10 return 11 low = left 12 high = right 13 mid_value = q_list[left] 14 while low < high: 15 while low < high and q_list[high] >= mid_value: 16 high -= 1 17 q_list[low] = q_list[high] 18 while low < high and q_list[low] < mid_value: 19 low += 1 20 q_list[high] = q_list[low] 21 22 q_list[low] = mid_value 23 quick_sort(q_list, left, low - 1) 24 quick_sort(q_list, low + 1, right)
?希爾排序
1 #coding:utf-8 2 ''' 3 O(nlogn) 4 ''' 5 6 def shell_sort(s_list): 7 n= len(s_list) 8 gap = n // 2 9 while gap > 0: 10 for j in range(gap, n): 11 i = j 12 while i > gap - 1: 13 if s_list[i] < s_list[i-gap]: 14 s_list[i-gap],s_list[i] = s_list[i],s_list[i-gap] 15 i -= gap 16 else: 17 break 18 gap = gap // 2
?
)
)
