Python-数据结构与算法

# 冒泡排序:将相邻的元素以此比较、重复比较列表元素、降序还是升序都可、

def sorted1(alist):
    n = len(alist)
    # i表示第几轮冒泡(i的数量表示遍历的次数）
    for i in range(n-1):
        print(i)
        # j表示访问到的元素索引
        for j in range(n-1-i):
            print(j)
            if alist[j] > alist[j+1]:
                alist[j],alist[j+1] = alist[j+1],alist[j]
    return alist

if __name__ == '__main__':
    alist = [9,1,3,2,8]
    print(sorted1(alist))

# 插入排序：将未排序的序列的值插入到已排序的序列中
# 思路：假设成两个序列，一个是已排序的一个是未排序的，初始化时已排序的是空序列 输入的整个序列是未排序
def insert_sorted(alist1):
    n1 = len(alist1)
    print(n1)
    # 把未排序的序列遍历
    for i in range(n1):
        # 未排序的序列从头到尾做为准备插入的数据
        insertdata = alist1[i]
        while i >= 1:
            if alist1[i-1] > insertdata:
                alist1[i] = alist1[i-1]
            else:
                break
            i = i-1
            alist1[i] = insertdata
    return alist1

if __name__ == '__main__':
    alist1 = [9,10,1,6,4,7]
    print(insert_sorted(alist1))

def shell_sort(alist):
    '''希尔排序：将序列平均分成两组，然后第一组的第一个元素和 第二组的第一个元素比较。
    第一组的第二个元素和 第二组的第二个元素比较。
    。。。
    如果出现最后一个元素没有分组的、就会相邻元素一次比较
    '''
    n = len(alist)
    gap = n//2
    #gap变化到0之前，插入算法执行的次数
    while gap > 0:
        #插入算法，与普通的插入算法的区别就是gap步长
        for j in range(gap, n):
            i = j
            while i > 0:
                if alist[i] < alist[i-gap]:
                    alist[i], alist[i-gap] = alist[i-gap], alist[i]
                    i -= gap
                else:
                    break
        #缩短gap步长,得到新的步长
        gap = gap // 2
'''最优时间复杂度：根据步长序列的不同而不同
最坏时间复杂度：O(n*n)
稳定性：不稳定'''
if __name__ == '__main__':
    li = [54, 26, 93,1,6,3,9]
    shell_sort(li)
    print(li)

"""
直接选择排序：最直观的简单排序方法、
每次遍历都是从待排序的序列里选出最小或最大的元素 放在序列的起始位置、直到全部排完
"""
def SelectSort(alist):
    n = len(alist)
    # 第i个元素和后面的每一个元素都会比较一遍
    for i in range(n):
        print(i)
        for j in range(i+1,n):
            print(j)
            if alist[i] > alist[j]:
                alist[i],alist[j] = alist[j],alist[i]
    return alist

if __name__ == '__main__':
    alist = [9,11,5,1,7,3,8]
    print(SelectSort(alist))