bubble什么意思

python⼗⼤经典排序算法

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进⾏排序，⽽外部排序是因排序的数据很⼤，⼀次不能容纳全部的排

序记录，在排序过程中需要访问外存。常见的内部排序算法有：插⼊排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排

序、基数排序等。⽤⼀张图概括：

关于时间复杂度：

1.平⽅阶(O(n2))排序各类简单排序：直接插⼊、直接选择和冒泡排序。

2.线性对数阶(O(nlog2n))排序快速排序、堆排序和归并排序。

3.O(n1+§))排序，§是介于0和1之间的常数。希尔排序。

4.线性阶(O(n))排序基数排序，此外还有桶、箱排序。

关于稳定性：

稳定的排序算法：冒泡排序、插⼊排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

名词解释：

n：数据规模

k：“桶”的个数

In-place：占⽤常数内存，不占⽤额外内存

Out-place：占⽤额外内存

稳定性：排序后2个相等键值的顺序和排序之前它们的顺序相同

冒泡排序

冒泡排序（BubbleSort）也是⼀种简单直观的排序算法。它重复地⾛访过要排序的数列，⼀次⽐较两个元素，如果他们的顺序错误就把他们

交换过来。⾛访数列的⼯作是重复地进⾏直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越⼩的元素会经

由交换慢慢“浮”到数列的顶端。

作为最简单的排序算法之⼀，冒泡排序给我的感觉就像Abandon在单词书⾥出现的感觉⼀样，每次都在第⼀页第⼀位，所以最熟悉。冒泡

排序还有⼀种优化算法，就是⽴⼀个flag，当在⼀趟序列遍历中元素没有发⽣交换，则证明该序列已经有序。但这种改进对于提升性能来说

并没有什么太⼤作⽤。

1.算法步骤

1.⽐较相邻的元素。如果第⼀个⽐第⼆个⼤，就交换他们两个。

2.对每⼀对相邻元素作同样的⼯作，从开始第⼀对到结尾的最后⼀对。这步做完后，最后的元素会是最⼤的数。

3.针对所有的元素重复以上的步骤，除了最后⼀个。

4.持续每次对越来越少的元素重复上⾯的步骤，直到没有任何⼀对数字需要⽐较。

2.动图演⽰

代码实现

defbubbleSort(arr):

foriinrange(1,len(arr)):

forjinrange(0,len(arr)-i):

ifarr[j]>arr[j+1]:

arr[j],arr[j+1]=arr[j+1],arr[j]

returnarr

选择排序

选择排序是⼀种简单直观的排序算法，⽆论什么数据进去都是O(n²)的时间复杂度。所以⽤到它的时候，数据规模越⼩越好。唯⼀的

好处可能就是不占⽤额外的内存空间了吧。

1.算法步骤

1.⾸先在未排序序列中找到最⼩（⼤）元素，存放到排序序列的起始位置

2.再从剩余未排序元素中继续寻找最⼩（⼤）元素，然后放到已排序序列的末尾。

3.重复第⼆步，直到所有元素均排序完毕。

2.动图演⽰

代码实现

deflectionSort(arr):

foriinrange(len(arr)-1):

#记录最⼩数的索引

minIndex=i

forjinrange(i+1,len(arr)):

ifarr[j]

minIndex=j

#i不是最⼩数时，将i和最⼩数进⾏交换

ifi!=minIndex:

arr[i],arr[minIndex]=arr[minIndex],arr[i]

returnarr

插⼊排序

插⼊排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的⼈都应

该能够秒懂。插⼊排序是⼀种最简单直观的排序算法，它的⼯作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向

前扫描，找到相应位置并插⼊。

插⼊排序和冒泡排序⼀样，也有⼀种优化算法，叫做拆半插⼊。

1.算法步骤

1.将第⼀待排序序列第⼀个元素看做⼀个有序序列，把第⼆个元素到最后⼀个元素当成是未排序序列。

2.从头到尾依次扫描未排序序列，将扫描到的每个元素插⼊有序序列的适当位置。（如果待插⼊的元素与有序序列中的某个元素相

等，则将待插⼊元素插⼊到相等元素的后⾯。）

2.动图演⽰

代码实现

definrtionSort(arr):

foriinrange(len(arr)):

preIndex=i-1

current=arr[i]

whilepreIndex>=0andarr[preIndex]>current:

arr[preIndex+1]=arr[preIndex]

preIndex-=1

arr[preIndex+1]=current

returnarr

希尔排序

希尔排序，也称递减增量排序算法，是插⼊排序的⼀种更⾼效的改进版本。但希尔排序是⾮稳定排序算法。

希尔排序是基于插⼊排序的以下两点性质⽽提出改进⽅法的：

插⼊排序在对⼏乎已经排好序的数据操作时，效率⾼，即可以达到线性排序的效率；

