专栏首页马一特排序算法与查找算法

排序算法与查找算法

排序算法

冒泡排序

  • 时间复杂度:O(n²)
  • 空间复杂度:O(1)
  • 健壮性:健壮
  • 难易程度:简单
def bubbleSort(li):
    for i in range(len(li) - 1):
        for j in range(len(li) - i - 1):
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]

li = [345, 456, 68.435, 1, 6, 4, 568, ]
bubbleSort(li)
print(li)

选择排序

  • 时间复杂度:O(n²)
  • 空间复杂度:O(1)
  • 健壮性:健壮
  • 难易程度:简单
def selectSort(li):
    for i in range(len(li) - 1):
        min = I  # 选择一个小的来比较
        for j in range(i + 1, len(li)):
           if li[min] > li[j]:
               li[min], li[j] = li[j], li[min]

li = [345, 456, 68.435, 1, 6, 4, 568, ]
selectSort(li)
print(li)

插入排序

  • 时间复杂度:O(n²)
  • 空间复杂度:O(1)
  • 健壮性:健壮
  • 难易程度:较复杂
def insertSort(li):
    for i in range(len(li) - 1):
        temp = li[i]
        j = i - 1
        while j >= 0 and li[j] > temp:
            li[j + 1] = li[j]
            j = j - 1
        li[j + 1] = temp


li = [345, 456, 68.435, 1, 6, 4, 568, ]
insertSort(li)
print(li)

快速排序

  • 时间复杂度:O(nlogn)
  • 空间复杂度:O(nlogn)
  • 健壮性:不稳定
  • 难易程度:复杂
# 二分左右
def partition(list_for_partition, left, right):
    # 中轴点
    pivot = list_for_partition[left]

    while left < right:
        while left < right and list_for_partition[right] >= pivot:
            right -= 1
        list_for_partition[left] = list_for_partition[right]
        while left < right and list_for_partition[left] <= pivot:
            left += 1
        list_for_partition[right] = list_for_partition[left]

    list_for_partition[left] = pivot
    return left


# 快速排序
def sort_quickly(list_for_partition, left, right):
    if left < right:
        pivot = partition(list_for_partition, left, right)

        sort_quickly(list_for_partition, left, pivot - 1)
        sort_quickly(list_for_partition, pivot + 1, right)
    return list_for_partition


# 输出结果
def output_sort_result(list_for_partition):
    return sort_quickly(list_for_partition, 0, len(list_for_partition) - 1)

堆排序

  • 时间复杂度:O(nlog₂n)
  • 空间复杂度:O(1)
  • 健壮性:不稳定
  • 难易程度: 困难
def heap_sort(array):
    def heap_adjust(parent):
        child = 2 * parent + 1  # left child
        while child < len(heap):
            if child + 1 < len(heap):
                if heap[child + 1] > heap[child]:
                    child += 1  # right child
            if heap[parent] >= heap[child]:
                break
            heap[parent], heap[child] = \
                heap[child], heap[parent]
            parent, child = child, 2 * child + 1

    heap, array = array.copy(), []
    for i in range(len(heap) // 2, -1, -1):
        heap_adjust(i)
    while len(heap) != 0:
        heap[0], heap[-1] = heap[-1], heap[0]
        array.insert(0, heap.pop())
        heap_adjust(0)
    return array

查找算法

顺序查找

二分查找

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 复杂网络是怎么应用于神经网络上

    从随机网络到无尺度网络,复杂性蕴含于万物之间的链接,我们看到在网络中,表面的无序和深层的有序共存。网络普遍具有先发优势、适者生存、健壮和脆弱并存的特...

    马一特
  • Python数据分析常用的库总结

    Python之所以能够成为数据分析与挖掘领域的最佳语言,是有其独特的优势的。因为他有很多这个领域相关的库可以用,而且很好用,比如Numpy、SciPy、Matp...

    马一特
  • 数据分析与数据挖掘 - 06线性代数

    导数是高等数学中非常重要的知识点,也是人工智能的算法应用中比较常用的一个知识,这一章我们的重点就是讲解一下导数和其求导法则。首先我们来看一下导数的基本概念:函数...

    马一特
  • JQuery高级

    列一个变量,存储正则规则,用这个变量去test某个数据-----匹配True和不匹配False

    小闫同学啊
  • Emmet语法

    $ :占位符(显示有多少位),$默认从1开始递增 @ : @-从最高位开始递减,@10从10开始递增

    链上世界
  • 详解:兄弟们,这个不懂,li嵌套,我懂再写哈

    俺的问题? 俺搞不清一行四个哪里,为什么一行四个中第三个为1为什么? 俺理解的是兄弟元素第二是也就是

    用户7873631
  • bootstrap 多内容页脚

    用户5760343
  • 移动端导航简单实现

    在移动端导航的功能太常见了,很多时候还需要可滑动,点击的时候还需要当前动画到中间。实现的方法很多,今天分享一个本人最近开发所用的方法。

    wade
  • 第42天:焦点图

    半指温柔乐
  • 你真的理解HTML5标签语义化吗?

    <head>标签用于定义文档的头部,它是所有头部元素的容器。<head>描述了文档的各种属性和信息,包括文档的标题、在 Web 中的位置以及和其他文档的关系等。...

    陈大鱼头

扫码关注云+社区

领取腾讯云代金券