python基础__十大经典排序算法
用Python实现十大经典排序算法!
1、冒泡排序
冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
- 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
(2)动图演示
(3)Python 代码
1 def bubbleSort(arr):
2 for i in range(1, len(arr)):
3 for j in range(0, len(arr)-i):
4 if arr[j] > arr[j+1]:
5 arr[j], arr[j + 1] = arr[j + 1], arr[j]
6 return arr
2、选择排序
(1)算法步骤
- 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
- 再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
- 重复第二步,直到所有元素均排序完毕。
(2)动图演示
(3)Python 代码
1 def selectionSort(arr):
2 for i in range(len(arr) - 1):
3 # 记录最小数的索引
4 minIndex = i
5 for j in range(i + 1, len(arr)):
6 if arr[j] < arr[minIndex]:
7 minIndex = j
8 # i 不是最小数时,将 i 和最小数进行交换
9 if i != minIndex:
10 arr[i], arr[minIndex] = arr[minIndex], arr[i]
11 return arr
3、插入排序
(1)算法步骤
- 将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
- 从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)
(2)动图演示
(3)Python 代码
1 def insertionSort(arr):
2 for i in range(len(arr)):
3 preIndex = i-1
4 current = arr[i]
5 while preIndex >= 0 and arr[preIndex] > current:
6 arr[preIndex+1] = arr[preIndex]
7 preIndex-=1
8 arr[preIndex+1] = current
9 return arr
4、希尔排序
- 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率;
- 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位;
希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。
(1)算法步骤
- 选择一个增量序列 t1,t2,……,tk,其中 ti > tj, tk = 1;
- 按增量序列个数 k,对序列进行 k 趟排序;
- 每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
(2)动图演示
(3)Python 代码
1 def shellSort(arr):
2 import math
3 gap=1
4 while(gap < len(arr)/3):
5 gap = gap*3+1
6 while gap > 0:
7 for i in range(gap,len(arr)):
8 temp = arr[i]
9 j = i-gap
10 while j >=0 and arr[j] > temp:
11 arr[j+gap]=arr[j]
12 j-=gap
13 arr[j+gap] = temp
14 gap = math.floor(gap/3)
15 return arr
5、归并排序
- 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);
- 自下而上的迭代;
和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。
(1)算法步骤
- 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
- 设定两个指针,最初位置分别为两个已经排序序列的起始位置;
- 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
- 重复步骤 3 直到某一指针达到序列尾;
- 将另一序列剩下的所有元素直接复制到合并序列尾。
(2)动图演示
(3)Python 代码
1 def mergeSort(arr):
2 import math
3 if(len(arr)<2):
4 return arr
5 middle = math.floor(len(arr)/2)
6 left, right = arr[0:middle], arr[middle:]
7 return merge(mergeSort(left), mergeSort(right))
8
9 def merge(left,right):
10 result = []
11 while left and right:
12 if left[0] <= right[0]:
13 result.append(left.pop(0));
14 else:
15 result.append(right.pop(0));
16 while left:
17 result.append(left.pop(0));
18 while right:
19 result.append(right.pop(0));
20 return result
6、快速排序
快速排序的最坏运行情况是 O(n²),比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn),且 O(nlogn) 记号中隐含的常数因子很小,比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。
(1)算法步骤
- 从数列中挑出一个元素,称为 “基准”(pivot);
- 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
- 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
(2)动图演示
(3)Python 代码
1 def quickSort(arr, left=None, right=None):
2 left = 0 if not isinstance(left,(int, float)) else left
3 right = len(arr)-1 if not isinstance(right,(int, float)) else right
4 if left < right:
5 partitionIndex = partition(arr, left, right)
6 quickSort(arr, left, partitionIndex-1)
7 quickSort(arr, partitionIndex+1, right)
8 return arr
9
10 def partition(arr, left, right):
11 pivot = left
12 index = pivot+1
13 i = index
14 while i <= right:
15 if arr[i] < arr[pivot]:
16 swap(arr, i, index)
17 index+=1
18 i+=1
19 swap(arr,pivot,index-1)
20 return index-1
21
22 def swap(arr, i, j):
23 arr[i], arr[j] = arr[j], arr[i]
7、堆排序
- 大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;
- 小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列;
堆排序的平均时间复杂度为 Ο(nlogn)。
- 创建一个堆 H[0……n-1];
- 把堆首(最大值)和堆尾互换;
- 把堆的尺寸缩小 1,并调用 shift_down(0),目的是把新的数组顶端数据调整到相应位置;
- 重复步骤 2,直到堆的尺寸为 1。
(2)动图演示
(3)Python 代码
1 def buildMaxHeap(arr):
2 import math
3 for i in range(math.floor(len(arr)/2),-1,-1):
4 heapify(arr,i)
5
6 def heapify(arr, i):
7 left = 2*i+1
8 right = 2*i+2
9 largest = i
10 if left < arrLen and arr[left] > arr[largest]:
11 largest = left
12 if right < arrLen and arr[right] > arr[largest]:
13 largest = right
14
15 if largest != i:
16 swap(arr, i, largest)
17 heapify(arr, largest)
18
19 def swap(arr, i, j):
20 arr[i], arr[j] = arr[j], arr[i]
21
22 def heapSort(arr):
23 global arrLen
24 arrLen = len(arr)
25 buildMaxHeap(arr)
26 for i in range(len(arr)-1,0,-1):
27 swap(arr,0,i)
28 arrLen -=1
29 heapify(arr, 0)
30 return arr
8、计数排序
(1)动图演示
(2)Python 代码
1 def countingSort(arr, maxValue):
2 bucketLen = maxValue+1
3 bucket = [0]*bucketLen
4 sortedIndex =0
5 arrLen = len(arr)
6 for i in range(arrLen):
7 if not bucket[arr[i]]:
8 bucket[arr[i]]=0
9 bucket[arr[i]]+=1
10 for j in range(bucketLen):
11 while bucket[j]>0:
12 arr[sortedIndex] = j
13 sortedIndex+=1
14 bucket[j]-=1
15 return arr
9、桶排序
- 在额外空间充足的情况下,尽量增大桶的数量
- 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
同时,对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要。
什么时候最快
当输入的数据可以均匀的分配到每一个桶中。
什么时候最慢
当输入的数据被分配到了同一个桶中。
Python 代码
1 def bucket_sort(s):
2 """桶排序"""
3 min_num = min(s)
4 max_num = max(s)
5 # 桶的大小
6 bucket_range = (max_num-min_num) / len(s)
7 # 桶数组
8 count_list = [ [] for i in range(len(s) + 1)]
9 # 向桶数组填数
10 for i in s:
11 count_list[int((i-min_num)//bucket_range)].append(i)
12 s.clear()
13 # 回填,这里桶内部排序直接调用了sorted
14 for i in count_list:
15 for j in sorted(i):
16 s.append(j)
17
18 if __name__ == __main__ :
19 a = [3.2,6,8,4,2,6,7,3]
20 bucket_sort(a)
21 print(a) # [2, 3, 3.2, 4, 6, 6, 7, 8]
10、基数排序
基数排序 vs 计数排序 vs 桶排序
基数排序有两种方法:这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:
- 基数排序:根据键值的每位数字来分配桶;
- 计数排序:每个桶只存储单一键值;
- 桶排序:每个桶存储一定范围的数值;
动图演示
Python 代码
1 def RadixSort(list):
2 i = 0 #初始为个位排序
3 n = 1 #最小的位数置为1(包含0)
4 max_num = max(list) #得到带排序数组中最大数
5 while max_num > 10**n: #得到最大数是几位数
6 n += 1
7 while i < n:
8 bucket = {} #用字典构建桶
9 for x in range(10):
10 bucket.setdefault(x, []) #将每个桶置空
11 for x in list: #对每一位进行排序
12 radix =int((x / (10**i)) % 10) #得到每位的基数
13 bucket[radix].append(x) #将对应的数组元素加入到相 #应位基数的桶中
14 j = 0
15 for k in range(10):
16 if len(bucket[k]) != 0: #若桶不为空
17 for y in bucket[k]: #将该桶中每个元素
18 list[j] = y #放回到数组中
19 j += 1
20 i += 1
21 return list
最新文章
- 【Thinking in Java】编写构造器时应注意:尽量避免调用其他非private方法
- 2016-2017 ACM-ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred) 几道简单题的题解
- Android本地服务
- STM32内存映射
- HTML5-常见的事件- contextmenu 事件
- (五)Hololens Unity 开发之 手势识别
- java 23种设计模式 深入理解
- switchysharp设置
- JS监听对象属性改变
- GenerationType四中类型
- Redux Todos Example
- 关于CPU 架构与指令集的一些个人理解
- day 7-21 pymysql模块
- .NET Core开发日志——依赖注入
- c# 休眠后 定时唤醒
- GUI界面操作-实现简单的记事本
- zabbix系列之四——快速使用
- ls: Call From hdoop2/192.168.18.87 to hdoop2:8020 failed on connection exception: java.net.ConnectException: 拒绝连接; For more details see
- java mac install
- 山东省第四届ACM程序设计竞赛A题:Rescue The Princess