一、前言

在面试的问题中可能会遇到排序算法，毕竟作为一个程序员，掌握排序算法是非常重要的。本文总结了用python实现的八种经典排序算法。排序算法是数据结构和算法中最基本的算法之一。排序算法可以分为内部排序和外部排序。内部排序是对内存中的数据记录进行排序，而外部排序是访问外部内存，因为排序的数据太大，不能一次保存所有的排序记录。常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、合并排序、快速排序、堆排序、基数排序等。

冒泡排序是一种简单的排序算法。它反复访问要排序的序列，一次比较两个元素，如果它们的顺序不对，就交换它们。重复访问序列的工作，直到不需要交换为止，也就是说，序列已经被排序。这个算法的名字来自这样一个事实:元素越小，它就越慢地浮到序列的顶部。这个算法的名字来自这样一个事实:越小的元素会慢慢“浮动”的顺序(升序或降序)通过交换,就像二氧化碳泡沫的碳酸饮料最终将浮到顶部,所以它被称为“泡沫排序”。

算法原理:

比较相邻的元素，如果第一个大于第二个，交换两个。

对每一对相邻的元素做同样的处理，从开始的第一对到结束的最后一对。此时，最后一个元素应该是最大的数。

对除最后一个元素外的所有元素重复上述步骤。

对于越来越少的元素，继续重复上述步骤，直到没有可比较的数字对为止。

演示过程如下:

def bubble_sort(nums):
    for pass_num in range(len(nums) - 1, 0, -1):   # n-1趟
        flag = True    # 每一趟置flag为True
        for i in range(pass_num):
            if nums[i] > nums[i + 1]:
                nums[i], nums[i + 1] = nums[i + 1], nums[i]
                flag = False     # 有交换：flag置为False
        # 每一趟结束后大的数会往后冒泡
        # flag为True  说明到这趟已经没有交换 提前跳出循环 提高算法效率
        # print(nums)
        if flag:
            break
    return nums


s = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
print(s)
print(bubble_sort(s))

# 结果如下：
[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

选择性排序是一种简单直观的排序算法，无论输入什么数据，它的时间复杂度是O (n)²)。所以当你使用它时，数据越小越好。唯一的优势可能是它不会占用额外的内存空间。

算法原理:

首先，找到无序序列中的最小(大)元素，并将其存储在排序序列的开头

然后我们继续从剩余的无序元素中找到最小(最大)的元素，然后把它放在排序后的序列的末尾。

重复第二步，直到所有元素都排序完毕。

动态图如下:

def select_sort(nums):
    for pass_num in range(len(nums) - 1, 0, -1):   # n-1趟
        pos_max = 0
        for location in range(1, pass_num + 1):
            if nums[location] > nums[pos_max]:
                pos_max = location
        # 每一趟只交换一次
        nums[pass_num], nums[pos_max] = nums[pos_max], nums[pass_num]

    return nums

s = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
print(s)
print(select_sort(s))


# 结果如下：
[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

def insert_sort(arr):
    for index_ in range(1, len(arr)):
        position = index_
        current_value = arr[index_]    # 插入项
        # 比对 移动  直到找到第一个比它小的项
        while position > 0 and arr[position - 1] > current_value:
            arr[position] = arr[position - 1]
            position = position - 1
        # 插入新项
        arr[position] = current_value

    return arr


s = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
print(s)
print(insert_sort(s))
# 结果如下：
[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]