冒泡排序的思想 python 冒泡排序、递归排序

2024-08-30 10:05:21

冒泡排序的时间复杂度是O(N^2)

冒泡排序的思想: 每次比较两个相邻的元素, 如果他们的顺序错误就把他们交换位置

比如有五个数: 12, 35, 99, 18, 76, 从大到小排序, 对相邻的两位进行比较

第一趟:
第一次比较: 35, 12, 99, 18, 76
第二次比较: 35, 99, 12, 18, 76
第三次比较: 35, 99, 18, 12, 76
第四次比较: 35, 99, 18, 76, 12

经过第一趟比较后, 五个数中最小的数已经在最后面了, 接下来只比较前四个数, 依次类推

第二趟
99, 35, 76, 18, 12
第三趟
99, 76, 35, 18, 12
第四趟
99, 76, 35, 18, 12
比较完成

冒泡排序原理: 每一趟只能将一个数归位, 如果有n个数进行排序,只需将n-1个数归位, 也就是说要进行n-1趟操作(已经归位的数不用再比较)

#!/usr/bin/env python

# coding:utf-8

def bubbleSort(nums):

    for i in range(len(nums)-1):    # 这个循环负责设置冒泡排序进行的次数

        for j in range(len(nums)-i-1):  # ｊ为列表下标

            if nums[j] > nums[j+1]:

                nums[j], nums[j+1] = nums[j+1], nums[j]

    return nums

nums = [5,2,45,6,8,2,1]

print bubbleSort(nums)

缺点: 冒泡排序解决了桶排序浪费空间的问题, 但是冒泡排序的效率特别低

来自：http://www.cnblogs.com/qlshine/p/6017957.html

递归排序：

def func(lt=[]):

    if len(lt)<=1:

        return lt

    key = lt[0]

    lt_l = []

    lt_r = []

    lt_m = []

    for i in lt:

        if i < key:

            lt_l.append(i)

        elif i > key:

            lt_r.append(i)

        else:

            lt_m.append(i)

    lt_l = func(lt_l)

    lt_r = func(lt_r)

    return lt_l+lt_m+lt_r

lt = [12,34,2,5,8,9,1,6]

print(func(lt))

　　

最新文章

热门文章