20191209-八大排序之冒泡排序

Happyunlimited 2019-12-09

1. 冒泡排序

算法核心思想

在数组arr[n]中,从第一个数开始,拿arr[i]和后面的数arr[i+1]进行比较,如果arr[i]比后面的大,就交换两个数的位置,这样遍历一遍数组后,把最大的数据排在了最后面,之后继续循环排剩下的n-1个数,直到完成所有的排序,由于每次都是把最大的排到最后面,就好像冒泡一样,故取名冒泡排序,具体执行逻辑如下:

  1. 取第一个数和后面第二个数到第n个数比较大小,如果位置错误交换位置,一轮结束后最大的值在第n个位置
  2. 取第一个数和后面第二个到第n-1个数比较大小,如果位置错误交换位置,一轮结束后第二大的值在第n-1个位置
  3. 取第一个数和后面第二个到第n-i个数比较大小,如果位置错误交换位置,一轮结束后第i大的值在第n-i个位置
  4. 重复上诉步骤直至排序结束

代码实现

def bubbleSort(arr):
    for i in range(len(arr)):
        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

执行解析

使用两层for循环,外层控制比较的轮数,内层进行具体比较,len(arr)-i-1每一轮比较减少一个数即第一轮比较n个数,第二轮比较n-1个数,第n个数不参与比较,因为第一轮排序已经将最大的数放置在第n个位置

总结

冒泡排序是一种相对较容易理解的排序算法,最坏的情况下时间复杂度为O(n2)

相关推荐

ustbfym / 0评论 2019-11-02