python如何实现常用的五种排序算法详解

一、冒泡排序

原理:

  1. 比较相邻的元素。如果第一个比第二个大就交换他们两个
  2. 每一对相邻元素做同样的工作,直到结尾最后一对
  3. 每个元素都重复以上步骤,除了最后一个

第一步:

将乱序中的最大值找出,逐一移到序列最后的位置

alist = [3, 5, 9, 2, 1, 7, 8, 6, 4]

def bubble_sort(alist):
    # 找最大值的方式是通过对列表中的元素进行两两比较,值大的元素逐步向后移动
    # 序列中有n个元素,两两比较的话,需要比较n-1次
    for i in range(len(alist) - 1):  # 循环n-1次,控制两两比较的次数
        if alist[i] > alist[i + 1]:
            # 如果前面的元素大于后面的元素,交换两个元素的位置,否则不做任何操作
            alist[i], alist[i + 1] = alist[i + 1], alist[i]

    return alist

print(bubble_sort(alist))

# 输出:最大值已经移动到最右边了
[3, 5, 2, 1, 6, 7, 8, 4, 9]

当上述代码已经可以将序列中的最大值放置到合适的位置,然后我们就可以将上述操作继续作用到 n-1 和元素对应的新序列,则就可以将 n-1 个元素对应的最大值放置到了 n-1 和元素的最后位置。

结论:发现如果将上述的操作逐步的作用 n-1 此就可以将整个序列变成有序的。

第二步:

将第一步的操作继续作用 n-1 次

alist = [3, 5, 9, 2, 1, 7, 8, 6, 4]

def bubble_sort(alist):

    for j in range(len(alist)-1):   # 外层循环次数递增,内层循环次数递减
        for i in range(len(alist) - 1-j):  # 循环次数需要递减-j,控制两两比较的次数
            if alist[i] > alist[i + 1]:
                # 如果前面的元素大于后面的元素,交换两个元素的位置,否则不做任何操作
                alist[i], alist[i + 1] = alist[i + 1], alist[i]

    return alist

print(bubble_sort(alist))

# 输出
[1, 2, 3, 4, 5, 6, 7, 8, 9]

二、选择排序

思路:

  1. 首先在序列中找到最大(小)元素,存放到序列的最后
  2. 在从剩余的序列元素中继续找最大(小)的元素,放到序列中上一个最大值的前一个位置
  3. 重复第二步,直到所有元素排序完毕

第一步:

将乱序中的元素两两比较,找出最大值,然后直接将最大值放置到序列最后的位置(将最大值直接和最后一个元素交换位置)

def select_sort(alist):
    max_index = 0  # 最大值元素的下标,一开始假设下标为0的元素为最大值
    for i in range(len(alist) - 1):  # 循环控制两两比较的次数
        # 如果在比较的过程中发现,下标为max_index不是最大值,那么就改变max_index
        if alist[max_index] < alist[i + 1]:
            max_index = i + 1

    # 循环结束后max_index就一定是最大值的下标,并且把该数和最后一个值做交换
    alist[len(alist) - 1], alist[max_index] = alist[max_index], alist[len(alist) - 1]
    return alist

alist = [3, 5, 9, 2, 1, 7, 8, 6, 4]
print(select_sort(alist))

# 输出
[3, 5, 4, 2, 1, 7, 8, 6, 9]

第二步:

将第一步继续作用 n-1 次

def select_sort(alist):
    for j in range(len(alist) - 1):# 外层循环递增n-1次
        max_index = 0  # 最大值元素的下标,一开始假设下标为0的元素为最大值
        for i in range(len(alist) - 1 - j):  # 内层循环递减,循环控制两两比较的次数
            # 如果在比较的过程中发现,下标为max_index不是最大值,那么就改变max_index
            if alist[max_index] < alist[i + 1]:
                max_index = i + 1

        # 循环结束后max_index就一定是最大值的下标,并且把该数和最后一个值做交换
        alist[len(alist) - 1 - j], alist[max_index] = alist[max_index], alist[len(alist) - 1 - j]
    return alist

