排序算法介绍——冒泡排序+插入排序+选择排序

Sally ·

更新时间:2024-09-20

· 703 次阅读

冒泡排序 相邻元素两两进行比较，每次比较结束都得到数组中最大的元素

#冒泡排序
def bubblesort(bubbleList):
    #外层循环，整个数组的长度
    flag = True
    n = len(bubbleList)
    while(n):
        #内层循环，相邻两个数之间进行比较
        #比如四个数字两两比较只需要3次，所以要减一
        for i in range(n-1):
            #从小到大排序：前一个＞后一个，则交换
            if bubbleList[i]>bubbleList[i+1]:
                bubbleList[i],bubbleList[i+1] = bubbleList[i+1],bubbleList[i]
                flag = False
        #用于优化时间复杂度
        if flag:
            break
        n -= 1
    return bubbleList
if __name__ == '__main__':
    bubbleList = [5,7,3,6,9,8]
    bubbleList = bubblesort(bubbleList)
    print(bubbleList)
#时间复杂度：外层循环是n,内层循环是n,所以是O(n*n)
#空间复杂度：因为只是进行一个比较操作，所以是O(1)
#该算法是稳定的

插入排序 从第二个元素开始插入，每次插入都需要和之前的元素进行比较。

# 插入排序
def insertion_sort(Insertion_List):
    n = len(Insertion_List)
    #插入元素时从第二个元素开始比较
    for i in range(1,n):
        key = Insertion_List[i]
        #寻找当前元素前面的元素进行比较
        j = i - 1
        #依次将当前元素的前面元素与当前元素进行比较
        while j>=0 and Insertion_List[j]>key:
            Insertion_List[j+1] = Insertion_List[j]
            j -= 1
        #将当前元素插入之前的序列当中
        Insertion_List[j+1] = key
    return Insertion_List
if __name__ == "__main__":
    Insertion_List = [4,3,1,5,2]
    Insertion_List = insertion_sort(Insertion_List)
    print(Insertion_List)
#时间复杂度：O(n*n)
#空间复杂度：O(1)
#稳定

选择排序

# 插入排序
#思路：i(0-len(s)),依次选择i为最小值的下表，与后续的元素相比较
#直到找到整个数组中的最小值，交换位置
def select_sort(select_List):
    n = len(select_List)
    for i in range(n):
        #这里采用的是最小值的下标
        min_num = i
        for j in range(i+1,n):
            if select_List[j] <select_List[min_num]:
                min_num = j
        #交换：将最小值与当前位置的值交换
        select_List[min_num],select_List[i] = select_List[i],select_List[min_num]
    return select_List
if __name__ =='__main__':
    select_List = [4,2,3,5,9,8,7,6]
    select_List = select_sort(select_List)
    print(select_List)
# 时间复杂度：O(n*n)
#空间复杂度：O(1)
#不稳定

作者：科研小白

选择排序选择冒泡排序插入排序排序算法算法排序