内容字号:默认大号超大号

段落设置:段首缩进取消段首缩进

字体设置:切换到微软雅黑切换到宋体

Python实现冒泡排序/选择排序/插入排序/快速排序和堆排序

2018-09-11 22:04 出处:清屏网 人气: 评论(0

冒泡排序

  • 时间复杂度: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(li, left, right):
    temp = li[left]

    while left < right:
        while li[right] > temp:
            right -= 1
        li[left] = li[right]

        while li[left] < temp:
            left += 1
        li[right] = li[left]

    li[left] = temp

    return left

def quickSort(li, left, right):
    if left < right:
        mid = partition(li, left, right)
        quickSort(li, left, mid - 1)
        quickSort(li, mid + 1, right)


li = [345, 456, 68.435, 1, 6, 4, 568, ]
partition(li, 0, (len(li) - 1))
quickSort(li, 0, (len(li) - 1))
print(li)

堆排序

  • 时间复杂度: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
分享给小伙伴们:
本文标签: 冒泡排序Python

相关文章

发表评论愿您的每句评论,都能给大家的生活添色彩,带来共鸣,带来思索,带来快乐。

CopyRight © 2015-2016 QingPingShan.com , All Rights Reserved.

清屏网 版权所有 豫ICP备15026204号