四川有什么好的网站建设公司,定制做网站服务,我的家乡ppt模板免费下载,广东圆心网站开发顶先最后推荐#xff1a;哈哈#xff0c;意思是放到顶部强调其重要性#xff0c;但是应该我总结的六种算法看完了后再看的一篇醍醐灌顶的文章 一#xff1a;冒泡排序#xff08;Bubble Sort#xff09; 原理#xff1a;假设有n个数#xff0c;第一轮时#xff1a;从第… 顶先最后推荐哈哈意思是放到顶部强调其重要性但是应该我总结的六种算法看完了后再看的一篇醍醐灌顶的文章 一冒泡排序Bubble Sort 原理假设有n个数第一轮时从第一个元素开始与相邻的元素比较如果前面的元素小就交换直到第n-1个元素时这样的结果是将最大的元素放到了最后同理第二轮还是从第一个元素开始比较直到第n-2个元素这样能够把剩下的n-1个数中的最大的数放到第n-1的位置一直这样进行n-1轮就能够完成排序。 1 def Bublesort(seq):2 i 03 j 04 while i len(seq):5 while j len(seq)-i-1:6 if seq[j] seq[j1]:7 seq[j],seq[j1] seq[j1],seq[j]8 else:9 j1
10 j0
11 i1
12
13 a[3,4,6,2,1]
14 Bublesort(a)
15 print(a) 冒泡排序 由代码可知其时间复杂度为O(n2). 二选择排序Selection Sort 原理选择排序的思路非常简单每次都遍历找出上次剩下的元素中的最大数然后和剩下数中随后一个元素交换位置一个进行n-1次 1 #coding:utf-82 #Attention:max标志需取为seq[0]我刚开始取了0这会导致最后一次比较时出问题3 def SelectionSort(seq):4 i,j,maxel 0,0,seq[0]5 while i len(seq):6 while j len(seq)-i:7 if seq[j] maxel:8 maxel j9 j1
10 seq[maxel],seq[len(seq)-i-1] seq[len(seq)-i-1],seq[maxel]
11 j,maxel0,seq[0]
12 i1
13
14 a[3,4,6,2,1]
15 SelectionSort(a)
16 print(a) 选择排序 可以看出的是其时间复杂度依然是O(n2),看起来和冒泡排序一样但由于每轮其交换位置的次数少故实际上其比冒泡排序好。 三插入排序Insertion Sort 原理如下图所示将第一个元素作为标准每次将下一个元素放到前面正确的位置中去。 技巧从已排好序元素最后一个开始遍历比较因为插入移动只会移动其后面的元素。 1 def insertion_sort(a_list):2 for index in range(1, len(a_list)):3 current_value a_list[index]4 position index5 while position 0 and a_list[position - 1] current_value: #从目前元素开始向前若目前值就后移一位6 a_list[position] a_list[position - 1]7 position position - 18 a_list[position] current_value9
10 a [54, 26, 93, 17, 77, 31, 44, 55, 20]
11 insertion_sort(a)
12 print(a) 插入排序 依旧可以看出的是其时间复杂度为O(n2)但是他的不同之处在于其始终保持了一个部分有序的序列 四希尔排序Shell Sort 希尔排序这章书里面的配图不好导致我理解错误直到运行程序出错才发现错误后来看了些其他资料弄明白了。其实希尔排序就是跳跃式插入排序我们试想一下如果一个元素集是987654321那么每次插入排序都要全部后移了这样效率极低如果能够不按顺序的进行插入排序就好多了虽然每次并没有完全排好序但是能够让他们离真实的位置更近这就是其优势所在了。 实现原理每次取一个gap第一次取集合元素个数整除2的结果然后对从首元素开始每gap距离的元素组合成一个组并对其进行插入排序假设集合[54, 26, 93, 17, 77, 31, 44, 55, 20]那么第一次gap为9//24那么就能够有这些组[54,77,20],[26,31],[93,44],[17,55],注意并不是对其真的分组只是将其看作一组后进行插入排序那么结果是[20, 26, 44, 17, 54, 31, 93, 55, 77],到此第一次完成。第二次把gap改为上次gap//2的结果也就是2所以对上次的结果分组为[20,44,54,93,77],[26,17,31,55],对其进行插入排序后的结果是[20, 17, 44, 26, 54, 31, 77, 55, 93]到此第二次完成。第三次gap为1注意当gap为1时就表明是最后一轮了最上此结果[20, 17, 44, 26, 54, 31, 77, 55, 93]全部进行插入排序就能够得到结果了。【仔细看看就能够发现其每次排序后真的是数字离其真实位置更近了】。 注意有个控制循环的条件就是每次分组的组数其实就是gap的值容易看出是两层控制外层控制进入的哪组分组内层控制具体每组的插入排序 1 def shell_sort(a_list):2 sublist_count len(a_list) // 23 while sublist_count 0:4 for start_position in range(sublist_count):5 gap_insertion_sort(a_list, start_position, sublist_count)6 print(After increments of size, sublist_count, The list is,a_list)7 sublist_count sublist_count // 28 9 def gap_insertion_sort(a_list,start, gap):
10 for i in range(start gap, len(a_list), gap):
11 current_value a_list[i]
12 position i
13 while position gap and a_list[position - gap] current_value:
14 a_list[position] a_list[position - gap]
15 position position - gap
16 a_list[position] current_value
17
18 a_list [54, 26, 93, 17, 77, 31, 44, 55, 20]
19 shell_sort(a_list)
20 print(a_list) 希尔排序 五:归并排序Merge Sort 原理图由图可以看出其也是用了递归原理base就是只剩一个元素时返回其本身 1 def partition(seq, start, mid, stop):2 lst []3 i start4 j mid5 while i mid and j stop:6 if seq[i] seq[j]:7 lst.append(seq[i])8 i19 else:
10 lst.append(seq[j])
11 j1
12 while i mid:
13 lst.append(seq[i])
14 i1
15 while j stop:
16 lst.append(seq[j])
17 j1
18 for i in range(len(lst)):
19 seq[starti]lst[i]
20
21 def mergeSortRecursively(seq, start, stop):
22 if start stop-1:
23 return
24 mid (start stop) // 2
25 mergeSortRecursively(seq, start, mid)
26 mergeSortRecursively(seq, mid, stop)
27 partition(seq, start, mid, stop)
28
29 a[3,4,6,8,2,1,5,9]
30 mergeSortRecursively(a, 0, len(a))
31 print(a) 归并排序 来分析下其时间复杂度吧由于每次都将list二分这是logn而每次排列是n由于这两小步组成一步故时间复杂度为O(nlogn) 六快速排序Quick Sort 原理如下第一次以第一个元素为标志将后面小的放他左边大的放他右边而后将其放到中间。第二次分别在其两边重复这样的过程最后直到每组只有一个数据。 有个需要注意的是最坏情况下为以排好序的集合那么后面的数都标志大或者小操作太多或者无效最理想的是标志能够是平均值左右故最好对数据进行随机化处理。 还有看完代码后注意比较可以是快速排序与归并排序是某种程度相反的归并到了最后两个元素才开始排序从部分有序积累到全部有序而二分是反的从第一次二分就是整个数列的二分最后二分到只有两个元素时此时完成了全部有序。 1 import random2 def partition(seq, start, stop):3 pivotIndex start4 pivot seq[pivotIndex]5 i start16 j stop-1 7 while i j:8 while pivot seq[i]:9 i1
10 while pivot seq[j]:
11 j-1
12 if i j:
13 seq[j],seq[i] seq[i],seq[j]
14 i1
15 j-1
16 seq[pivotIndex],seq[j] seq[j],pivot
17 return j
18
19 def quicksortRecursively(seq, start, stop):
20 if start stop-1:
21 return
22 pivotIndex partition(seq, start, stop)
23 quicksortRecursively(seq, start, pivotIndex)
24 quicksortRecursively(seq, pivotIndex1, stop)
25
26 def quicksort(seq):
27 # randomize the sequence first
28 for i in range(len(seq)):
29 j random.randint(0,len(seq)-1)
30 seq[i],seq[j] seq[j],seq[i]
31
32 quicksortRecursively(seq, 0, len(seq))
33
34 a[3,4,6,8,2,1,5,9]
35 quicksort(a)
36 print(a) 快速排序 同理可以分析出其时间复杂度为O(nlogn) 转载于:https://www.cnblogs.com/pengsixiong/p/5323772.html
