Python实现 二分查找 冒泡排序 快速排序 插入排序 选择排序 堆排序 与归并排序

  1 # -*- encoding: utf-8 -*-
  2 import random
  3 
  4 
  5 class BinarySearch(object):
  6     @staticmethod
  7     def binary_search(order: list,  target: int, low: int, high: int):
  8         """ 列表长度校验，上下限校验, 列表排序校验(是否有序，升序还是降序) """
  9         # 认为是升序的 , 且参数合法的
 10         middle = (low + high) // 2
 11         if high == low:
 12             return middle + 1 if order[middle] <= target else middle
 13         elif high < low:
 14             return low
 15         else:
 16             if target == order[middle]:
 17                 return middle + 1
 18             elif target > order[middle]:
 19                 return BinarySearch.binary_search(order, target, middle + 1, high)
 20             else:
 21                 return BinarySearch.binary_search(order, target, low, middle - 1)
 22 
 23     @staticmethod
 24     def binary_search_in_loop(order: list, l: int, h: int, t: int):
 25         """ 列表长度校验，上下限校验, 列表排序校验(是否有序，升序还是降序) """
 26 
 27         # 认为是升序的 , 且参数合法的
 28         if t <= order[l]:
 29             return l
 30         if t >= order[h]:
 31             return h + 1
 32 
 33         while l <= h:
 34             middle = (l + h) // 2
 35             # 返回大于等于 t 的索引 ，往该索引 之前插入元素
 36             # 无论是 奇数个 还是 偶数个都会 折半为 偶数个
 37             if t == order[middle]:
 38                 return middle
 39             elif t > order[middle]:
 40                 if middle + 1 <= h and t < order[middle + 1]:
 41                     return middle + 1
 42                 l = middle + 1
 43             else:
 44                 if middle - 1 >= l and t > order[middle - 1]:
 45                     return middle
 46                 h = middle - 1
 47 
 48     @staticmethod
 49     def two_find(x, lis, start=0, end=None):
 50         if end is None:
 51             end = len(lis) - 1
 52         num = (end - start) // 2 + start
 53         if end > start:
 54             if lis[num] > x:
 55                 return BinarySearch.two_find(x, lis, start=start, end=num)
 56             elif lis[num] < x:
 57                 return BinarySearch.two_find(x, lis, start=num + 1, end=end)
 58             elif lis[num] == x:
 59                 return num
 60             elif lis[end] == x:
 61                 return end
 62         else:
 63             return None
 64 
 65 
 66 class BubbleSort(object):
 67 
 68     @staticmethod
 69     def bubble_sort_for(scrambl: list):
 70         list_size = len(scrambl)
 71         finish = False
 72         for i in range(list_size):
 73             if not finish:
 74                 finish = True
 75                 for j in range(list_size - i - 1):
 76                     if scrambl[j] > scrambl[j + 1]:
 77                         scrambl[j], scrambl[j + 1] = scrambl[j + 1], scrambl[j]
 78                         finish = False
 79             else:
 80                 break
 81         return scrambl
 82 
 83     @staticmethod
 84     def bubble_sort_while(scrambl: list):
 85         list_size = len(scrambl)
 86         finish = True
 87         while list_size > 1:
 88             if finish:
 89                 finish = False
 90                 for j in range(list_size - 1):
 91                     if scrambl[j] > scrambl[j + 1]:
 92                         scrambl[j], scrambl[j + 1] = scrambl[j + 1], scrambl[j]
 93                         finish = True
 94             else:
 95                 break
 96             list_size -= 1
 97         return scrambl
 98 
 99 
