python中几种常用的排序算法

这篇文章主要介绍“python中几种常用的排序算法”，在日常操作中，相信很多人在python中几种常用的排序算法问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”python中几种常用的排序算法”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

排序算法的运用非常广泛。各种语言都有自己内置的排序函数，在面试过程中也经常会有排序算法的考题。总结几种排序算法的实现。

这个问题的显示表示是：请详细描述如何将一组数字按从小到大的顺序排列。

我首先想到的是：

1. 找出数组中最小的一个；

2. 把这个数放到另一数组的最后面；

3. 把这个数从原来的数组中剔除；

4. 重复

重复的过程通常涉及到遍历和递归，上面这个解法叫「选择排序」，用 Python 实现如下：

def select_sort(arr):
    new_arr = []
     # 重复
    for i in range(len(arr)):
        small_index = find_smallest(arr)
         # 把这个数从原来的数组中剔除；
        smallest = arr.pop(small_index)
         # 把这个数放到另一数组的最后面；
        new_arr.append(smallest)
    return new_arr
def find_smallest(arr):
     """找出数组中最小的一个；"""
    smallest = arr[0]
    index = 0
    for e in range(1,len(arr)):
        if arr[e] < smallest:
            smallest = arr[e]
            index = e
    return index

可以看出来，代码实现基本上就是用编程语言写出解题思路。所以很多编程进阶书都提到一个解决问题的办法就是离开键盘，去上个厕所，在纸上画一画。只要是解题思路很详细，基本上是可以用来当伪代码使用的，可以全部放入代码的注释当中。

冒泡排序（Bubble Sort）

1. 比较前一个数和后一个数，如果前比后大，对换他们的位置；

2. 循环执行

def bubble_sort(arr):
    for i in range(len(arr) - 1):
        for j in range(len(arr) - i - 1):
            if arr[j] > arr[j + 1]:
                tmp = arr[j + 1]
                arr[j + 1] = arr[j]
                arr[j] = tmp
    return arr

快速排序

上面两种算法要操作的步骤很多，当数组太多时就会造成性能过低，我们可以想办法减少要操作的步骤，从而降低算法的复杂度，提高执行效率。减少步骤的很多算法都是将数据分成几部分来处理，也就是通常说的「分治」，从而不断减少没部分需要处理的步骤，选择排序就是这样一种算法：
1.选出第一个元素
2.遍历每个元素，也就是从第二个开始拿，如果比第一个元素小，放到一个新数组里；如果比它大，放到另一个数组；
3.对两个新数组执行同样的操作；
那什么时候不需要执行这样的操作了呢？当数组的元素个数小于2的时候，不需要比较了，分治策略就结束。

「分治」是一种非常常见的解题思路。因为它能不断的将问题变成更简单的问题，最后变成一个显而易见的事。也就是说它有两个条件：

• 基准条件。也就是没有办法再分了，足够简单了。

• 分治条件或者叫递归条件。能够进一步缩小需要解决的问题的规模。

分治法在算法中非常普遍，不是因为他能降低算法的复杂度，而是他能一步步将复杂的问题变得越来越简单，规模越来越小，最后变成一个超级简单的问题，如果能进一步抽象这种过程，就能考执行同样的抽象步骤解出来来。分治法经常和递归用在一起，这就衍生了一种变成方式——函数式编程，如果能多接触一些递归的案例，对于函数式变成和抽象是非常有帮助的。软件设计就是讲一个非常复杂的问题抽象的过程，所以掌握函数式编程和递归概念对于抽象能力和软件设计应该是很有帮助的。

下面实现快速排序：

def quick(arr):
    if len(arr) < 2:
        return arr
    else:
        base = arr[0]
        less = [i for i in arr[1:] if i < base]
        greater = [i for i in arr[1:] if i >= base]
        return quick(less) + [base] + quick(greater)

归并排序

归并排序和选择排序一样是一种分治递归策略：

1. 从中间分成两组

2. 将两个已经排序好的列表进行合并，合并成的列表就是排序好的
   那怎么对上述两个列表排序呢？对两个列表再执行分组策略
   什么时候不能继续了呢？当元素个数小于 2 的时候

具体实现：

def merge_sort(arr):
    # divide to two
    if len(arr) < 2:
        return arr
    mid = int(len(arr)/2)
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)
def merge(left, right):
    result = []
    j = 0
    i = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    # add the larger part both left and right
    result += left[i:]
    result += right[j:]
    return result

到此，关于“python中几种常用的排序算法”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！