python排序

1.冒泡排序

def bubble_sort(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

if __name__ == "__main__":

    data = [1,2,5,2,99,3,67,45,12,4,78,90]

    date = bubble_sort(data)

    print(date)

---

关于冒泡排序的时间复杂度，在上面python实现的代码中时间复杂度是 ，当然可以再考虑一下极端的情况：当队列已经从小到大排好序或者从大到小排好序，从小到大排好顺序时可以只扫描一遍就结束排序，此时时间复杂度为O(n)，如果是从大到小，那么就需要扫描n-1次，同时需要比较交换n-1次，时间复杂度为 。

2.选择排序算法

def select_sort(items):

    n = len(items)

    for cur in range(n-1):

      item_max = cur

      for i in range(cur+1, n):

          if items[i] > items[item_max]:

              items[i], items[item_max] = items[item_max], items[i]

      if item_max != cur:

          items[cur], items[item_max] = items[item_max], items[cur]

if __name__ == "__main__":

    a = [3,6,4,2,11,10,5]

    select_sort(a)

    print(a)

---

关于选择排序的时间复杂度：

选择排序的交换操作介于 0 和 (n - 1） 次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。