alist = [3, 5, 9, 2, 1, 7, 8, 6, 4]
print(select_sort(alist))

三、插入排序

思路:

  • 需要将原始序列分为两个部分:有序部分、无序部分。
  • 将无序部分中的元素逐一插入到有序部分中

注意:初始情况下,有序部分为乱序序列中的第一个元素,无序部分为乱序序列的 n-1 个元素

例如:

# 乱序序列:[8,3,5,7,6]
[8,    3,5,7,6] # 8就是初始的有序部分,3、5、7、6就是初始的无序部分
[3,8,    5,7,6]
[3,5,8,    7,6]
[3,5,7,8,    6]
[3,5,7,6,8,   ]

第一步:

定义一个变量 i ,i 表示的是有序部分元素的个数和无序部分第一个元素小标

alist = [8, 3, 1, 6, 7]

i = 1  # i 就是有序部分元素的个数和无序部分第一个元素下标
# alist[i-1]:有序部分最后一个元素下标
# alist[i]:无序部分第一个元素下标
if alist[i - 1] > alist[i]:
    alist[i], alist[i - 1] = alist[i - 1], alist[i]
 # [3, 8,    1, 6, 7]

第二步:循环作用到每个元素中

alist = [8, 3, 1, 6, 7]

i = 2
# alist[i-1]:有序部分最后一个元素下标
# alist[i]:无序部分第一个元素下标
while i > 0:
    if alist[i - 1] > alist[i]:
        # 循环第一次时[3,1,8,   6,7]
        alist[i], alist[i - 1] = alist[i - 1], alist[i]
        i -= 1
        # 循环继续
        # [1,3,8,   6,7]
    else:
        break

第三步:

处理变量 i,需要让 i 进行自己递增

for i in range(1, len(alist)): # i = [1,2,3,4]
    # alist[i-1]:有序部分最后一个元素下标
    # alist[i]:无序部分第一个元素下标
    while i > 0:
        if alist[i - 1] > alist[i]:
            alist[i], alist[i - 1] = alist[i - 1], alist[i]
            i -= 1
        else:
            break

完整代码:

def insert_sort(alist):
    for i in range(1, len(alist)):
        while i > 0:
            if alist[i - 1] > alist[i]:
                alist[i - 1], alist[i] = alist[i], alist[i - 1]
                i -= 1
            else:
                break
    return alist

四、希尔排序

关键变量:增量gap

gap:初始值为 len(alist) // 2

  • 表示分组的组数
  • 每一组数据之间的间隔

插入排序就是增量为 1 的希尔排序

第一步:

将插入排序代码写出

def hill_sort(alist):
    for i in range(1, len(alist)):
        while i > 0:
            if alist[i - 1] > alist[i]:
                alist[i - 1], alist[i] = alist[i], alist[i - 1]
                i -= 1
            else:
                break
    return alist

第二步:

在插入排序代码中加入增量的概念

def hill_sort(alist):
    gap = len(alist) // 2  # 初识增量

    # 将插入排序中的增量1替换成gap
    # 由增量1变成了增量为gap了
    for i in range(gap, len(alist)):
        while i > 0:
            if alist[i - gap] > alist[i]:
                alist[i - gap], alist[i] = alist[i], alist[i - gap]
                i -= gap
            else:
                break
    return alist

第三步:

在第二步中进行增量的缩减(增量缩减到1结束)完整代码

def hill_sort(alist):
    gap = len(alist) // 2  # 初识增量

    while gap >= 1:
        for i in range(gap, len(alist)):
            while i > 0:
                if alist[i - gap] > alist[i]:
                    alist[i - gap], alist[i] = alist[i], alist[i - gap]
                    i -= gap
                else:
                    break
        gap //= 2  # 缩减增量
    return alist

五、快速排序

