Python中都有哪些排序算法

今天就跟大家聊聊有关Python中都有哪些排序算法，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。

1.冒泡排序

冒泡排序是 CS  入门课程中最常讲授的一种，因为它清楚地说明了排序的工作原理，同时又简单又易于理解。冒泡排序将逐步遍历列表并比较相邻的元素对。如果元素的顺序错误，则会交换这些元素。重复对列表中未排序部分的遍历，直到对列表进行排序。因为冒泡排序重复地通过列表中未排序的部分，所以它的最坏情况复杂性为O(n²)。

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中都有哪些排序算法有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注亿速云行业资讯频道，感谢大家的支持。