排序算法(上)

Posted by Starrk的小屋 on February 10, 2020

冒泡算法

冒泡算法 简介

冒泡算法是种直观而又简单的算法,给定一组共有n个元素的序列,对序列中的每个相邻元素进行比较,若右边的大于左边则进行交换。在第一轮遍历后,序列中最大的元素会被置于末尾。总共遍历n-1轮。

对于有n个元素的序列,冒泡算法总共需要进行遍历序列:n + n-1 + n-2 + …. + 1 = \(\frac{(n+1)n}{2}\)

对于最好的情况,当序列都为正序:此时需要做0次交换

对于最差的情况,当序列都为逆序:此时需要做 n-1 + n-2 + …+ 1 = \(\frac{n(n-1)}{2}\) 次交换。

平均交换次数为:\(\frac{n(n-1)}{4}\)

显然时间复杂度为:O(\(n^2\))

空间复杂度:O(1)

冒泡排序代码

def buble_sort(unsorted_list):

    for i in range(len(unsorted_list)):
        #注意序列长度,此时索引j的范围需要-1
        for j in range(0,len(unsorted_list)-i-1):
            if(unsorted_list[j] > unsorted_list[j+1]):
                unsorted_list[j],unsorted_list[j+1] = unsorted_list[j+1],unsorted_list[j]
    return unsorted_list

选择排序

选择排序 简介

选择排序是在每轮遍历序列中找出它们当中最小的元素,然后与首位的元素进行交换。当一轮遍历完后,将指向首位的指针向后移动。与冒泡排序相似的是,选择排序同样会重复n-1轮遍历。每次遍历的元素个数从n开始递减。但与冒泡排序不同的是,在每轮遍历中选择排序会找到最小的数,而冒泡排序会找到最大的。

总共遍历次数,最好、最差情况时交换次数都于冒泡排序相同。

平均交换次数同样为:\(\frac{n(n-1)}{4}\)

时间复杂度:O(\(n^2\))

空间复杂度:O(1)

选择排序代码

def full_select(unsorted_list):
    length = len(unsorted_list)
    for i in range(0,length):
        #初始时最小元素为首位元素
        min_index = i
        min_num = unsorted_list[min_index]
        for j in range(i + 1, length):
            #每轮遍历找到最小元素并暂存
            if (min_num > unsorted_list[j]):
                min_index = j
                min_num = unsorted_list[min_index]
                
        unsorted_list[i],unsorted_list[min_index] = unsorted_list[min_index],unsorted_list[i]

    return unsorted_list

插入排序

插入排序 简介

插入排序与斗地主排序扑克牌类似。它优先构建一个有序序列,当新的元素增加时,从后向前扫描有序序列找到新元素所在位置并将其插入。它虽比冒泡排序和选择排序更抽象一点,但原理仍然直观。

对于最好的情况,当序列都为正序:此时需要做0次操作

对于最差的情况,当序列都为逆序:此时需要做1+2+3+…+n-1 = \(\frac{n(n-1)}{2}\) 次操作。

平均操作仍为:\(\frac{n(n-1)}{4}\) 次

这里的操作包含了寻找合适位置时的遍历以及后续的插入。

所以插入排序的时间复杂度为:O(\(n^2\)) 空间复杂度为:O(1)

插入排序代码

def insert_sort(input_list):
    input_length  = len(input_list)
    for i in range(input_length-1):
        j=i+1
        #从有序序列中查找位置
        for k in range(j):
            if(input_list[k]<input_list[j]):continue
            #插入操作
            else:
                tmp = input_list[j]
                input_list.pop(j)
                input_list.insert(k,tmp)
    return input_list