• 研究了一下冒泡排序，官方写法是下面这样 list_num = ['0', '0', '1', '1', '2', '2', '3', '3', '4', '4', '5', '5', '6', '6', '7', '7', '8', '8', '9', '9'] print(list_num) a = 0 b = 0 length = len(....
测试排序一个length = 20的列表

研究了一下冒泡排序，官方的写法是下面这样的

list_num = ['0', '0', '1', '1', '2', '2', '3', '3', '4', '4', '5', '5', '6', '6', '7', '7', '8', '8', '9', '9']

print(list_num)
a = 0
b = 0
length = len(list_num) - 1
while length > 0:
a += 1
for i in range(length):
b += 1
if list_num[i] > list_num[i + 1]:
list_num[i], list_num[i + 1] = list_num[i + 1], list_num[i]
length -= 1
print(list_num)
print(a, b)

结果输出：
['0', '0', '1', '1', '2', '2', '3', '3', '4', '4', '5', '5', '6', '6', '7', '7', '8', '8', '9', '9']
['0', '0', '1', '1', '2', '2', '3', '3', '4', '4', '5', '5', '6', '6', '7', '7', '8', '8', '9', '9']
19 190

更多标准排序结果：
['3', '4', '5', '2', '0', '1', '7', '7', '6', '8', '2', '6', '9', '0', '1', '5', '9', '4', '8', '3']
['0', '0', '1', '1', '2', '2', '3', '3', '4', '4', '5', '5', '6', '6', '7', '7', '8', '8', '9', '9']
19 190

['0', '2', '2', '7', '7', '9', '1', '8', '9', '5', '3', '4', '6', '5', '8', '4', '1', '3', '6', '0']
['0', '0', '1', '1', '2', '2', '3', '3', '4', '4', '5', '5', '6', '6', '7', '7', '8', '8', '9', '9']
19 190

['6', '9', '7', '1', '5', '1', '0', '9', '5', '0', '4', '2', '8', '7', '8', '3', '6', '3', '2', '4']
['0', '0', '1', '1', '2', '2', '3', '3', '4', '4', '5', '5', '6', '6', '7', '7', '8', '8', '9', '9']
19 190

这里我做了一个简单的测试，代码中的列表是已经排好序的，无奈冒泡排序仍然for循环19次 ，进行190次比较才得出预期的值

经过大量运行可以发现上面这种冒牌排序，不论什么列表，结果都是一样，for循环19次，比较190次，显然存在大量无效运算

我自己写了一种优化后的冒泡排序，可以快速高效的完成排序，最少一遍for 循环就能完成排序

下面是我的优化后的冒泡排序写法：

list_num = ['0', '0', '1', '1', '2', '2', '3', '3', '4', '4', '5', '5', '6', '6', '7', '7', '8', '8', '9', '9']
print(list_num)
boolean = True
i = 0
a = 0
length = len(list_num) - 1

while boolean:
boolean = False
i += 1
for b in range(length):
a += 1
if list_num[b] > list_num[b + 1]:
list_num[b], list_num[b + 1] = list_num[b + 1], list_num[b]
boolean = True
elif not boolean:
boolean = False
length -= 1

print(list_num)
print(i, a)

运行结果：
['0', '0', '1', '1', '2', '2', '3', '3', '4', '4', '5', '5', '6', '6', '7', '7', '8', '8', '9', '9']
['0', '0', '1', '1', '2', '2', '3', '3', '4', '4', '5', '5', '6', '6', '7', '7', '8', '8', '9', '9']
1 19

更多优化排序结果：
['4', '3', '4', '5', '3', '1', '2', '2', '7', '1', '8', '5', '8', '0', '9', '7', '6', '6', '0', '9']
['0', '0', '1', '1', '2', '2', '3', '3', '4', '4', '5', '5', '6', '6', '7', '7', '8', '8', '9', '9']
18 189

['2', '5', '1', '3', '8', '7', '0', '3', '9', '6', '0', '7', '8', '1', '4', '4', '6', '2', '5', '9']
['0', '0', '1', '1', '2', '2', '3', '3', '4', '4', '5', '5', '6', '6', '7', '7', '8', '8', '9', '9']
13 169

['2', '5', '0', '8', '7', '1', '9', '7', '3', '8', '4', '6', '1', '4', '0', '2', '3', '9', '6', '5']
['0', '0', '1', '1', '2', '2', '3', '3', '4', '4', '5', '5', '6', '6', '7', '7', '8', '8', '9', '9']
14 175



展开全文
• 冒泡排序重复地走访需要排序的元素列表，依次比较两个相邻的元素，如果顺序(如从大到小或从小到大)错误就交换它们的位置。重复地进行直到没有相邻的元素需要交换，则元素列表排序完成。在冒泡排序中，值最大(或最小)...
一、冒泡排序简介冒泡排序(Bubble Sort)是一种常见的排序算法，相对来说比较简单。冒泡排序重复地走访需要排序的元素列表，依次比较两个相邻的元素，如果顺序(如从大到小或从小到大)错误就交换它们的位置。重复地进行直到没有相邻的元素需要交换，则元素列表排序完成。在冒泡排序中，值最大(或最小)的元素会通过交换慢慢“浮”到元素列表的“顶端”。就像“冒泡”一样，所以被称为冒泡排序。二、冒泡排序原理冒泡排序的原理如下：1. 比较相邻的两个元素。如果第一个比第二个大则交换他们的位置(升序排列，降序则反过来)。2. 从列表的开始一直到结尾，依次对每一对相邻元素都进行比较。这样，值最大的元素就通过交换“冒泡”到了列表的结尾，完成第一轮“冒泡”。3. 重复上一步，继续从列表开头依次对相邻元素进行比较。已经“冒泡”出来的元素不用比较(一直比较到结尾也可以，已经“冒泡”到后面的元素即使比较也不需要交换，不比较可以减少步骤)。4. 继续从列表开始进行比较，每轮比较会有一个元素“冒泡”成功。每轮需要比较的元素个数会递减，一直到只剩一个元素没有“冒泡”时(没有任何一对元素需要比较)，则列表排序完成。以列表 [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] 进行升序排列为例。列表的初始状态如下图。要进行升序排列，则大的元素要依次“冒泡”到列表的结尾。1. 从列表的开头，比较相邻的两个元素，如果第一个值比第二个值大则交换。10小于17，不需要交换。2. 向列表的结尾方向“走访”，比较第二组相邻的元素(第二个和第三个)，如果不是从小到大则交换。17小于50，不需要交换。3. 继续“走访”，比较第三组相邻的元素，如果不是从小到大则交换。50大于7，所以需要交换。4. 对顺序错误的元素进行位置交换。交换50和7的位置。5. 一直“走访”到结尾，第一轮“冒泡”结束后，值最大的元素“冒泡”到了列表的结尾。50“冒泡”到了列表结尾。在下一轮“冒泡”中，不需要再将50进行比较，需要比较的元素个数减1。6. 从列表开头，重复下一轮“冒泡”，每进行一轮“冒泡”，需要比较的元素都少一个，直到没有元素对需要比较时，整个列表排序完成。排序结果如下图。三、Python实现冒泡排序# coding=utf-8def bubble_sort(array):for i in range(1, len(array)):for j in range(0, len(array)-i):if array[j] > array[j+1]:array[j], array[j+1] = array[j+1], array[j]return arrayif __name__ == '__main__':array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]print(bubble_sort(array))运行结果：[5, 7, 10, 15, 17, 21, 24, 27, 30, 36, 45, 50]代码中，i 表示第几轮“冒泡”，j 表示“走访”到的元素索引。每一轮“冒泡”中，j 需要从列表开头“走访”到 len(array) – i 的位置。四、冒泡排序的时间复杂度和稳定性1. 时间复杂度在没有特殊说明时，一般都是计算最坏时间复杂度。在冒泡排序中，最坏的情况是元素列表的初始状态是完全逆序排列的，需要进行 n-1 轮“冒泡”，每一轮“冒泡”需要进行 n-i 次比较和交换操作。i 的平均值为 n/2 ，时间复杂度为 T(n)=n(n-1)/2 ，再乘每次操作的步骤数(常数，不影响大O记法)，所以冒泡排序的时间复杂度为 O(n^2) 。2. 稳定性排序算法的稳定性指，当元素列表中有相等的元素时，相等元素的相对次序是否固定不变，如果相对次序固定不变，则排序算法是稳定的，反之。在冒泡排序中，每次比较两个元素，当元素的大小顺序错误时才会进行交换，如果元素列表中有两个相等的元素，它们最终肯定会相邻在一起，但对它们比较时不会进行交换，相对次序是保持不变的。所以冒泡排序是一种稳定的排序算法。冒泡排序优化：将时间复杂度降为O(n)def bublle_sort(alist):"""冒泡排序"""n = len(alist)for j in range(n-1):count = 0for i in range(0, n-1-j):#从头走到为if alist[i]>alist[i+1]:alist[i],alist[i+1] = alist[i+1],alist[i]count +=1if 0 == count:breakif __name__ == "__main__":li = [54,25,93,17,77,31,44,55,20,10]print(li)bublle_sort(li)print(li)如有失效，请留言告知丨转载请注明原文链接：Python冒泡排序及优化
展开全文
• 1.冒泡排序(从大到小)：交换发生在内部循环稳定的排序冒泡排序的平均时间复杂度是O(n2),最好的时间复杂度是O(n),最坏的时间复杂度是O(n2)，空间复杂度为O(1)冒泡排序的优化在于didswap变量 ，通过这个变量的设置，...
1.冒泡排序(从大到小)：交换发生在内部循环稳定的排序冒泡排序的平均时间复杂度是O(n2),最好的时间复杂度是O(n),最坏的时间复杂度是O(n2)，空间复杂度为O(1)冒泡排序的优化在于didswap变量 ，通过这个变量的设置，实现冒泡排序的最好时间复杂度是O(n)#!usr/bin/pythonarr=[1,2,3,4,5,6,7,8,67,5,64,43,546,56,76,34,657,34,45,56,23]def BubbleSort(list):for i in range(len(list)-1):didswap = Falsefor j in range(len(list)-1-i):if list[j]list[j],list[j+1]=list[j+1],list[j]didswap =Trueif didswap == False:return listreturn listprint (BubbleSort(arr))2.选择排序(从大到小)：交换发生在外部循环不稳定的排序平均算法复杂度O(n2),最好算法复杂度O(n2),最坏的算法复杂度为O(n2),空间复杂度O(1)#!usr/bin/pythondefSelectSort(lists):for i in range(len(lists)-1):max=ifor j in range(i+1,len(lists)):if lists[j]>lists[max]:max=jlists[max],lists[i]=lists[i],lists[max]returnlistslists=[2,3,4,65,7,6,5,5,6,7,8,6,4]print SelectSort(lists)3.插入排序(从大到小排序)：稳定的排序平均复杂度O(n2),最好的时间复杂度O(n),最坏的算法复杂度O(n2),空间复杂度是O(1)#!usr/bin/pythondefInsertSort(lists):for i in range(1,len(lists)):key=lists[i]j=i-1while j>=0 and lists[j]lists[j+1]=lists[j]j=j-1lists[j+1]=keyreturnlistsarr=[2,3,4,5,6,8,7,5,6,7,6,4,5,6,7,8,7,5]print InsertSort(arr)4.归并排序(从大到小)：归并排序的思想就是分而治之归并排序是稳定平均O(nlgn) 最好的时间复杂度是O(nlgn),最坏的时间复杂度是O(nlgn),空间复杂度是O(n)#!usr/bin/pythondefMerge(left,right):i,j=0,0result=[]while i=right[j]:result.append(left[i])i+=1else:result.append(right[j])j+=1result+=left[i:]result+=right[j:]returnresultdefMergeSort(lists):if len(lists)<2:returnlistsdiv= len(lists)/2left=MergeSort(lists[0:div])right=MergeSort(lists[div:])returnMerge(left,right)lists= [2,3,4,5,6,7,6,5,34,23,4,56,6,3,4,6]print MergeSort(lists)5.快速排序：(递归调用)平均时间复杂度O(nlgn),平均时间复杂度O(nlgn),最坏的时间复杂度O(n2)空间复杂度O(lgn)-Olg(n)def QuickSort(myList,start,end):#判断low是否小于high,如果为false,直接返回if start < end:i,j = start,end#设置基准数base = myList[i]while i < j:#如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现while (i < j) and (myList[j] >= base):j = j - 1#如找到,则把第j个元素赋值给第个元素i,此时表中i,j个元素相等myList[i] = myList[j]#同样的方式比较前半区while (i < j) and (myList[i] <= base):i = i + 1myList[j] = myList[i]#做完第一轮比较之后,列表被分成了两个半区,并且i=j,需要将这个数设置回basemyList[i] = base#递归前后半区QuickSort(myList, start, i - 1)QuickSort(myList, j + 1, end)return myListlists = [49,38,65,97,76,13,27,49]print(QuickSort(lists,0,len(lists)-1))print (lists)7.堆排序(从大到小)：第一步最小堆化；第二步建立最小堆；第三步堆排序#!user/bin/pythondefAjustHeap(lists,i,size):min=ileft=2*i+1right=2*i+2if i < size/2:if right < size and lists[min] >lists[right]:min=rightif left < size and lists[min]>lists[left]:min=leftif min!=i:lists[i],lists[min]=lists[min],lists[i]AjustHeap(lists,min,size)defBuildHeap(lists,size):for i in range(0,(size/2))[::-1]:AjustHeap(lists,i,size)defHeapSort(lists):size=len(lists)BuildHeap(lists,size)for i in range(0,size)[::-1]:lists[i],lists[0]=lists[0],lists[i]AjustHeap(lists,0,i)returnlistsarr=[12,23,4,3,5,6,7,8,76,43,5,6,7,34,3,76]print HeapSort(arr)6.希尔排序(从大到小)：(插入排序的一种)#!user/bin/pythondefShellSort(lists):step=len(lists)/2while (step>=1):#step终止循环为1for i in range(step,len(lists)):#没一次step对应很多个新列表while(i>=step and lists[i] > lists[i-step]):#每个列表进行排序lists[i],lists[i-step]=lists[i-step],lists[i]i=i-stepstep=step/2returnlistsarr=[12,23,4,3,5,6,7,8,76,43,5,6,7,34,3,76]print ShellSort(arr)8.计数排序：
展开全文
• 我对Python相当陌生，我将从...我建议第一个选项是优化冒泡排序，但第二个选项有问题。在维基百科中，这个“允许我们跳过很多元素，结果在最坏情况下，比较计数提高了大约50%”。所以我第一个选项代码看起来...
我对Python相当陌生，我将从排序算法、PEP8和Python的Zen开始我的旅程。我刚在CodeReview上写了一篇帖子。我做了修复，我想问一下Optimizing Bubble Sort : Second option。我建议第一个选项是优化冒泡排序，但第二个选项有问题。在维基百科中，这个“允许我们跳过很多元素，结果在最坏的情况下，比较计数提高了大约50%”。所以我的第一个选项的代码看起来和工作原理一样：def bubble_sort(container):"""Bubble sort with optimization.Description----------Performance cases:Worst      : O(n^2)Average    : O(n^2)Best case  : O(n)Parameters----------data_container : Mutable structure with comparable objects and structurewhich has implemented __len__, __getitem__ and __setitem__.Returns-------NoneExamples---------->>> bubble_sort([7,1,2,6,4,2,3])[1, 2, 2, 3, 4, 6, 7]>>> bubble_sort(['a', 'c', 'b'])['a', 'b', 'c']"""# setting up variableslength = len(container)changed = Truewhile changed:changed = Falsefor i in range(length - 1):if container[i] > container[i + 1]:container[i], container[i + 1] = container[i + 1], container[i]changed = Truelength -= 1问题是为了实现第二个优化选项，我必须做些什么改变。另外，到目前为止，我还试着表现得像伪代码一样。我的代码不工作(不分类)，看起来像：^{pr2}\$
展开全文
• Python 算法 08 -- 冒泡排序及其优化-1.jpg (93.27 KB, 下载次数: 0)2020-11-6 21:31 上传Python 算法 08 -- 冒泡排序及其优化-2.jpg (56...[5,4,3,2,1]要求：按从小到大的顺序排序2、分析● 冒泡排序的思路两两比较...
• Python冒泡排序优化、选择排序、插入排序及优化 1. 冒泡排序 def bubble_sort(alist): '''冒泡排序''' for i in range(len(alist)-1, 0, -1): # i表示每次遍历需要比较次数，逐渐减小 for j in range...
• 本文地址:http://www.04007.cn/article/647.html冒泡排序是常见的一个排序法，经过一轮轮相邻两两比较，每次将当前轮的最大值排到...冒泡排序的PHP实现如下示例： a.php：本文地址:http://www.04007.cn/article/647....
• 1.冒泡排序(从大到小)：交换发生在内部循环稳定的排序冒泡排序的平均时间复杂度是O(n2),最好的时间复杂度是O(n),最坏的时间复杂度是O(n2)，空间复杂度为O(1)冒泡排序的优化在于didswap变量 ，通过这个变量的设置，...
• 冒泡排序处理数据原本有序 “”" li = [11,22,44,88,66,55,33] def maopao(li): n = len(li) # 遍历列表长度减1次,最后一个不需要比较 for i in range(1, n): # 创建一个变量flag，用来记录本轮冒泡，是否有数据交换...
• 冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作...
• ## Python冒泡排序算法及其优化

万次阅读 多人点赞 2018-09-04 14:19:38
冒泡排序 所谓冒泡，就是将元素两两之间进行比较，谁大就往后移动，直到将最大元素排到最后面，接着再循环一趟，从头开始进行两两比较，而上一趟已经排好那个元素就不用进行比较了。（图中排好序元素标记为...
• 说到算法中排序，冒泡排序是最简单一种排序算法了，甚至不学数据结构与算法同学都会使用它。但是你有没有想过可以怎么优化？什么是冒泡排序：就像水慢慢烧开，气泡从下往上越来越大那样，第一次循环都把n个...
• python实现冒泡排序及其优化 冒泡排序是排序算法中比较基础部分，简单原理就是 将数量大小比作轻重不同气泡，轻气泡会冒到重气泡之上思想 最原始排序代码如下： def BubbleSort(numList): if not ...
• 说到算法中排序，冒泡排序是最简单一种排序算法了，甚至不学数据结构与算法同学都会使用它。但是你有没有想过可以怎么优化？ 什么是冒泡排序：就像水慢慢烧开，气泡从下往上越来越大那样，第一次循环都把n个...
• 1.冒泡排序（从大到小）：交换发生在内部循环 ...冒泡排序的优化在于didswap变量 ，通过这个变量的设置，实现冒泡排序的最好时间复杂度是O(n) #!usr/bin/python arr=[1,2,3,4,5,6,7,8,67,5,64,43,546,56...
• n = n-1 #实现方法2 def bubble_sort2(my_list): n = len(my_list) for j in range(n-1): for i in range(n-1-j): if my_list[i] > my_list[i+1]: my_list[i],my_list[i+1] = my_list[i+1],my_list[i] #优化，...
• 冒泡排序优化3.冒泡排序最终优化总结 原理 冒泡排序是一种交换排序，核心是冒泡，把数组中最小的那个往上冒，冒的过程就是和他相邻的元素交换。 重复走访要排序的数列，通过两两比较相邻记录的排序码。排序过程中...
• Python十大排序（上）冒泡排序选择排序插入排序希尔排序归并排序 冒泡排序 冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换...
• 冒泡排序1、题目假设有一个列表 list = [5,4,3,2,1]要求：按从小到大的顺序排序2、分析● 冒泡排序的思路两两比较，互换位置，每一轮选出最大(小)的数放到列尾● 图解① 第一轮比较第一轮比较② 第二轮比较③ 第三轮...
• /usr/bin/env pythone3#通过冒泡排序的方式，把列表进行排序优化前count=0number = [10,5,3,20,7,50,35,21,2,9,1,45,15]total=len(number)for a in range(total): for i in range(len(number)-1): if number[i] >...
• 1.冒泡排序是最基础排序方式，使用两次for循环完成，内层循环比较两个相邻元素大小，一次循环完找出最大元素放在最后，外层循环有多少个待排元素，循环多少遍，这样两层循环完乱序列表就排序好了，第一次...
• 写在前面，排序算法属于面试中绝对不会错过一道题，不管是原理，手撕，变形，优化，全都是考点。接下来更几篇文章争取全面考虑，从面试官角度解析排序算法以及对应回答~如果喜欢话可以点赞收藏关注！及时...
• Python 冒泡排序   冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，...
• 1、遇到情况：对于s = [5, 1, 2, 3, 4]这个列表而言，只执行一次循环即可实现排序，如果继续循环，就是1与2、3、 4进行排序，很浪费时间，所以没必要。 2、解决办法： 增加标示为flag，如果flag为True则表示还要...
• 1.冒泡排序 冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该...
• 优化Python实现（傻帽排序法） 维基百科： 冒泡排序（英语：Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...
• 一句话说，冒泡排序，就是 两两比较然后最大后移，最终形成一个有序数列，从整个流程看就像泡泡往上冒，所以叫做冒泡排序 def bubble_sort(array): if len(array)<2: return array else: n = len(array) ...
• 冒泡排序大家应该都很熟悉，是一个比较交换排序，时间复杂度是O（n2）,之前用过java实现过，现在用python来实现一次，还有其优化 总共用了三种实现方式 话不多说，直接上代码，比较三种性能------------------ ...
• 之前的优化是在原有普通的冒泡排序的基础上，加入排序标记，如果检查相邻元素之后发现并没有发生元素顺序的调换，那么则可以看做已经排好序了，直接退出，进行下次循环 虽然效果已经比之前普通的冒泡排序要好很多，...

...

python 订阅