PyThon排序算法的用法及示例
387次观看相信有很多朋友在听别人讲关于python的排序算法时,经常觉得云里雾里吧,其实关于python的排序算法一共就五大内容,小编给大家梳理了一遍,内容非常简单易懂,一起来看看吧~
1、冒泡排序
冒泡排序将逐步遍历列表并比较相邻的元素对。如果元素的顺序错误,则会交换这些元素。重复对列表中未排序部分的遍历,直到对列表进行排序。
示例代码:
def bubble_sort(arr):
def swap(i, j):
arr[i], arr[j] = arr[j], arr[i]
n = len(arr)
swapped = True
x = -1
while swapped:
swapped = False
x = x + 1
for i in range(1, n-x):
if arr[i - 1] > arr[i]:
swap(i - 1, i)
swapped = True
return arr
场景演示:
2、选择排序
选择排序优于冒泡排序。使用选择排序,我们将输入列表/数组分为两部分:已排序项的子列表和构成列表其余部分的剩余项的子列表。
我们首先在未排序的子列表中找到最小的元素,并将其放在已排序子列表的末尾。我们不断地获取最小的未排序元素,并将其按排序顺序放入已排序的子列表中。此过程将重复进行,直到列表完全排序。
示例代码:
def selection_sort(arr):
for i in range(len(arr)):
minimum = i
for j in range(i + 1, len(arr)):
# 选择最小值
if arr[j] < arr[minimum]:
minimum = j
# 把它放在已排序的数组结尾
arr[minimum], arr[i] = arr[i], arr[minimum]
return arr
场景演示:
3、插入排序
插入排序比冒泡排序和选择排序都要快,而且可以说更加简单。在每次循环迭代中,插入排序从数组中删除一个元素。然后在另一个排序数组中查找该元素所属的位置,并将其插入其中。它重复这个过程,直到没有输入元素保留。
代码示例:
def insertion_sort(arr):
for i in range(len(arr)):
cursor = arr[i]
pos = i
while pos > 0 and arr[pos - 1] > cursor:
# 交换列表中的数字
arr[pos] = arr[pos - 1]
pos = pos - 1
# 中断并进行最终交换
arr[pos] = cursor
return arr
场景演示:
4、合并排序
合并排序是一个完美的分而治之的算法例子。使用这种算法只需要通过以下两个主要步骤:
(1) 连续分割未排序的列表,直到有N个子列表,其中每个子列表都有1个“未排序”的元素,N是原始数组中的元素数。
(2) 反复合并,即一次将两个子列表合并在一起,生成新的已排序子列表,直到所有元素都完全合并到一个已排序的数组中。
代码示例:
def merge_sort(arr):
# 对最后一个数组进行拆分
if len(arr) <= 1:
return arr
mid = len(arr) // 2
# 在两个部分上递归执行merge_sort
left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:])
# 合并在一起
return merge(left, right, arr.copy())
def merge(left, right, merged):
left_cursor, right_cursor = 0, 0
while left_cursor < len(left) and right_cursor < len(right):
# 将每一个排序并放入结果
if left[left_cursor] <= right[right_cursor]:
merged[left_cursor+right_cursor]=left[left_cursor]
left_cursor += 1
else:
merged[left_cursor + right_cursor] = right[right_cursor]
right_cursor += 1
for left_cursor in range(left_cursor, len(left)):
merged[left_cursor + right_cursor] = left[left_cursor]
for right_cursor in range(right_cursor, len(right)):
merged[left_cursor + right_cursor] = right[right_cursor]
return merged
场景演示:
5、快速排序
快速排序也是一种分而治之的算法,与合并排序一样。尽管它有点复杂,但在大多数标准实现中,它的执行速度比合并排序快得多,而且很少达到O(n?)的最坏情况复杂度。它有三个主要步骤:
(1) 我们首先从数组中选择一个元素,称之为pivot。
(2) 将小于轴的所有元素移到轴的左侧;将大于轴的所有元素移到轴的右侧。这称为分区操作。
(3) 递归地将上述2个步骤分别应用于元素的每个子数组,这些元素的值比上一个轴的值小或大。
示例代码:
def partition(array, begin, end):
pivot_idx = begin
for i in xrange(begin+1, end+1):
if array[i] <= array[begin]:
pivot_idx += 1
array[i], array[pivot_idx] = array[pivot_idx], array[i]
array[pivot_idx], array[begin] = array[begin], array[pivot_idx]
return pivot_idx
def quick_sort_recursion(array, begin, end):
if begin >= end:
return
pivot_idx = partition(array, begin, end)
quick_sort_recursion(array, begin, pivot_idx-1)
quick_sort_recursion(array, pivot_idx+1, end)
def quick_sort(array, begin=0, end=None):
if end is None:
end = len(array) - 1
return quick_sort_recursion(array, begin, end)
场景演示:
以上就是python排序算法的全部内容了,足够能让您抓取排序算法精髓,多多尝试几次,一定让您的python排序算法使用炉火纯青~
更多PyThon编程实例,点击进入PyThon学习网教学中心。
©本文版权归环球青藤所有,任何形式转载请联系我们。