精华内容
下载资源
问答
  • Python 排序算法

    千次阅读 2017-12-12 15:26:34
    冒泡排序、简单选择排序、插入排序、希尔排序、快速排序

    一、冒泡排序

    原理:循环第一次找最小的,逐步交换到第一个位置,循环第二次找第二小,逐步交换到第二个位置...直到遍历完整个数组即可。

    def bubble_sort(p_list):
        for i in range(len(p_list)):
            for j in range(len(p_list) - 1, i, -1):
                if p_list[j] < p_list[j - 1]:
                    p_list[j], p_list[j - 1] = p_list[j - 1], p_list[j]

    二、选择排序

    原理:与冒泡排序本质相同,区别在每次循环中,找到剩余元素中的最小值时,一次交换到最终位置

    def select_sort(p_list):
        for i in range(len(p_list)):
            min_id = i
            for j in range(i + 1, len(p_list)):
                if p_list[min_id] > p_list[j]:
                    min_id = j
            if min_id != i:
                p_list[i], p_list[min_id] = p_list[min_id], p_list[i]


    三、直接插入排序

    原理:将数组分为左右两部分,左边默认为有序序列,右边为无序序列,初始时,左边序列只有第一元素;

    遍历右边所有元素将其按照大小逐步移动到左边序列中去,每次遍历的元素实际上都是无序序列中的第一个元素,其左边既是有序序列中最后一个元素。

    def insert_sort(p_list):
        for i in range(1, len(p_list)):
            for j in range(i, 0, -1):
                if p_list[j] < p_list[j - 1]:
                    p_list[j], p_list[j - 1] = p_list[j - 1], p_list[j]

    四、希尔排序

    原理:提供一个增量序列,在遍历数组,进行比较时,两个元素间id的差值由增量序列来提供,并且每次都将与当前元素的id差值为增量整数倍的元素进行比较;

    最后一个增量总是1;增量序列为递减的;增量序列长度太小会导致无法准确排序。

    
    
    def shell_sort(p_list):
        increment = len(p_list)
        while increment > 1:
            increment = int(increment / 3) + 1
            for i in range(increment, len(p_list), 1):
                for j in range(i, 0, -increment):
                    if p_list[j] < p_list[j - increment]:
                        p_list[j], p_list[j - increment] = p_list[j - increment], p_list[j]

    五、快速排序

    原理:基于二分和递归的思想,选择一个基准数,通过移动元素使在待排序数组中,其左边元素都比它小,右边元素都比它大;

    然后将左右两边分别再进行快速排序即可。

    def quick_sort(p_list):
        quick_div(p_list, 0, len(p_list) - 1)
    
    
    def quick_div(p_list, p_start, p_end):
        if p_start < p_end:
            mid_id = quick_part(p_list, p_start, p_end)
            quick_div(p_list, p_start, mid_id - 1)
            quick_div(p_list, mid_id + 1, p_end)
    
    
    def quick_part(p_list, p_start, p_end):
        part_key = p_list[p_start]
        while p_start < p_end:
            while p_start < p_end and p_list[p_end] > part_key:
                p_end -= 1
            p_list[p_end], p_list[p_start] = p_list[p_start], p_list[p_end]
            while p_start < p_end and p_list[p_start] < part_key:
                p_start += 1
            p_list[p_end], p_list[p_start] = p_list[p_start], p_list[p_end]
        return p_start

    展开全文
  • Python排序算法汇总

    千次阅读 2019-07-02 08:36:09
    一、排序介绍 第一篇给大家介绍排序的相关概念:比较性、稳定性、复杂度,让大家对排序有一个简单的认识。...因快排的重要性,所以单独拿出来讲,快排是面试or考试中最高频的一种排序算法,它是分而治之的算法...

    点击对应标题即可跳转相应文章

    一、排序介绍

    第一篇给大家介绍排序的相关概念:比较性、稳定性、复杂度,让大家对排序有一个简单的认识。

    二、Python实现五种排序

    分别从过程图解、算法思想、代码实现和算法分析四个方向介绍如何使用Python实现 冒泡、选择、插入、希尔、归并五种排序。

    三、一行代码实现快排

    因快排的重要性,所以单独拿出来讲,快排是面试or考试中最高频的一种排序算法,它是分而治之的算法思想,对大规模数据排序效果很好,但是对基本有序的数据集效率没有插入排序高,所以快排优化方案:
    对大规模数据先用快排,然后用插入排序。

    四、实测这几种排序性能

    上面为大家介绍了6种排序:冒泡、选择、插入、希尔、归并、快排。

    那这6种排序到底谁最快?猪哥设计实验实测了一把!想知道结果的同学自己查看文章哦!

    五、其他排序
    猪哥目前只为大家详细介绍了Python实现六种排序算法,还有四种排序算法以后有机会再给大家介绍吧!
    在这里插入图片描述

    展开全文
  • Python排序算法与快速排序

    千次阅读 2020-08-19 10:47:19
    排序算法 import random import time 冒泡排序 arr = [5, 2, 1, 3, 8, 6]*1000 def bubble_sort(): for i in range(len(arr) - 1): for j in range(1, len(arr) - i): # j-1和j进行比较 if arr[j - 1] > ...

    排序算法

    import random
    import time
    

    冒泡排序

    arr = [5, 2, 1, 3, 8, 6]*1000
    
    def bubble_sort():
        for i in range(len(arr) - 1):
            for j in range(1, len(arr) - i):
                # j-1和j进行比较
                if arr[j - 1] > arr[j]:
                    # 交换
                    arr[j - 1], arr[j] = arr[j], arr[j - 1]
    
    bubble_sort()
    print(arr)
    

    选择排序

    arr = list(range(1, 1000))
    random.shuffle(arr)
    
    def select_sort():
            # 选择次数 n-1
            for i in range(len(arr) - 1):
                # 找i及以后的位置中最小的位置
                min_index = i
                # 扫描i以后的序列中是否存在更小的位置
                for j in range(i + 1, len(arr)):
                    if arr[j] < arr[min_index]:
                        min_index = j
                # 判断最小位置和当前位置是否恰好重合
                if i != min_index:
                    arr[i], arr[min_index] = arr[min_index], arr[i]
    
    

    插入排序

    def insert_sort():
            for i in range(1, len(arr)):
                # 为arr[i]找到一个插入位置
                # 监视哨
                temp = arr[i]
    
                # 待插入的位置
                insert_index = i
        
                # 向前判断
                while insert_index > 0 and temp < arr[insert_index - 1]:
                    arr[insert_index] = arr[insert_index - 1]
                    insert_index -= 1
        
                # 插入数据
                arr[insert_index] = temp
    

    非原地快排

     def quick_sort1(sort_arr: list):
            """
            进行列表的划分 将列表划分为左 中 右
            :param sort_arr:待划分的列表
            :return: 最终的连接左中右的列表
            """
            if len(sort_arr) <= 1:
                return sort_arr
            # 准备三个列表 左 中 右
            less, pivot, right = [], [sort_arr[0]], []
    
            # 循环1-末尾
            for i in range(1, len(sort_arr)):
                if sort_arr[i] < pivot[0]:
                    less.append(sort_arr[i])
                elif sort_arr[i] == pivot[0]:
                    pivot.append(sort_arr[i])
                else:
                    right.append(sort_arr[i])
        
            # 返回划分结果
            return quick_sort1(less) + pivot + quick_sort1(right)
    

    原地排序

      def quick_sort2(start: int, end: int):
            """
            将序列的一部分划分为左小右大
            :param start: 序列的起始位置
            :param end: 序列的结束位置
            :return: None
            """
            if start < end:
                s = start
                e = end
                # 临界值在的一端的标识
                # True:临界值在s端  False:临界值在e端
                flag = True
    
                while s != e:
                    if arr[s] > arr[e]:
                        arr[s], arr[e] = arr[e], arr[s]
                        # 临界值:从s端变为e端  e端变为s端
                        flag = not flag
                    # 移动s或e
                    if flag:
                        e -= 1
                    else:
                        s += 1
        
                # 继续将左边的部分再划分
                quick_sort2(start, e - 1)
                # 继续将右边的部分再划分
                quick_sort2(s + 1, end)
    
    
       # print(arr)
            s = time.time()
            # select_sort()
            # insert_sort()
            # quick_sort1(arr)
            # arr.sort()
            quick_sort2(0, len(arr) - 1)
            print(time.time() - s)
            print(arr)
    
    

    折半查找

    import random
        
        arr = [random.randint(1, 100) for i in range(50)]
        
        
        def binary_search(s_list, key):
            # 定义起始和结束
            start = 0
            end = len(s_list) - 1
        
            while start <= end:
                # 中间位置:
                mid = (start + end) // 2
                if s_list[mid] == key:
                    return mid
                elif key > s_list[mid]:
                    # 修改start的值
                    start = mid + 1
                else:
                    end = mid - 1
            # 未找到
            return -1
        
        
        arr.sort()
        print(arr)
        print(binary_search(arr, 19))
    
    
    展开全文
  • Python排序算法:插入排序

    千次阅读 2018-05-31 00:05:12
    插入排序(Insertion Sort)是一种简单直观的排序算法。 通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。 插入排序在实现上,在从后向前的扫描过程中,需要把已排序元素...


    什么是插入排序

    插入排序(Insertion Sort)是一种简单直观的排序算法。
    通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
    插入排序在实现上,在从后向前的扫描过程中,需要把已排序元素逐步向后挪位,为最新元素提供插入空间。

    插入排序动图

    (用MD写的,插入的动图貌似是不会动了。。。。)
    从第二位开始,依次和前面的数进行比较,第一位默认已经是有序的了;
    第三位和前两位依次比较,第四位和前三位依次比较;
    前面的元素均为有序,后面为无序;
    即:
    先将前两个排序
    再将前三个排序
    前四个

    一直到最末尾




    代码实现

    def insertion_sort(list):
        n = len(list)
        for i in range(1,n):
            for j in range(i,0,-1):
                if list[j] < list[j-1]:
                    list[j],list[j-1] = list[j-1],list[j]
                else:
                    break
        return list




    解析

    def insertion_sort(list):
        n = len(list)
        for i in range(1,n):

    首先,得到数据的长度后,开始从 1 遍历整个数据(从 1 开始而不是从 0 开始),因为第一个元素已经是有序的了,所以不用再排序了。

    def insertion_sort(list):
        n = len(list)
        for i in range(1,n):
            for j in range(i,0,-1):
                if list[j] < list[j-1]
                    list[j],list[j-1] = list[j-1],list[j]

    从当前元素开始依次往前扫描
    判断与前一位相比大小




    优化插入排序

    上面的代码中,交换操作很费操作步骤,因为一次交换,相当于 3 次复制,这还不包括内部的函数过程。所以我们可以根据这点进行优化,把原本交换操作,改成赋值语句。

    def insertion_sort(list):
        n = len(list)
        for i in range(1, n):
            key = list[i]
            j = i - 1
            while j >= 0 and list[j] > key:
                list[j+1] = list[j]
                j -= 1
            list[j+1] = key
        return list
    
    list1 = [5,6,2,7,9,0,1,3,8,4]
    print("原列表:%s" %list1)
    insertion_sort(list1)
    print("排序后列表:%s" %list1)
    
    >> 原列表:[5, 6, 2, 7, 9, 0, 1, 3, 8, 4]
       排序后列表:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

    优化后代码解析

    def insertion_sort(list):
        n = len(list)
        for i in range(1, n):
            key = list[i]
            j = i - 1

    首先,遍历列表每一位,然后用 key 保存当前位置的值; j 表示前一位;

    def insertion_sort(list):
        n = len(list)
        for i in range(1, n):
            key = list[i]
            j = i - 1
            while j >= 0 and list[j] > key:

    然后,使用 while 条件循环,判断前一位的元素是否比当前位的大,并且前一位的下标 >= 0(即最小到第一位)
    这样就可以有条件的进行循环,而不像原来的写法那样一个个循环遍历。

    def insertion_sort(list):
        n = len(list)
        for i in range(1, n):
            key = list[i]
            j = i - 1
            while j >= 0 and list[j] > key:
                list[j+1] = list[j]
                j -= 1
            list[j+1] = key
        return list

    符合条件后,就可以把原来的元素位进行赋值操作,赋值成较大的元素;然后依次将较大的元素赋值给相比较的两位中的后面一位。直至比较到第一位或比较到某位元素小于当前元素的值。将保存起来的该位的值插入即可。

    例:list = [1,4,5,3]
    - 1循环 i 到第四位了 (i = 3)
    - key保存 list[3] 的值,即 key = 3
    - 然后将 list[2] 与 key = 3 比较,5>3,则将5的值赋给后面那位,即[1,4,5,5]
    - 再将 list[1] 与 key = 3 比较 ,4>3,则将4的值赋给后面那位,即[1,4,4,5]
    - 再将 list[0] 与 key = 3 比较 ,1<3,不符合循环条件
    - 于是执行后面的语句,将 key = 3 值赋给 list[0+1] 即list[1],即[1,3,4,5]




    补小知识点

    range()函数

    补个range()函数小知识点:

    生成顺序的:

    for i in range(1,10,1)
        print(i)
    
    >> 1,2,3,4,5,6,7,8,9

    生成倒序的:

    for i in range(10,0,-1)
        print(i)
    
    >> 10,9,8,7,6,5,4,3,2,1

    因为 顾头不顾尾 ,所以生成的数减到 1 即停止了,不包括 0 。

    & 和 and

    优化后的代码,while 条件使用了两个条件与的判断
    最初使用了 & 运算符,结果导致始终进不了循环,然后改为 and 即正常

    运算符 名称 说明 例子
    & 按位与 数的按位与 5&3 得1
    and 布尔“与” 如果x为False,x and y返回False,否则它返回y的计算值 x = False; y = True; x and y,由于x是False,返回False。在这里,Python不会计算y,因为它知道这个表达式的值肯定是False(因为x是False)。这个现象称为短路计算
    展开全文
  • Python排序算法之归并排序

    千次阅读 2019-05-15 20:51:42
    归并排序 归并排序是采用分治法的典型应用,分治法的思想就是先递归分解数组,再合并数组。将数组分解为最小之后再合并两个有效数组,其基本...算法实现 # -*- coding: utf-8 -*- def merge_sort(array): "...
  • Python排序算法(一)冒泡排序、选择排序、插入排序

    千次阅读 多人点赞 2018-09-18 11:16:26
    今天总结一下Python中的排序算法。这篇文章有的排序算法是:冒泡排序、选择排序、插入排序。 冒泡排序 先看一下代码。 ''' 冒泡排序 ''' def bubble_sort(aList): n = len(aList) for i in range(0, n - 1): ...
  • 冒泡排序是一种简单的排序算法,它重复地遍历要排序的数组,一次比较两个元素,如果顺序错误就把它们交换过来。由于最大的元素经过交换会慢慢“浮”到数列的顶端,因此叫作冒泡排序。 冒泡排序的算法运作流程: ...
  • 提示:写完文章后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 系列文章目录 前言 一、pandas是什么?... 1.... 2....原理就不在这里说了,... 由于快排是不稳定的排序算法,且平均时间复杂度为O(nlog...
  • python算法源码之排序(附源码)1. 算法认识2. 冒泡排序3. 选择排序4. 插入排序5. 归并排序6.快速排序7.计数排序 1. 算法认识 1.算法是指解决问题的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统...
  • for i in range(n): print('Hello World’) for j in range(n): print('Hello World')
  • Python排序算法(二)——冒泡排序

    千次阅读 2019-04-28 21:39:00
    有趣的事,Python永远不会缺席!... 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列,依次比较两个相邻的元素,一层一层的将较大的元素往后移动...
  • 冒泡排序算法的原理如下: 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。 针对所有...
  • [Python笔记]部分经典排序的实现0、部分排序算法相关术语1、选择排序 Selection sort2、插入排序 Insertion sort3、冒泡排序 Bubble sort4、快速排序 Quick sort5、归并排序 Merge sort 0、部分排序算法相关术语 (1...
  • 带你掌握4种Python 排序算法

    千次阅读 2021-06-24 09:44:04
    摘要:在编程里,排序是一个重要算法,它可以帮助我们更快、更容易地定位数据。在这篇文章中,我们将使用排序算法分类器对我们的数组进行排序,了解它们是如何工作的。
  • # 算法2 de # 算法3

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 109,266
精华内容 43,706
关键字:

python排序算法

python 订阅