但插⼊排序⼀般来说是低效的，因为插⼊排序每次只能将数据移动⼀位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若⼲⼦序列分别进⾏直接插⼊排序，待整个序列中的记录“基本有序”时，

再对全体记录进⾏依次直接插⼊排序。

1.算法步骤

1.选择⼀个增量序列t1，t2，……，tk，其中ti>tj,tk=1；

2.按增量序列个数k，对序列进⾏k趟排序；

3.每趟排序，根据对应的增量ti，将待排序列分割成若⼲长度为m的⼦序列，分别对各⼦表进⾏直接插⼊排序。仅增量因⼦为1

时，整个序列作为⼀个表来处理，表长度即为整个序列的长度。

代码实现

defshellSort(arr):

importmath

gap=1

while(gap

gap=gap*3+1

whilegap>0:

foriinrange(gap,len(arr)):

temp=arr[i]

j=i-gap

whilej>=0andarr[j]>temp:

arr[j+gap]=arr[j]

j-=gap

arr[j+gap]=temp

gap=(gap/3)

returnarr

归并排序

归并排序（Mergesort）是建⽴在归并操作上的⼀种有效的排序算法。该算法是采⽤分治法（DivideandConquer）的⼀个⾮常典型的

应⽤。

作为⼀种典型的分⽽治之思想的算法应⽤，归并排序的实现由两种⽅法：

⾃上⽽下的递归（所有递归的⽅法都可以⽤迭代重写，所以就有了第2种⽅法）；

⾃下⽽上的迭代；

在《数据结构与算法JavaScript描述》中，作者给出了⾃下⽽上的迭代⽅法。但是对于递归法，作者却认为：

However,itisnotpossibletodosoinJavaScript,astherecursiongoestoodeepforthelanguagetohandle.

然⽽，在JavaScript中这种⽅式不太可⾏，因为这个算法的递归深度对它来讲太深了。

说实话，我不太理解这句话。意思是JavaScript编译器内存太⼩，递归太深容易造成内存溢出吗？还望有⼤神能够指教。

和选择排序⼀样，归并排序的性能不受输⼊数据的影响，但表现⽐选择排序好的多，因为始终都是O(nlogn)的时间复杂度。代价是需

要额外的内存空间。

1.算法步骤

1.申请空间，使其⼤⼩为两个已经排序序列之和，该空间⽤来存放合并后的序列；

2.设定两个指针，最初位置分别为两个已经排序序列的起始位置；

3.⽐较两个指针所指向的元素，选择相对⼩的元素放⼊到合并空间，并移动指针到下⼀位置；

4.重复步骤3直到某⼀指针达到序列尾；

5.将另⼀序列剩下的所有元素直接复制到合并序列尾。

2.动图演⽰

代码实现

defmergeSort(arr):

importmath

if(len(arr)<2):

returnarr

middle=(len(arr)/2)

left,right=arr[0:middle],arr[middle:]

returnmerge(mergeSort(left),mergeSort(right))

defmerge(left,right):

result=[]

whileleftandright:

ifleft[0]<=right[0]:

((0));

el:

((0));

whileleft:

((0));

whileright:

((0));

returnresult

快速排序

快速排序是由东尼·霍尔所发展的⼀种排序算法。在平均状况下，排序n个项⽬要Ο(nlogn)次⽐较。在最坏状况下则需要Ο(n2)次⽐

较，但这种状况并不常见。事实上，快速排序通常明显⽐其他Ο(nlogn)算法更快，因为它的内部循环（innerloop）可以在⼤部分的

架构上很有效率地被实现出来。

快速排序使⽤分治法（Divideandconquer）策略来把⼀个串⾏（list）分为两个⼦串⾏（sub-lists）。

快速排序⼜是⼀种分⽽治之思想在排序算法上的典型应⽤。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为⼀听到这个名字你就知道它存在的意义，就是快，⽽且效率⾼！它是处理⼤数据最快的排序算

法之⼀了。虽然WorstCa的时间复杂度达到了O(n²)，但是⼈家就是优秀，在⼤多数情况下都⽐平均时间复杂度为O(nlogn)的排

序算法表现要更好，可是这是为什么呢，我也不知道。好在我的强迫症⼜犯了，查了N多资料终于在《算法艺术与信息学竞赛》上找

到了满意的答案：

快速排序的最坏运⾏情况是O(n²)，⽐如说顺序数列的快排。但它的平摊期望时间是O(nlogn)，且O(nlogn)记号中隐含的

常数因⼦很⼩，⽐复杂度稳定等于O(nlogn)的归并排序要⼩很多。所以，对绝⼤多数顺序性较弱的随机数列⽽⾔，快速排

序总是优于归并排序。

1.算法步骤

1.从数列中挑出⼀个元素，称为“基准”（pivot）;

2.重新排序数列，所有元素⽐基准值⼩的摆放在基准前⾯，所有元素⽐基准值⼤的摆在基准的后⾯（相同的数可以到任⼀边）。在

这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

3.递归地（recursive）把⼩于基准值元素的⼦数列和⼤于基准值元素的⼦数列排序；

递归的最底部情形，是数列的⼤⼩是零或⼀，也就是永远都已经被排序好了。虽然⼀直递归下去，但是这个算法总会退出，因为在每

次的迭代（iteration）中，它⾄少会把⼀个元素摆到它最后的位置去。

2.动图演⽰

代码实现

defquickSort(arr,left=None,right=None):

left=0ifnotisinstance(left,(int,float))elleft

right=len(arr)-1ifnotisinstance(right,(int,float))elright

ifleft

partitionIndex=partition(arr,left,right)

quickSort(arr,left,partitionIndex-1)

quickSort(arr,partitionIndex+1,right)

returnarr

defpartition(arr,left,right):

pivot=left

index=pivot+1

i=index

whilei<=right:

ifarr[i]

swap(arr,i,index)

index+=1

i+=1

swap(arr,pivot,index-1)

returnindex-1

defswap(arr,i,j):

arr[i],arr[j]=arr[j],arr[i]

堆排序

堆排序（Heapsort）是指利⽤堆这种数据结构所设计的⼀种排序算法。堆积是⼀个近似完全⼆叉树的结构，并同时满⾜堆积的性质：

即⼦结点的键值或索引总是⼩于（或者⼤于）它的⽗节点。堆排序可以说是⼀种利⽤堆的概念来排序的选择排序。分为两种⽅法：

1.⼤顶堆：每个节点的值都⼤于或等于其⼦节点的值，在堆排序算法中⽤于升序排列；

2.⼩顶堆：每个节点的值都⼩于或等于其⼦节点的值，在堆排序算法中⽤于降序排列；

堆排序的平均时间复杂度为Ο(nlogn)。

1.算法步骤

1.创建⼀个堆H[0……n-1]；

2.把堆⾸（最⼤值）和堆尾互换；

3.把堆的尺⼨缩⼩1，并调⽤shift_down(0)，⽬的是把新的数组顶端数据调整到相应位置；

4.重复步骤2，直到堆的尺⼨为1。

2.动图演⽰

代码实现

defbuildMaxHeap(arr):

importmath

foriinrange((len(arr)/2),-1,-1):

heapify(arr,i)

defheapify(arr,i):

left=2*i+1

right=2*i+2

largest=i

ifleftarr[largest]:

largest=left

ifrightarr[largest]:

largest=right

iflargest!=i:

swap(arr,i,largest)

heapify(arr,largest)

defswap(arr,i,j):

arr[i],arr[j]=arr[j],arr[i]

defheapSort(arr):

globalarrLen

arrLen=len(arr)

buildMaxHeap(arr)

foriinrange(len(arr)-1,0,-1):

swap(arr,0,i)

arrLen-=1

heapify(arr,0)

returnarr

计数排序

计数排序的核⼼在于将输⼊的数据值转化为键存储在额外开辟的数组空间中。作为⼀种线性时间复杂度的排序，计数排序要求输⼊的

数据必须是有确定范围的整数。

1.动图演⽰

代码实现

defcountingSort(arr,maxValue):

bucketLen=maxValue+1

bucket=[0]*bucketLen

sortedIndex=0

arrLen=len(arr)

foriinrange(arrLen):

ifnotbucket[arr[i]]:

bucket[arr[i]]=0

bucket[arr[i]]+=1

forjinrange(bucketLen):

whilebucket[j]>0:

arr[sortedIndex]=j

sortedIndex+=1

bucket[j]-=1

returnarr

桶排序

桶排序是计数排序的升级版。它利⽤了函数的映射关系，⾼效与否的关键就在于这个映射函数的确定。为了使桶排序更加⾼效，我们

需要做到这两点：

1.在额外空间充⾜的情况下，尽量增⼤桶的数量

2.使⽤的映射函数能够将输⼊的N个数据均匀的分配到K个桶中

同时，对于桶中元素的排序，选择何种⽐较排序算法对于性能的影响⾄关重要。

1.什么时候最快

当输⼊的数据可以均匀的分配到每⼀个桶中。

2.什么时候最慢

当输⼊的数据被分配到了同⼀个桶中。

基数排序

基数排序是⼀种⾮⽐较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别⽐较。由于整数也可以表达

字符串（⽐如名字或⽇期）和特定格式的浮点数，所以基数排序也不是只能使⽤于整数。

1.基数排序vs计数排序vs桶排序

基数排序有两种⽅法：

这三种排序算法都利⽤了桶的概念，但对桶的使⽤⽅法上有明显差异：

基数排序：根据键值的每位数字来分配桶；

计数排序：每个桶只存储单⼀键值；

桶排序：每个桶存储⼀定范围的数值；

基数排序动图演⽰

原⽂/wuxinyan/p/