文档章节

十大经典排序算法的python实现

o
 osc_yny7gjj7
发布于 2018/09/03 13:51
字数 1979
阅读 7
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

十种常见排序算法可以分为两大类

  非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序。包括:冒泡排序、选择排序、归并排序、快速排序、插入排序、希尔排序、堆排序等。

  线性时间非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此称为线性时间非比较类排序。包括:计数排序、桶排序、基数排序等。

下面介绍各种算法的基本思想及python实现:

1  冒泡排序(Bubble Sort)

1.1 基本思想:

  它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

 

1.2 实现代码:

1 def bubbleSort(arr):
2     n = len(arr)
3     for i in range(n-1):
4         for j in range(n-i-1):
5             if arr[j] > arr[j+1]:
6                 arr[j], arr[j+1] = arr[j+1], arr[j]
7     return arr

 

2  选择排序(Selection Sort)

2.1 基本思想:

  首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

 

2.2 实现代码

1 def selectionSort(arr):
2     n = len(arr)
3     for i in range(n-1):
4         minIndex = i
5         for j in range(i+1, n, 1):
6             if arr[j] < arr[minIndex]:
7                 minIndex = j
8         arr[i], arr[minIndex] = arr[minIndex], arr[i]
9     return arr

 

3 插入排序(Insertion Sort)

3.1 基本思想

  通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

 

3.2 实现代码

1 def insertionSort(arr):
2     n = len(arr)
3     for i in range(1, n):
4         for j in range(i, 0, -1):
5             if arr[j] < arr[j-1]:
6                 arr[j-1], arr[j] = arr[j], arr[j-1]
7     return arr

 

4  希尔排序(Shell Sort)

4.1 基本思想

  它是简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素,将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序。希尔排序又叫缩小增量排序

 

4.2 实现代码

 1 def shellsort(arr):
 2     n = len(arr)
 3     group = 3
 4     gap = n // group
 5     while gap > 0:
 6         for i in range(0, gap):
 7             for j in range(i+gap, n, gap):
 8                 tmp = arr[j]
 9                 for k in range(j-gap, i-1, -gap):
10                     if arr[k] >= arr[j]:
11                         arr[k + gap], arr[k] = arr[k], tmp
12         gap //= group
13     return arr

 

5 归并排序(Merge Sort)

5.1 基本思想

  归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。 

 

5.2 实现代码

 1 def mergeSort(arr):
 2     if len(arr) < 2:
 3         return arr
 4     middle = int(len(arr) / 2)
 5     left = mergeSort(arr[:middle])
 6     right = mergeSort(arr[middle:])
 7     return merge(left, right)
 8 def merge(left, right):
 9     result = []
10     leftindex = rightindex = 0
11     while leftindex < len(left) and rightindex < len(right):
12         if left[leftindex] <= right[rightindex]:
13             result.append(left[leftindex])
14             leftindex += 1
15         else:
16             result.append(right[rightindex])
17             rightindex += 1
18     if len(left):
19         for i in left[leftindex:]:
20             result.append(i)
21     if len(right):
22         for i in right[rightindex:]:
23             result.append(i)
24     return result

 

6  快速排序(Quick Sort)

6.1 基本思想

  通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

 

6.2 实现代码

 1 def quickSort(arr, left, right):
 2     if left < right:
 3         partitionIndex = partition(arr, left, right)
 4         quickSort(arr, left, partitionIndex - 1)
 5         quickSort(arr, partitionIndex + 1, right)
 6         return arr
 7 def partition(arr, left ,right):
 8     pivot = right
 9     i = left - 1
10     for j in range(left, right):
11         if arr[j] <= arr[pivot]:
12             i += 1
13             arr[i], arr[j] = arr[j], arr[i]
14     arr[i+1], arr[pivot] = arr[pivot], arr[i+1]
15     # print(arr)
16     return i + 1

 

7  堆排序(Heap Sort)

7.1 基本思想

  堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

 

7.2 代码实现

 1 def adjust_heap(arr, i, n):
 2     lchild = 2 * i + 1
 3     rchild = 2 * i + 2
 4     max = i
 5     if i < n / 2:
 6         if lchild < n and arr[lchild] > arr[max]:
 7             max = lchild
 8         if rchild < n and arr[rchild] > arr[max]:
 9             max = rchild