思路:

  1. 将列表中第一个元素设定为基准数字,赋值给mid变量,然后将整个列表中比基准小的数值放在基准的左侧,比基准大的数字放在基准右侧,然后将基准数字左右两侧的序列在根据此方法进行排放
  2. 定义两个指针,low 指向最左侧,high 指向最右侧
  3. 然后对最右侧指针进行向左移动,移动法则是,如果指针指向的数值比基准小,则将指针指向的数字移动到基准数字原始位置,否则继续移动指针。
  4. 如果最右侧指针指向的数值移动到基准位置时,开始移动最左侧指针,将其向右移动,如果该指针指向的数值大于基准侧将该数值移动到最右侧指针指向的位置,然后停止移动。
  5. 如果左右侧指针重复则,将基准放入左右指针重复的位置,则基准左侧为比其小的数值,右侧为比其大的数值

第一步:

核心操作,将基数 mid 放置到序列中间,使得基数左侧都是比它小的,右侧是比它大的

def quick_sort(alist):
    low = 0  # 第一个元素下标
    high = len(alist) - 1  # 最后一个元素下标

    mid = alist[low]  # 基数:初始值为序列中的第一个数值
    while low != high:
        # 先移动high
        while low < high:
            if mid < alist[high]:  # 下标high对应的值大于mid,high就向右偏移1
                high = high - 1
            else:
                # 否则,就把将high指向的数值放置到左侧下标为low对应的空位
                alist[low] = alist[high]
                break  # 传递后high下标偏移结束

        # 开始移动low
        while low < high:
            if mid > alist[low]:  # 下标low对应的值小于mid,low就向左偏移1
                low = low + 1
            else:
                # 否则,就把将low指向的数值放置到左侧下标为high对应的空位
                alist[high] = alist[low]
                break  # 并结束
    # 最后当low和high相等的时候,那么就把mid传给下标为low或high的位置
    alist[low] = mid
    return alist

alist = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
print(quick_sort(alist))

# 输出——>6左边都是比6小的,右边都是比6大的
[5, 1, 2, 4, 3,    6,    9, 7, 10, 8]

第二步:

将第一步的核心操作递归作用到基数的左右两侧的子序列中

# 那么如何区分根据基数拆分出的左右子序列呢?可以通过传入指定的left和right来指定不同的子序列
def quick_sort(alist, left, right):
    low = left  # 第一个元素下标
    high = right  # 最后一个元素下标

    if low > high:  # 递归结束条件,low是不能大于high的
        return

    mid = alist[low]  # 基数:初始值为序列中的第一个数值
    while low != high:
        # 先移动high
        while low < high:
            if mid < alist[high]:  # 下标high对应的值大于mid,high就向右偏移1
                high -= 1
            else:
                # 否则,就把将high指向的数值放置到左侧下标为low对应的空位
                alist[low] = alist[high]
                break  # 传递后high下标偏移结束
        # 开始移动low
        while low < high:
            if mid >= alist[low]:  # 下标low对应的值小于mid,low就向左偏移1
                low += 1
            else:
                # 否则,就把将low指向的数值放置到左侧下标为high对应的空位
                alist[high] = alist[low]
                break  # 并结束

    # 最后当low和high相等的时候,那么就把mid传给下标为low或high的位置
    if low == high:
        alist[low] = mid

    # 上述为核心操作,需要将核心操作递归作用到左右子序列中
    quick_sort(alist, left, low - 1)  # 递归到左侧序列中
    quick_sort(alist, high + 1, right)  # 递归到右侧序列中

    return alist

alist = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
print(quick_sort(alist, 0, len(alist) - 1))

# 输出
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

总结

