" name="sm-site-verification"/>
侧边栏壁纸
博主头像
PySuper博主等级

千里之行,始于足下

  • 累计撰写 203 篇文章
  • 累计创建 14 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

冒泡排序、选择排序、插入排序

PySuper
2021-03-17 / 0 评论 / 0 点赞 / 8 阅读 / 3781 字
温馨提示:
所有牛逼的人都有一段苦逼的岁月。 但是你只要像SB一样去坚持,终将牛逼!!! ✊✊✊

冒泡排序

时间复杂度:an^2 + bN + 1 (固定时间的操作,都是O(1))–> O(N^2)

额外空间复杂度:O(1)

注册
class ChangeBubbleSort(object):
    def sorted(self, arr: []):
        """
        冒泡排序
        :param arr: 无序列表
        :return: 排序后的列表
        """
        if len(arr) < 2 or arr is not None:
            for i in range(len(arr) - 1):
                for j in range(len(arr) - i - 1):
                    if arr[j] > arr[j + 1]:
                        arr[j], arr[j + 1] = arr[j + 1], arr[j]
        return arr


list_ = [2, 4, 3, 5, 7, 6, 9, 8]
sort_arr = ChangeBubbleSort().sorted(list_)
print(sort_arr)

选择排序

时间复杂度–> O(N^2)

额外空间复杂度O(1)

注册
class SelectionSort(object):
    def sort(self, arr: []):
        """
        选择排序,主要是记录最小值的缩影
        :param arr: 无序数列
        :return: 有序数列
        """
        if len(arr) > 2 or arr is not None:
            for i in range(len(arr) - 1):
                min_index = i

                # 重点:从头部开始,尾部不动 ==> 过程中i不变,j增加
                for j in range(i + 1, len(arr)):
                    # 每一次都找到最小的,替换min_index,最后替换最小值和当前i的数值
                    # if arr[j] < arr[min_index]:
                    #     min_index = j
                    min_index = j if arr[j] < arr[min_index] else min_index
                arr[i], arr[min_index] = arr[min_index], arr[i]
        print(arr)


list_ = [2, 4, 3, 5, 7, 6, 9, 8]
SelectionSort().sort(list_)

插入排序

时间复杂度:O(N^2)

额外空间复杂度:O(1)

注册
class InsertionSort(object):
    def sort(self, arr: []):
        """
        插入排序:(选择排序、冒泡排序是不考虑数列情况的,是否有排序)
            最好情况: O(N)
            最差情况: O(N^2)
            平均情况, 都按照最差的情况来算 O(N^2)
        """
        if len(arr) > 2 or arr is not None:

            # 这里从第2个数开始(index=1), 0~i-1上已经有序
            for i in range(1, len(arr)):

                # 第二个循环,是向前比较
                index = i
                while index > 0 and arr[index - 1] > arr[i]:
                    arr[index], arr[index - 1] = arr[index - 1], arr[index]
                    index -= 1
        print(arr)


list_ = [2, 4, 3, 5, 7, 6, 9, 8]
InsertionSort().sort(list_)
0
  1. 支付宝打赏

    qrcode alipay
  2. 微信打赏

    qrcode weixin

评论区