共计 2682 个字符,预计需要花费 7 分钟才能阅读完成。
摘要:在编程里,排序是一个重要算法,它能够帮忙咱们更快、更容易地定位数据。在这篇文章中,咱们将应用排序算法分类器对咱们的数组进行排序,理解它们是如何工作的。
本文分享自华为云社区《Python 排序算法指南》,原文作者:唐里。
在编程里,排序是一个重要算法,它能够帮忙咱们更快、更容易地定位数据。在这篇文章中,咱们将应用排序算法分类器对咱们的数组进行排序,理解它们是如何工作的。为了保障本文的可读性,这里只着重介绍 4 个排序算法。
- 冒泡排序
- 插入排序.
- 归并排序.
- 疾速排序
冒泡排序
冒泡排序是一种简略的排序算法,它比拟两个相邻对象的程序,将非预期程序的相邻对象地位替换。上面是它的工作步骤:
- 比拟第一个和第二个对象,如果第一个大于第二个,将之替换。
- 将第二个对象和第三个对象进行比拟,查看雷同条件。以此类推直到比拟到数组最初一个数。
- 反复执行这个过程,这样数组就依照从左到右从小到大排列了。
代码如下
# Python 中的冒泡排序
def bubbleSort(array):
# 外循环拜访数组的每个元素
for i in range(len(array)):
# 内循环将数组元素与外循环迭代元素进行比拟
for j in range(0, len(array) - i - 1):
# 比拟两个相邻元素
if array[j] > array[j + 1]:
# 如果元素不是预期程序则替换元素
temp = array[j]
array[j] = array[j+1]
array[j+1] = temp
data = [5, 4, 3, 2, 1]
bubbleSort(data)
print('Sorted Array')
print(data)
#output: [1, 2, 3, 4, 5]
插入排序
插入排序也很简略,它分为曾经排序和未排序两局部,将未排序局部的元素选中后正确搁置在排序局部即可。相似卡牌游戏时咱们手里有分类卡。上面是它的工作步骤:
- 遍历数组查找最低元素的索引并将其与数组的第一个元素替换。
- 找到数组 (不包含第一个元素) 中另一个最低的元素,并将其与第二个元素替换,而后反复操作,直到数组的最初一个元素。
- 这样,数组中最低的元素都会移到右边,而最大的元素会在数组的左边,因而数组是有序的。
代码如下
# Python 中的排序算法
def insertionSort(array):
for step in range(1, len(array)):
key = array[step]
j = step - 1
# 将键与其左侧的每个元素进行比拟,直到找到小于它的元素
while j >= 0 and key < array[j]:
array[j + 1] = array[j]
j = j - 1
# 将键放在比它小的元素之后。array[j + 1] = key
data = [11, 4, 3, 2, 12]
insertionSort(data)
print("sorted array")
print(data)
#output: [2, 3, 4, 11, 12]
归并排序
归并排序是基于分治算法原理的最罕用的排序算法。咱们将数组分为多个局部,而后对他们进行排序,最初将子局部合并为一个排序数组,为了更好的了解,上面是它的工作步骤:
- 把数组分成小块,直到每一块中没有独自的元素。
- 比拟每一块数组,将最小值放在左侧,最大值放在数组的右侧。
- 如果感觉很难了解,看看这个动图。
代码如下
# Python 的归并排序
def mergeSort(array):
if len(array) > 1:
# r 是将数组分为两半后的宰割点
r = len(array)//2
L = array[:r]
M = array[r:]
# 通过递归办法对两半进行排序
mergeSort(L)
mergeSort(M)
i = j = k = 0
# 直到咱们达到 L 或 M 的任一端,从中抉择较大的元素 L 和 M 并将它们搁置在 A[p 到 r] 处的正确地位
while i < len(L) and j < len(M):
if L[i] < M[j]:
array[k] = L[i]
i += 1
else:
array[k] = M[j]
j += 1
k += 1
# 将 L 或者 M 里的元素排序好后,将残余的元素并放入 A[p to r]
while i < len(L):
array[k] = L[i]
i += 1
k += 1
while j < len(M):
array[k] = M[j]
j += 1
k += 1
array = [8, 6, 14, 12, 10, 3]
mergeSort(array)
print("Sorted array:")
print(array)
#output: [3, 6, 8, 10, 12, 14]
疾速排序
与归并排序一样,疾速排序也是基于分治算法的原理的一种排序算法。它抉择一个元素作为枢轴,并围绕枢轴分区数组。上面是它的工作步骤:
- 抉择一个转折点,这能够是随机抉择的。这里假如咱们抉择数组的最初一个元素作为轴心。
- 将所有小于轴心的我的项目放在左侧,大于轴心的我的项目放在数组右侧。
- 在枢轴的左右两侧反复下面的步骤。
# Python 中的疾速排序
# 找到分区地位
def partition(array, lowest, highest):
# 这里咱们抉择最右的元素作为枢轴
pivot = array[highest]
# 为最大的元素设置指针
i = lowest - 1
# 将每个元素与枢轴元素对比
for j in range(lowest, highest):
if array[j] <= pivot:
i = i + 1
# 将 i 处的元素与 j 处的元素替换
(array[i], array[j]) = (array[j], array[i])
# 将枢轴元素与 i 指定的较大元素替换
(array[i + 1], array[highest]) = (array[highest], array[i + 1])
# 返回分区实现的地位
return i + 1
def quickSort(array, lowest, highest):
if lowest < highest:
# 找到枢轴元素
# 小于枢轴的元素放右边
# 大于枢轴的元素放左边
pi = partition(array, lowest, highest)
# 枢轴左侧的递归调用
quickSort(array, lowest, pi - 1)
# 枢轴右侧的递归调用
quickSort(array, pi + 1, highest)
array = [9, 8, 3, 2, 1, 10, 7, 6, 19]
size = len(array)
quickSort(array, 0, size - 1)
print('Sorted Array is below')
print(array)
#output [1, 2, 3, 6, 7, 8, 9, 10, 19]
以上就是本文的全部内容,感激浏览,如果对你有帮忙心愿点个赞~
原文地址:https://python.plainenglish.i…
点击关注,第一工夫理解华为云陈腐技术~
正文完