到此这篇关于python如何实现常用的五种排序算法的文章就介绍到这了,更多相关python实现排序算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Python实现的数据结构与算法之快速排序详解

    本文实例讲述了Python实现的数据结构与算法之快速排序.分享给大家供大家参考.具体分析如下: 一.概述 快速排序(quick sort)是一种分治排序算法.该算法首先 选取 一个划分元素(partition element,有时又称为pivot):接着重排列表将其 划分 为三个部分:left(小于划分元素pivot的部分).划分元素pivot.right(大于划分元素pivot的部分),此时,划分元素pivot已经在列表的最终位置上:然后分别对left和right两个部分进行 递归排序. 其中

  • python 实现插入排序算法

    复制代码 代码如下: #!/usr/bin/python def insert_sort(array): for i in range(1, len(array)): key = array[i] j = i - 1 while j >= 0 and key < array[j]: array[j + 1] = array[j] j-=1 array[j + 1] = key if __name__ == "__main__": array = [2, 4, 32, 64,

  • python 算法 排序实现快速排序

    QUICKSORT(A, p, r)是快速排序的子程序,调用划分程序对数组进行划分,然后递归地调用QUICKSORT(A, p, r),以完成快速排序的过程.快速排序的最差时间复杂度为O(n2),平时时间复杂度为O(nlgn).最差时间复杂度的情况为数组基本有序的时候,平均时间复杂度为数组的数值分布较为平均的时候.在平时情况下快速排序跟堆排序的时间复杂度都为O(nlgn),但是快速排序的常数项较小,所以要优于堆排序. PARTITION(A, p, r) 复制代码 代码如下: x ← A[r]

  • python实现冒泡排序算法的两种方法

    什么是冒泡排序? 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法. 它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成. 这个算法的名字由来是因为越大的元素会经由交换慢慢"浮"到数列的顶端,故名冒泡排序. 以上是百度词条对冒泡排序的官方解释. 但是我要说一下我的个人理解,我觉得冒泡排序的核心思想是:每次比较两个数,如果他们顺序错误(大于或者小于),那么就把

  • python选择排序算法的实现代码

    1.算法:对于一组关键字{K1,K2,-,Kn}, 首先从K1,K2,-,Kn中选择最小值,假如它是 Kz,则将Kz与 K1对换:然后从K2,K3,- ,Kn中选择最小值 Kz,再将Kz与K2对换.如此进行选择和调换n-2趟,第(n-1)趟,从Kn-1.Kn中选择最小值 Kz将Kz与Kn-1对换,最后剩下的就是该序列中的最大值,一个由小到大的有序序列就这样形成. 2.python 选择排序代码: 复制代码 代码如下: def selection_sort(list2):    for i in

  • Python实现的直接插入排序算法示例

    本文实例讲述了Python实现的直接插入排序算法.分享给大家供大家参考,具体如下: # -*- coding:utf-8 -*- '''直接插入的python实现 时间复杂度O(n**2) 空间复杂度O(1) 稳定 思想:先将前两个元素排序,第三个元素插入前面已排好序列, 后面的元素依次插入之前已经排好序的序列 ''' author = 'Leo Howell' L = [89,67,56,45,34,23,1] def direct_insert_sort(numbers): for i in

  • python 实现归并排序算法

    理论不多说: 复制代码 代码如下: #!/usr/bin/python import sys def merge(array, q, p, r): left_array = array[q:p+1] right_array = array[p+1:r+1] left_array_num = len(left_array) right_array_num = len(right_array) i, j , k= [0, 0, q] while i < left_array_num and j <

  • python冒泡排序算法的实现代码

    1.算法描述:(1)共循环 n-1 次(2)每次循环中,如果 前面的数大于后面的数,就交换(3)设置一个标签,如果上次没有交换,就说明这个是已经好了的. 2.python冒泡排序代码 复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- def bubble(l):    flag = True    for i in range(len(l)-1, 0, -1):        if flag:             flag = False

  • python实现的各种排序算法代码

    复制代码 代码如下: # -*- coding: utf-8 -*-# 测试各种排序算法# link:www.jb51.net# date:2013/2/2 #选择排序def select_sort(sort_array):    for i, elem in enumerate(sort_array):        for j, elem in enumerate(sort_array[i:]):            if sort_array[i] > sort_array[j + i]

  • 基于python的七种经典排序算法(推荐)

    一.排序的基本概念和分类 所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作.排序算法,就是如何使得记录按照要求排列的方法. 排序的稳定性: 经过某种排序后,如果两个记录序号同等,且两者在原无序记录中的先后秩序依然保持不变,则称所使用的排序方法是稳定的,反之是不稳定的. 内排序和外排序 内排序:排序过程中,待排序的所有记录全部放在内存中 外排序:排序过程中,使用到了外部存储. 通常讨论的都是内排序. 影响内排序算法性能的三个因素: 时间复杂度:即时间性能,高效

随机推荐