Python的排序算法

一、算法

1.1 算法概念

算法就是计算机解决问题的方法或者步骤
程序 = 数据结构 + 算法
1.2 算法的特性

1】确定性： 算法的每条语句具有明白的意思，不能模棱两可
2】有穷性：在执行一定的时间后，能自动竣事算法
3】输入：至少有0个或者多个的输入
4】输出：至少要有一个输出
5】可行性：经济可行，社会可行
1.3 算法的设计要求

1】正确性：对于正确的输入，会给出正确的效果。
2】健壮性：对于错误的输入，要给出合理的处置处罚
3】可读性：要代码有适当的注释，命名规范
4】高效率：要求时间复杂度尽大概低
5】低存储：空间复杂度尽大概低
1.4 算法时间复杂度（T(n)）

1> 算法时间复杂度计算公式：T(n) = O(f(n));

T(n):时间复杂度
n:表示问题的规模
f(n) :是问题规模与执行次数之间的函数
O(f(n)):使用O阶记法，记录算法时间复杂度
2> 时间复杂度推导

3> 常见的时间复杂度

二、排序算法

2.1 概念

1】定义：将给定的序列，按照特定的次序进行排列的一种算法
2】种类：

1.交换类排序：冒泡排序、快速排序
2.选择类排序：简单选择排序、堆排序
3.插入类排序：直接插入排序、折半插入排序、希尔排序
4.归并排序：二路归并、三路归并。。。
5.基数排序
2.2 冒泡排序

概念和原理：

冒泡排序：是一种简单的排序算法，它重复的遍历要排序的序列，一次比力两个元素，如果他们的次序错误，就把他们交换过来。
冒泡排序算法的运作如下：

• 比力相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
  
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  
• 针对全部的元素重复以上的步骤，除了最后一个。
  
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比力。
  

时间复杂度：O(n^2)

算法实现：

1. #定义冒泡函数
2. def bubble_sort(alist):
3.     j=0
4.     while j<len(alist): #确定序列中数据
5.         i=0
6.         while i<len(alist)-1-j: #一个序列中两两比较的次数
7.             if alist[i] > alist[i+1]:  #前一个元素比后一个元素大 交互
8.                 alist[i],alist[i+1] = alist[i+1],alist[i]
9.             i+=1
10.         j+=1

复制代码

2.3 选择排序

概念和原理：

选择排序：选择出当前序列中最小或者最大元素的所在的下标，再将最小元素和第一个位置交换（再将最大元素和最后一个位置交换），再找出剩下元素中最小或者最大元素的所在的下标，再将最小元素和第二个位置交换（再将最大元素和最后二个位置交换），以此类推
时间复杂度：O(n^2)

算法实现：

1. #定义选择排序算法
2. def select_sort(alist):
3.     i = 0 #当前序列中的第一个元素
4.     while i<len(alist)-1:
5.         min_idex = i #min_idex最小元素所在的下标 一开始就把第一个元素当成最小的
6.         j = i+1  #使用j遍历当前序列中后面所有的元素
7.         while j<len(alist):
8.             if alist[min_idex] > alist[j]: #alist[j] < alist[min_idex]
9.                 min_idex = j
10.             j+=1
11.         if min_idex != i:
12.             #将min_idex下标的元素放到第i位置上  交互
13.             alist[i],alist[min_idex] = alist[min_idex],alist[i]
14.         i+=1

复制代码

2.4 直接插入排序 （抓牌）

概念和原理：

1】定义：每次将待排序中的第一个元素，放入已排序列表中对应的位置
2】原理：每一步从待排序列中选取第一个元素，将其插入到之前已排序序列中，直到待排序列全部元素排完，则竣事排序
时间复杂度：O(n^2)

算法实现：

1. #定义直接插入排序算法
2. def insert_sort(alist):
3.     i = 1 #记录待排序列中的第一个位置  从第二个元素开始
4.     while i < len(alist):
5.         temp = alist[i]
6.         j = i
7.         while temp < alist[j-1] and j>0: #如果当前这个元素比前面的元素小
8.             #前面的元素后移
9.             alist[j] = alist[j-1]
10.             j-=1
11.         alist[j] = temp #将当前要插入的位置 将值赋值进来
12.         i+=1
15. li = [54,26,93,17,77,31,44,55,20]
16. insert_sort(li)
17. print(li)

复制代码

2.5 快速排序

概念和原理：

1】定义：快速排序是在序列元素与选定基准比力分割为大小两个部分的排序
基准（piovt）
2】原理：

1.从待排序列中，选定一个基准
2.以此为基准，将待排序列分为大小两个部分
3.对每个部分，再次选择一个基准，进行上述操作
4.直到每一个部分只有一个元素时，则排序乐成
时间复杂度：O(n^2)
算法实现：

1. #定义第一趟快排函数
2. def part(alist,L,R):
3.     #定义基准
4.     p = alist[L]
5.     while L<R:
6.         while alist[R]>=p and L<R:
7.             R-=1
8.         alist[L] = alist[R] #将比基准小的数据放在左边
10.         while alist[L] <= p and L<R:
11.             L+=1
12.         alist[R] = alist[L] #将比基准大的数据放在右边
14.     #当L==R 说明只剩最后一个元素-->基准，L或者R就是基准所在的位置
15.     alist[L] = p
17.     return L  #基准所在的下标
20. #定义快排函数
21. def quick_sort(alist,L,R):
22.     if L<R:
23.         #进行第一次快排，
24.         p_idex = part(alist,L,R)
26.         #将基准左侧的序列再次进行快排
27.         quick_sort(alist,L,p_idex-1)
29.         #将基准右侧的序列再次进行快排
30.         quick_sort(alist,p_idex+1,R)
34. li = [54,26,93,17,77,31,44,55,20]
35. quick_sort(li,0,len(li)-1)
36. print(li)

复制代码

2.6 希尔排序（相识）

概念和原理：

希尔排序是插入排序的一种，也称为缩小量排序。
原理：将序列在一个表中并对序列分别进行插入排序，重复过程，不外每次用更长的序列（步长更长了，列数更少了）
时间复杂度：O(n^2)

算法实现

1. #定义希尔排序算法
2. def shell_sort(alist):
3.     #获取元素总个数
4.     n=len(alist)
5.     #设置初始步长
6.     gap = n//2
7.     while gap > 0:
8.         #按步长进行插入
9.         for i in range(gap,n):
10.             j = i
11.             while j>=gap and alist[j-gap] > alist[j]:
12.                 alist[j-gap],alist[j] = alist[j],alist[j-gap]
13.                 j-=gap
15.         #更新步长
16.         gap = gap // 2
18. alist = [49,58,65,97,26,13,27,49,55,4]
19. shell_sort(alist)
20. print(alist)

复制代码

2.7 归并排序

概念和原理：

1】归并排序是采用分治法的一种典型的应用
2】归并排序的思想就是先递归分解序列，再归并序列

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。