100 class QuickSort(object):
101     """
102         1-为了便于递归经常选择第一个(倒数第一个也可以）作为中心数据,
103           因为递归过程中递归范围是变动的，从而无法选择其他位置作为中心数据。
104         2-不能保证你最后交换的那个数，是小于等于左边的，这与基准数的位置有关。
105           比如2 1 4 9
106     """
107 
108     @staticmethod
109     def quick_sort(scrambl: list, low: int, high: int):
110         if low > high:
111             return
112         i = low
113         j = high
114         center = scrambl[low]
115         # criterion : n. （批评判断的）标准；准则；规范；准据
116 
117         ‘‘‘
118             【1】 j 向左找，找到小的停下；i 向右找，再碰到 j 之前找到大的；交换值后继续；直到 j 碰到 i，或者 i 碰到 j !
119             【2】 j 向左找，找到小的停下；i 向右找，直到碰到 j 还没找到大的，j 处为小的，将小的移到中心值处，将中心值放到小的处！
120             【3】 j 向左找，直到碰到 i 还没找到小的，i处只能小于等于中心值，因为i处大于中心值，则说明i向前走过，i，
121                   向前走过则应该发生交换，此时 将 i 处值换为中心值，将 i 处的值移动到 中心值处。
122             【4】 核心是 i 左边始终是小的 ，j 的右边始终是大的。
123         ‘‘‘
124 
125         while i < j:  # i != j
126             while i < j and scrambl[j] >= center:
127                 j -= 1
128 
129             while i < j and scrambl[i] <= center:
130                 i += 1
131 
132             if i < j:
133                 scrambl[i], scrambl[j] = scrambl[j], scrambl[i]
134 
135             print(scrambl)
136 
137         # 这种实现方式 最终 i 与 j 肯定位于同一位置。
138         scrambl[low] = scrambl[i]
139         scrambl[i] = center
140         QuickSort.quick_sort(scrambl, low, i - 1)
141         QuickSort.quick_sort(scrambl, i + 1, high)
142 
143     @staticmethod
144     def quick_sort2(scrambl: list, low: int, high: int):
145         i = low
146         j = high
147         center = scrambl[low]
148         ‘‘‘
149             【1】 j 向左找，找到小的；与 i 互换, i 向右找, 找到大的，与 j 互换； 此时 大的将小的重复的覆盖。
150                   继续，循环覆盖，直到 j 碰到 i，或者 i 碰到 j !
151             【2】 j 向左找，找到小的；i 向右找，直到碰到 j 还没找到大的，只好与 j 停于同一个位置，j 处为重复的小的，替换为中心数据
152             【3】 j 向左找，直到碰到 i 还没找到小的，i 处只能大于(重复的大值)等于中心值（没走过），如果小于中心值，
153                   则说明只能为重复的小值，这与 j 找不到小的矛盾。如果不是重复的小值，则说明i走过，走过则i处应为重复的大值。
154             【4】 核心是 i 左边始终是小的 ，j 的右边始终是大的。碰到处 即 i=j 即为中心值
155         ‘‘‘
156         while i < j:
157             while i < j and scrambl[j] >= center:
158                 j -= 1
159             if i < j:
160                 scrambl[i] = scrambl[j]
161                 i += 1
162 
163             while i < j and scrambl[i] <= center:
164                 i += 1
165             if i < j:
166                 scrambl[j] = scrambl[i]
167                 j -= 1
168 
169             print(scrambl)
170 
171         scrambl[i] = center
172 
173         if i - 1 > low:
174             QuickSort.quick_sort2(scrambl, low, i - 1)
175         if j + 1 < high:
176             QuickSort.quick_sort2(scrambl, i + 1, high)
177 
178         # 默认返回None
179 
180 
181 class InsertSort(object):
182     """
183         插入排序对于少量的数据它是一个有效的算法。
184         插入排序的工作方式像人手里的扑克牌一样。
185         开始时我们手里为空并且桌子上的牌面向下。
186         然后我们每次从桌上拿走一张牌并将它插入手里正确的位置。
187         为了把这种牌插入正确的位置，我们要从右到左将它和已在手中的牌进行比较。
188     """
189 
190     @staticmethod
191     def insert_sort_forward(scrambl: list):
192         list_size = len(scrambl)
193         for i in range(1, list_size):  # 一开始手中已经有 1 张牌, 手中的牌都是有序的
194             temp = scrambl[i]  # scrambl[i] :揭起的第 i 张牌
195             for j in range(0, i):  # range(0, i-1) : 手中的 第0张到第i-1张有序牌
196                 if scrambl[j] > temp:  # 正向比较
197                     while i > j:
198                         scrambl[i] = scrambl[i - 1]
199                         i -= 1
200                     scrambl[j] = temp
201                     break
202         return scrambl
203 
204     @staticmethod
205     def insert_sort_backforward(scrambl: list):
206         list_size = len(scrambl)
207         for i in range(1, list_size):
208             end = i - 1
209             temp = scrambl[end]
210 
211             while end >= 0 and scrambl[end] > temp:  # 反向比较
212                 scrambl[end + 1] = scrambl[end]
213                 end -= 1
214 
215             scrambl[end + 1] = temp
216         return scrambl
217 
218     @staticmethod
219     def binary_insert_sort(scrambl):
220         length = len(scrambl)
221         for i in range(1, length):
222             insert_position = BinarySearch.binary_search(scrambl, scrambl[i], 0, i-1)
223             if insert_position == i:
224                 continue
225             else:
226                 insert_value = scrambl[i]
227                 for j in range(i, insert_position, -1):
228                     scrambl[j] = scrambl[j - 1]
229                 scrambl[insert_position] = insert_value
230         return scrambl
231 
232     @staticmethod
233     def shell_sort(scrambl: list):
234         # 希尔排序算法仅仅适用于当线性表为顺序存储的情况， 指针 --> x --> y --> z --> w
235         # The array is divided into multiple subarrays as many as the increment value .
236         increment = len(scrambl) // 2
237         while increment >= 1:
238             for i in range(increment):
239                 for j in range(i + increment, len(scrambl), increment):
240                     inserter = scrambl[j]
241                     compare_index = j
242                     while compare_index >= increment and inserter < scrambl[compare_index - increment]:
243                         scrambl[compare_index] = scrambl[compare_index - increment]
244                         compare_index = compare_index - increment
245                     scrambl[compare_index] = inserter
246             increment //= 2
247         return scrambl
248 
249 
250 class ChooseSort(object):
251 
252     @staticmethod
253     def choose_sort(scrambl: list):
254         list_size = len(scrambl)
255         for i in range(list_size - 1):
256             min_value = scrambl[i]
257             min_index = None
258             for j in range(i + 1, list_size):
259                 if scrambl[j] < min_value:
260                     min_value = scrambl[j]
261                     min_index = j
262             if min_index:
263                 scrambl[i], scrambl[min_index] = scrambl[min_index], scrambl[i]
264         return scrambl
265 
266     @staticmethod
267     def choose_sort2(scrambl: list):
268         list_size = len(scrambl)
269         for i in range(list_size - 1):
270             min_index = i
271             for j in range(i + 1, list_size):
272                 if scrambl[j] < scrambl[min_index]:
273                     min_index = j
274             if min_index > i:
275                 scrambl[i], scrambl[min_index] = scrambl[min_index], scrambl[i]
276         return scrambl
277 
278 
279 class HeapSort(object):
280     # 完全二叉树可以用线性结构表示的树形结构！
281     @staticmethod
282     def heap_sort(scrambl: list):
283         length = len(scrambl)
284         if length < 2:
285             return scrambl
286         for i in range(length//2 - 1, -1, -1):      # shift up
287             HeapSort.adjust_heap(scrambl, i, length)
288 
289         for i in range(length - 1, -1, -1):         # shift down
290             scrambl[0], scrambl[i] = scrambl[i], scrambl[0]
291             HeapSort.adjust_heap(scrambl, 0, i)
292         return scrambl
293 
294     @staticmethod
295     def adjust_heap(scrambl: list, father: int, length: int):
296         lchild = father * 2 + 1
297         rchild = father * 2 + 2
298         maxer = father
299 
300         if rchild < length and scrambl[rchild] > scrambl[maxer]:
301             maxer = rchild
302 
303         if lchild < length and scrambl[lchild] > scrambl[maxer]:
304             maxer = lchild
305 
306         if maxer != father:
307             scrambl[father], scrambl[maxer] = scrambl[maxer], scrambl[father]
308             HeapSort.adjust_heap(scrambl, maxer, length)
309 
310 
311 class MergeSort(object):
312     """
313         归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,
314         该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
315         将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，
316         再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
317     """
318 
319     @staticmethod
320     def merge_sort(scrambl: list, low_start: int, low_end: int, high_start: int, high_end: int):
321         # tmp = [None for i in range(len(scrambl))]
322         # ps: list() will create a empty list, that means you can not index.
323         tmp = [None] * len(scrambl)  # * 对非字面值是浅拷贝
324         ls = index = low_start
325         while low_start <= low_end and high_start <= high_end:
326             if scrambl[low_start] <= scrambl[high_start]:
327                 tmp[index] = scrambl[low_start]
328                 low_start += 1
329                 index += 1
330             else:
331                 tmp[index] = scrambl[high_start]
332                 high_start += 1
333                 index += 1
334         while low_start <= low_end:
335             tmp[index] = scrambl[low_start]
336             low_start += 1
337             index += 1
338         while high_start <= high_end:
339             tmp[index] = scrambl[high_start]
340             high_start += 1
341             index += 1
342         while ls <= high_end:
343             scrambl[ls] = tmp[ls]
344             ls += 1
345 
346     @staticmethod
347     def divide(scrambl: list, low: int, high: int):
348         if low < high:
349             mid = (low + high) // 2
350             MergeSort.divide(scrambl, low, mid)
351             MergeSort.divide(scrambl, mid + 1, high)
352             MergeSort.merge_sort(scrambl, low, mid, mid + 1, high)
353 
354 
355 if __name__ == "__main__":
356     unorder = [random.randint(0, 10) for i in range(10)]
357     print(unorder)
358     """
359     print(BubbleSort.bubble_sort_for(unorder))
360     print(BubbleSort.bubble_sort_while(unorder))
361     a = [3, 9, 6, 1, 5, 4, 0, 8, 7, 2]
362     QuickSort.quick_sort(a, 0, 9)
363     print(a)
364     b = [3, 9, 6, 1, 5, 4, 0, 8, 7, 2]
365     QuickSort.quick_sort2(b, 0, 9)
366     print(b)
367     c = [3, 9, 6, 1, 5, 4, 0, 8, 7, 2]
368     print(InsertSort.insert_sort_forward(c))
369     d = [3, 9, 6, 1, 5, 4, 0, 8, 7, 2]
370     print(ChooseSort.choose_sort2(d))
371     e = [2, 4, 6, 8]
372     print(BubbleSort.bubble_sort_for([4, 3, 5, 2]))
373     MergeSort.divide(unorder, 0, len(unorder) - 1)
374     print(HeapSort.heap_sort(unorder))
375     for i in range(0, 11):                 # 0  1  2  3  4  5
376         print(i, BinarySearch.binary_search([1, 3, 4, 6, 8, 9], i, 0, 5))
377     """
378     print(InsertSort.binary_insert_sort(unorder))
379 
380 
381 # 基本数据结构 --> 高级数据结构 --> 基础算法 --> 高级算法 --> 机器学习算法
382 # chunk it up   |    Deliberate Practicing  |  FeedBack