10         if max != i:
11             arr[max], arr[i] = arr[i], arr[max]
12             adjust_heap(arr, max, n)              # 下滤
13 def build_max_heap(arr, n):
14     for i in range(0, int(n // 2))[::-1]:
15         adjust_heap(arr, i, n)
16 def heap_sort(arr):
17     n = len(arr)
18     build_max_heap(arr, n)
19     for i in range(0, n)[::-1]:
20         arr[0], arr[i] = arr[i], arr[0]
21         adjust_heap(arr, 0, i)                    # 下滤
22     return arr

 

8 计数排序

8.1 基本思想

  计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

 

8.2 实现代码

 1 def countingSort(arr, maxValue):
 2     bucket = np.array(np.zeros(maxValue + 1))   # 算上0,arr必须是正数
 3     sortedIndex = 0
 4     bucketLen = maxValue + 1
 5     n = len(arr)
 6     for i in range(0, n):
 7         # if bucket[arr[i]]:
 8         bucket[arr[i]] += 1
 9     for j in range(0, bucketLen):
10         while bucket[j] > 0:
11             arr[sortedIndex] = j
12             sortedIndex += 1
13             bucket[j] -= 1
14     return arr

 

9 桶排序

9.1 基本思想

  假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(可以使用别的排序算法或是以递归方式继续使用桶排序进行排)。

 

9.2 实现代码

 1 def bucketSort(arr, bucketSize):
 2     if len(arr) == 0:
 3         return arr
 4     minValue = min(arr)           # 输入数据的最小值
 5     maxValue = max(arr)           # 输入数据的最大值
 6     # 桶的初始化
 7     DEFAULT_BUCKET_SIZE = 5      # 设置桶的默认数量为5
 8     bucketSize = bucketSize | DEFAULT_BUCKET_SIZE      # 按照位或(二进制)
 9     bucketCount = math.floor((maxValue - minValue) / bucketSize) + 1
10     buckets = [[] for i in range(bucketCount)]
11 
12     #  利用映射函数将数据分配到各个桶中
13     for i in range(0, len(arr)):
14         (buckets[math.floor((arr[i] - minValue) / bucketSize)]).append(arr[i])
15     arr = []
16     for i in range(0, len(buckets)):
17         insertionSort(buckets[i])               # 对每个桶进行排序,这里使用了插入排序
18         for j in range(0, len(buckets[i])):
19             arr.append(buckets[i][j])
20     return arr

 

10 基数排序

10.1 基本思想

  基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。

 

10.2 实现代码

 1 import math
 2 def radix_sort(arr, radix=10):
 3     k = int(math.ceil(math.log(max(arr), radix)))   # 取得位数
 4     bucket = [[] for i in range(radix)]             # 初始化 bucket = [[],[],...]
 5     for i in range(1, k+1):
 6         for j in arr:
 7             bucket[j % (radix ** i) // (radix ** (i - 1))].append(j)   # 先截取元素的后k位数再取第k位上的数字(k=1,2...)
 8         del arr[:]
 9         for z in bucket:
10             arr += z
11             print(arr)
12             del z[:]
13     return arr

 

 

参考:https://www.cnblogs.com/onepixel/articles/7674659.html

o
粉丝 1
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
用vertx实现高吞吐量的站点计数器

工具:vertx,redis,mongodb,log4j 源代码地址:https://github.com/jianglibo/visitrank 先看架构图: 如果你不熟悉vertx,请先google一下。我这里将vertx当作一个容器,上面所有的圆圈要...

jianglibo
2014/04/03
4K
3
SQLServer实现split分割字符串到列

网上已有人实现sqlserver的split函数可将字符串分割成行,但是我们习惯了split返回数组或者列表,因此这里对其做一些改动,最终实现也许不尽如意,但是也能解决一些问题。 先贴上某大牛写的s...

cwalet
2014/05/21
9.6K
0
Promises/A 和 when() 实现--When.js

When.js 是 cujojs 的轻量级的 Promises/A 和 when() 实现,从 wire.js 的异步核心和 cujojs 的 IOC 容器派生而来。包含很多其他有用的 Promiss 相关概念,例如联合多个 promiss、mapping 和...

匿名
2013/02/15
7.4K
0
django-c10k-demo

这是一个演示程序,用来实现同时 10000 个并发连接到 Django 。涉及的概念包括:the C10k problem, the WebSocket protocol, the Django web framework, and Python's upcoming asynchronou......

匿名
2013/03/27
1.7K
0
Python开发者社区整站源码--Pythoner

pythoner.net 整站源代码 依赖模块 Django 1.4.2 PIL DjangoVerifyCode 0.2.2 开发环境配置 运行scripts目录下的setupenv.sh文件,将会自动安装配置所需环境 设置本地环境变量:export env=D...

~T.y~
2013/04/10
3.1K
0

没有更多内容

加载失败,请刷新页面

加载更多

数据获取的小技巧

在大数据如此火的时代,我们要获取更多数据,就要进行数据采集,过滤,然后再进行使用。比如当我们在进行一个项目并且需要大量真实数据时,就需要通过爬虫去获得,有些爬取额数据还不能直接使用,...

xiaotaomi7
42分钟前
21
0
docker cp 容器和虚拟机间的数据拷贝

容器复制到主机 docker cp {container_name}:{source_path} {target_path}#例子: docker cp php:www/php.ini /home/alex/php.ini 主机复制到容器 docker cp {source_path} {container_nam......

关元
50分钟前
25
0
spring boot整合kafaka批量消费

spring boot整合kafaka批量消费: 配置文件: kafka: producer: bootstrap-servers: 127.0.0.1:9092 batch-size: 16785 #一次最多发送数据量 retries: 1 #发送失败后的重复发送次数 buffer-m...

漫步行者
55分钟前
7
0
最新苹果多屏电脑控制技术---ios群控/苹果群控/一键实时同步操作/入门安装步骤以及功能讲解

创联苹果群控是一款通过无线发送命令来操作主控手机来带动全部被控手机,主控手机怎么操作被控手机全部同步进行相同操作,支持一键每台手机输入不一样的文字!无需连接USB数据线、无需XP框架...

osc_bodzcw38
55分钟前
10
0
NOIP模拟赛 编码

题目描述 一个字符串str的p型编码a的定义如下:把str表示成b1个c1,b2个c2…bn个cn,然后将b1,c1,b2,c2,…,bn,cn收尾拼接成的字符串中最短的字符串设为a。例如:字符串122344111可被描述为"1个...

osc_wcs4pa6z
56分钟前
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部