算法基础：Python五大排序算法详解
算法基础：Python五大排序算法详解
排序算法的复杂度
排序是每个软件工程师和开发人员都需要掌握的技能。不仅要通过编程面试，还要对程序本身有一个全面的理解。不同的排序算法很好地展示了算法设计上如何强烈的影响程序的复杂度、运行速度和效率。
让我们看一下前6种排序算法，看看如何在Python中实现它们！
冒泡排序
冒泡排序通常是在CS入门课程中教的，因为它清楚地演示了排序是如何工作的，同时又简单易懂。冒泡排序步骤遍历列表并比较相邻的元素对。如果元素顺序错误，则交换它们。重复遍历列表未排序部分的元素，直到完成列表排序。因为冒泡排序重复地通过列表的未排序部分，所以它具有最坏的情况复杂度O(n^2)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | 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 |
选择排序
选择排序也很简单，但常常优于冒泡排序。如果您在这两者之间进行选择，最好默认选择排序。通过选择排序，我们将输入列表/数组分为两部分：已经排序的子列表和剩余要排序的子列表，它们构成了列表的其余部分。我们首先在未排序的子列表中找到最小的元素，并将其放置在排序的子列表的末尾。因此，我们不断地获取最小的未排序元素，并将其按排序顺序放置在排序的子列表中。此过程将重复进行，直到列表完全排序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | def selection_sort(arr):
for i in range(len(arr)):
minimum = i
for j in range(i + 1, len(arr)):
# Select the smallest value
if arr[j] < arr[minimum]:
minimum = j
# Place it at the front of the
# sorted end of the array
arr[minimum], arr[i] = arr[i], arr[minimum]
return arr |
插入排序
插入排序比冒泡排序和选择排序既快又简单。有趣的是，有多少人在玩纸牌游戏时会整理自己的牌！在每个循环迭代中，插入排序从数组中删除一个元素。然后，它在另一个排序数组中找到该元素所属的位置，并将其插入其中。它重复这个过程，直到没有输入元素。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
def insertion_sort(arr, simulation=False):
for i in range(len(arr)):
cursor = arr[i]
pos = i
while pos > 0 and arr[pos - 1] > cursor:
# Swap the number down the list
arr[pos] = arr[pos - 1]
pos = pos - 1
# Break and do the final swap
arr[pos] = cursor
return arr |
归并排序
归并排序是分而治之算法的完美例子。它简单地使用了这种算法的两个主要步骤：
（1）连续划分未排序列表，直到有N个子列表，其中每个子列表有1个“未排序”元素，N是原始数组中的元素数。
（2）重复合并，即一次将两个子列表合并在一起，生成新的排序子列表，直到所有元素完全合并到一个排序数组中。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | def merge_sort(arr):
# The last array split
if len(arr) <= 1:
return arr
mid = len(arr) // 2
# Perform merge_sort recursively on both halves
left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:])
# Merge each side together
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):
# Sort each one and place into the result
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 |
快速排序
快速排序也是一种分而治之的算法，如归并排序。虽然它有点复杂，但在大多数标准实现中，它的执行速度明显快于归并排序，并且很少达到最坏情况下的复杂度O(n²) 。它有三个主要步骤：
（1）我们首先选择一个元素，称为数组的基准元素(pivot)。
（2）将所有小于基准元素的元素移动到基准元素的左侧；将所有大于基准元素的元素移动到基准元素的右侧。这称为分区操作。
（3）递归地将上述两个步骤分别应用于比上一个基准元素值更小和更大的元素的每个子数组。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | 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) |
文章来源：https://www.leiphone.com/news/201901/1mIBTKyOx1QPADwQ.html
https://medium.com/@george.seif94/a-tour-of-the-top-5-sorting-algorithms-with-python-code-43ea9aa02889
布施恩德可便相知重
微信扫一扫打赏
支付宝扫一扫打赏