HTML框架 docker安装部署 ISP iphone string plot encoding redis常用语句 notifications vue的钩子函数 nginx视频 jq触发点击事件 java算法培训 less的比较级 linux全局搜索文件 js控制台打印 java 注解 python入门 pythonsocket编程 python3正则表达式 java教学 java使用 java类的继承 java匿名对象 java自学编程入门教程 java输出当前时间 javac java调用接口 java删除 java常用数据结构 java中的泛型 音频录制软件 微信超级好友 workflow中文 图片生成网址 kontakt iar下载 phpword 汽车配件查询软件 cubase下载
当前位置: 首页 > 学习教程  > 编程语言

图解排序

2020/8/11 20:33:34 文章标签:

图解排序

    • 常见排序
      • 1.插入排序
        • 1.1图解a
        • 1.2图解b
        • 1.3图解c
        • 1.4时间复杂度
        • 1.5 改进思路
        • 1.6 代码实现
      • 2.选择排序
        • 2.1图解a
        • 2.2图解b
        • 2.3时间复杂度
        • 2.4 改进思路
        • 2.5 代码实现
      • 3.交换排序
        • 3.1气泡(冒泡)排序
          • 3.1.1图解a
          • 3.1.2时间复杂度
          • 3.1.3改进思路
          • 3.1.4代码实现
        • 3.2快速排序
        • 3.2.1图解a
        • 3.2.2时间复杂度
        • 3.2.3改进思路
        • 3.3.3代码实现
      • 4.归并排序
        • 4.1二路归并
          • 4.1.1图解a
          • 4.1.2图解b
          • 4.1.3图解c
          • 4.1.4时间复杂度
          • 4.1.5改进思路
          • 4.1.6代码实现
      • 5.总结

本文将以图片的形式对常用的插入排序、选择排序、冒泡排序、快速排序、归并排序进行介绍,加以简单分析,对自己学习的一个总结的同时,希望能够帮助到正在学习的同学。若有不对之处,还请各位指正。

声明:本文中的图片来自于网络侵删,本文仅用于学习交流。

img

常见排序

1.插入排序

1.1图解a

图片来源于GeeksForGeeks

1.2图解b

img

1.3图解c

img

1.4时间复杂度

外层循环,内层比较。
O(n2) O(n^2)

1.5 改进思路

插入的时候,用二分查找去寻找插入的位置。

1.6 代码实现

尽供参考

def isnert_sorted(lit):
    for i in range(1,len(lit)):
        j = i
        key = lit[i]
        while lit[j] < lit[j-1] and j > 0:
            lit[j],lit[j-1] = lit[j-1],lit[j]
            j -= 1
        else:
            lit[j] = key
    return lit

2.选择排序

2.1图解a

img

2.2图解b

img

2.3时间复杂度

外层循环,每一个元素,内层循环,比较找最小。
O(n2) O(n^2)

2.4 改进思路

利用树的结构去存储数据。

  • 堆排序:也属于选择排序
  • 思路:每次与将子节点与父节点进行对比,直到所有的父节点都比子节点的值大,形成大根堆。

img

  • 时间复杂度:
    O(nlog2n) O(nlog_2n)

2.5 代码实现

仅供参考

下面代码中,用了另一个列表去接受最小值。可改进在原来的列表中。

def select_sort(lst):
    a = []
    for i in range(len(lst)):
        min_num = lst[i]
        for j in range(i,len(lst)):
            if lst[j] < min_num:
                min_num = lst[j]
        a.append(min_num)
    return a

3.交换排序

3.1气泡(冒泡)排序

3.1.1图解a

img

3.1.2时间复杂度

外层循环,每一个元素,内层循环,n-1次的比较。
O(n2) O(n^2)

3.1.3改进思路
  • 每一次的内层循环都是列表长度,可以添加辅助变量,检查上一次是否存在交换。辅助变量没有变,5也就意味着辅助变量以后已排好序。
  • 交错起泡,从左至右,然后从右至左。
3.1.4代码实现

仅供参考

def bubble_sort(lst):
    for i in range(len(lst)-1):
        if lst[i] > lst[i+1]:
            lst[i+1], lst[i] = lst[i], lst[i+1]
    return lst

3.2快速排序

3.2.1图解a

img

3.2.2时间复杂度

从两端开始比较,速度加快。
O(nlog2n) O(nlog_2n)

3.2.3改进思路

1.当原本数据有序时(不够乱),会影响快排。

3.3.3代码实现

# 该处的代码来自菜鸟教程的快速排序
def quickSort(arr, left=None, right=None):
    left = 0 if not isinstance(left,(int, float)) else left
    right = len(arr)-1 if not isinstance(right,(int, float)) else right
    if left < right:
        partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex-1)
        quickSort(arr, partitionIndex+1, right)
    return arr

def partition(arr, left, right):
    pivot = left
    index = pivot+1
    i = index
    while  i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index+=1
        i+=1
    swap(arr,pivot,index-1)
    return index-1

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

4.归并排序

4.1二路归并

4.1.1图解a

4.1.2图解b

4.1.3图解c

4.1.4时间复杂度

O(nlog2n) O(nlog_2n)

4.1.5改进思路

1.选择多路进行排序

4.1.6代码实现
# 该处的代码来自菜鸟教程的归并排序
def mergeSort(arr):
    import math
    if(len(arr)<2):
        return arr
    middle = math.floor(len(arr)/2)
    left, right = arr[0:middle], arr[middle:]
    return merge(mergeSort(left), mergeSort(right))

def merge(left,right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0));
    while left:
        result.append(left.pop(0))
    while right:
        result.append(right.pop(0));
    return result

5.总结

img


本文链接: http://www.dtmao.cc/news_show_100367.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?