小伙伴们大家好，上一期我们分享了数据结构中栈与队列部分的内容，那么这一期我们将要分享的是数据结构中一些常见的排序与搜索算法。

目录

前言

冒泡排序

选择排序

快速排序

前言

• 概念

排序算法（sorting algorithm）是一种将一串数据依照特定顺序进行排列的一种算法。

• 稳定性

稳定排序算法会让原本有相等键值的记录维持相对次序。也就是说，如果一个排序算法是稳定的，当有两个相等键值的记录R和S，且在原本的列表中R的相对位置出现在S之前，那么在排序过后的列表中R也将会在S之前。

不稳定排序算法可能会改变原有数据的相对次序，但是稳定的排序算法从来不会如此。

冒泡排序

• 概念

冒泡排序（Bubble Sort）是一种简单的排序算法。他重复的遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就交换过来，并且每一次都会选择出一个最大或最小的数据放置顶端。

• 具体过程

1、比较相邻元素，如果第一个比第二个大（升序），则交换两者顺序

2、对每一对相邻的元素做同样的工作，从开始第一对到结尾的最后一对。这一步完成后，结尾将会是最大的元素。

3、除了最后一个元素，对剩余的所有元素重复以上操作。

4、持续对越来越少的元素重复以上操作，直到没有任何一对数字需要比较。

一次冒泡排序过程需要进行n-1次比较，0-多次交换。

• 时间复杂度

最优时间复杂度O(n)：表示一次遍历过程完成发现没有任何可以交换的元素，排序结束

最坏时间复杂度O(n^2)

稳定性：稳定

• 代码实现

		 
# 冒泡排序算法
# 每一次选择一个最大的放到一端，注意下标
def bubbleSort(li):
 n=len(li)
 for i in range(0,n-1):
 count=0
 for j in range(0,n-i-1):
 if li[j]>=li[j+1]:
 count+=1
 li[j],li[j+1]=li[j+1],li[j]#交换数据
 if count==0:#初始数据有序的情况
 return li
 return li
if __name__ == '__main__':
 listt=[3,2,5,7,9,8,6,1]
 bubbleSort(listt)
 print(listt)

选择排序

• 概念

选择排序（Selection Sort）是一种简单直观的排序算法，他的工作原理如下，首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后继续从剩余未排序元素中继续寻找最小（大），然后放到已排序序列的末尾，以此类推，直到所有元素排序完成。

选择排序的主要优点主要与数据移动有关，如果某个元素位于正确的最终位置上，则他不会移动。选择排序每交换一次排序，他们当中至少有一个被移动到其最终位置上，因此对n个元素的表进行排序至多进行n-1次交换。

• 稳定性与复杂度

最优时间复杂度O(n^2)

最坏时间复杂度O(n^2)

稳定性：不稳定（不稳定，例如序列6 8 6 1 9，第一遍选择第1个元素6会和1交换，那么原序列中2个6的相对前后顺序就会改变，即不稳定）

• 代码实现

		# 选择排序
def SelectionSort(li):
 n=len(li)
 print(li)
 for i in range(0,n-1):
 max=li[0]#标记最大值
 temp=0#标记下标
 for j in range(0,n-i):
 if li[j]>max:
 max=li[j]
 temp=j#标记最大值的下标
 # 每次选出一个最大值放到已排序序列的最前端
 li[n-i-1],li[temp]=li[temp],li[n-i-1]
 print(li)
 return li
if __name__ == '__main__':
 listt=[3,2,5,7,9,8,6,1]
 SelectionSort(listt)

• 选择排序与冒泡排序的比较

冒泡排序是每次都进行相邻间的两个元素大小比较，直至末尾。选择排序是每一次都是当前元素与未排序元素一一比较，直至选出一个最大（最小）的值。

一趟冒泡排序交换次数比较多，一趟选择排序只需要交换一次。

冒泡排序稳定，选择排序不稳定。

快速排序

• 概念

快速排序（QuickSort）,又称划分交换排序（partition-exchange-sort）,具有递归性质，通过一趟排序将要排序的数据划分成独立的两部分，其中以一个数据为中轴，一边的数据据比另一边的数据都要小，然后再用同样的方法对这两部分分别进行快速排序，整个过程以递归的方式完成。

• 步骤

1、从数列中选择一个元素，通常选择第一个元素，称为基准（pivot）

2、重新排序，通常所有比基准数据小的放在左边，所有比基准数据大的放在右边（相同的数可以放在任意一侧）。在这次划分结束后，该基准数据就处于中轴位置。

3、对中轴数据两侧的未排序序列进行递归子排序，重复前两个步骤。

• 稳定性与复杂度

最优时间复杂度O(nlogn)

最坏时间复杂度O(n^2)

稳定性：不稳定

最好的情况就是，我们每运行一次分区，就会将数列分成两个几近相等的片段，即每个子序列元素个数相差不大，此时复杂度为O(nlogn)。最坏的情况就是，初始待排序序列基本有序，此时递归调度时没有函数出口，会陷入大量重复无作用的递归中。比如序列9，8，7，6，5，4，3，2，1，按从小到大排序时就是这种情况，造成这种情况的原因就是，基准数据选择不当，所以最好选择中间大小的数据作为基准防止这种情况的发生。

• 代码实现

	# 快速排序
def QuickSort(li,a,b):
 print(li)
 low=a
 high=b
 x=li[low]
 while low<high:
 while li[high]>=x and low<high:
 high-=1
 if low<high:#注意加这个条件，否则交换时会出错
 li[low]=li[high]
 low+=1
 while li[low]<x and low<high:
 low+=1
 if low < high:
 li[high]=li[low]
 high-=1
 li[low]=x
 print(li)
 if a<low-1:
 QuickSort(li,a,low-1)
 if low+1<b:
 QuickSort(li,low+1,b)
if __name__ == '__main__':
 listt=[4, 2, 5, 7, 9, 8, 6, 3, 1]
 QuickSort(listt,0,len(listt)-1)

好了，今天的分享就到这儿了。下一期将继续分享有关排序和搜索算法的内容。同时，欢迎持续关注小编相互交流，这里有最全面的python知识分享!