Python—数据结构算法

一、什么是算法

算法（Algorithm）：一个计算过程，解决问题的方法

二、时间复杂度、空间复杂度

Ⅰ、时间复杂度

    时间复杂度是一个函数，它定量描述该算法的运行时间，时间复杂度常用“O”表示，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。呈现时间频度的变化规律，记为T(n)=O(f(n)) 指数时间：一个问题求解所需的执行时间m(n),依输入数据n呈指数倍成长（即 求解所需的执行时间呈指数倍成长）

时间复杂度是用来估计算法运行时间的一个式子（单位），一般来说，时间复杂度高的算法比复杂度低的算法慢

print('Hello world')  # O(1)
 
 
# O(1)
print('Hello World')
print('Hello Python')
print('Hello Algorithm')
 
 
for i in range(n):  # O(n)
    print('Hello world')
 
 
for i in range(n):  # O(n^2)
    for j in range(n):
        print('Hello world')
 
 
for i in range(n):  # O(n^2)
    print('Hello World')
    for j in range(n):
        print('Hello World')
 
 
for i in range(n):  # O(n^2)
    for j in range(i):
        print('Hello World')
 
 
for i in range(n):
    for j in range(n):
        for k in range(n):
            print('Hello World')  # O(n^3)

Ⅱ、空间复杂度

空间复杂度：用来评估算法内存占用大小的一个式子

三、列表排序

列表排序：将无序列表变为有序列表

1、冒泡排序

所谓冒泡，就是将元素两两之间进行比较，谁大就往后移动，直到将最大的元素排到最后面，接着再循环一趟，从头开始进行两两比较，而上一趟已经排好的那个元素就不用进行比较了。（图中排好序的元素标记为黄色柱子）

时间复杂度：O(n2)

基础写法：

def bubble_sort(li):
    for i in range(len(li) - 1):
        for j in range(len(li) - 1 - i):
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]
    return li


list = [3, 1, 5.78, 8, 63, 96, 21, 0, 2]
print(bubble_sort(list))

冒泡优化1

# 设定一个变量为False，如果元素之间交换了位置，将变量重新赋值为True,最后再判断，#在一次循环结束后，变量如果还是为False，则brak退出循环，结束排序。
#如果冒泡排序中执行一趟而没有交换，则列表已经是有序状态，可以直接结束算法。
def bubble_sort(li):
    for i in range(len(li) - 1):
        flag = False
        for j in range(len(li) - 1 - i):
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]
                flag = True
        print("冒泡第%s次" % i)
        if not flag:
            print("yes")
            break
    return li


# list = [3, 1, 5.78, 8, 63, 96, 21, 0, 2]
list = [1, 2, 3, 4, 5, 8, 6, 9, 7]
print(bubble_sort(list))

冒泡优化三

双向排序提高效率，即当一次从左向右的排序比较结束后，立马从右向左来一次排序比较。

# 双向冒泡
@cal_time
def bubble_sort2(li):
    for i in range(len(li) - 1):
        flag = False
        for j in range(len(li) - 1 - i):
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]
                flag = True
        if flag:
            for j in range(len(li) - 1 - i, 0, -1):
                if li[j - 1] > li[j]:
                    li[j - 1], li[j] = li[j], li[j - 1]
                    flag = True
        if not flag:
            break
    return li

三种冒泡执行时间对比

import time, sys
sys.setrecursionlimit(1000000)
# 自定义计时装饰器
def cal_time(func):
    def waraper(*args, **kwargs):
        t1 = time.time()
        res = func(*args, **kwargs)
        t2 = time.time()
        print('%s消耗的时间是:%s' % (func.__name__, t2 - t1))
        return res
    return waraper
# 随机1-10000生成列表
li = list(range(1, 10000))
random.shuffle(li)
bubble_sort(li)
bubble_sort1(li)
bubble_sort2(li)
---------------------------------------------------------------------
# 时间：
bubble_sort消耗的时间是:9.232983350753784
bubble_sort1消耗的时间是:0.0010197162628173828
bubble_sort2消耗的时间是:0.0009989738464355469

2、选择排序

核心算法：固定位置，选择元素，即：先从序列中，找到最小的元素，放在第一个位置，之后找到第二小的元素，放在第二个元素，以此类推，就可以完成整个排序工作了。

# 时间复杂度: O(n^2) 空间复杂度: O(1)
@cal_time
def select_sort(li):
    for i in range(len(li) - 1):
        min_li = i
        for j in range(i + 1, len(li)):
            if li[j] < li[min_li]:
                min_li = j
        if min_li != i:
            li[i], li[min_li] = li[min_li], li[i]


li = list(range(1, 10000))
random.shuffle(li)
select_sort(li)

3、插入排序

# 列表被分为有序区和无序区两个部分。最初有序区只有一个元素。
# 每次从无序区选择一个元素，插入到有序区的位置，直到无序区变空。
@cal_time
def insert_sort(li):
    for i in range(1, len(li)):
        tmp = li[i]
        # 设置当前值其哪一个元素标识
        j = i - 1
        while j >= 0 and tmp < li[j]:
            li[j + 1] = li[j]
            j = j - 1
        li[j + 1] = tmp
li = list(range(1, 100))
random.shuffle(li)
insert_sort(li)
print(li)

排序low组

• 冒泡排序 插入排序 选择排序
• 时间复杂度：O(n2)
• 空间复杂度：O(1)

4、快速排序

    快速排序的思想：首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序

快速排序的算法是：

1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；

2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；

3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；

4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；

5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

# 时间复杂度: O(nlogn) 空间复杂度: O(1)
def partition(data, left, right):
    tmp = data[left]
    while left < right:
        while left < right and data[right] >= tmp:
            right -= 1
        data[left] = data[right]
        while left < right and data[left] <= tmp:
            left += 1
        data[right] = data[left]
    data[left] = tmp
    return tmp


def _quick_sort(data, left, right):
    if left < right:
        mid = partition(data, left, right)
        _quick_sort(data, left, mid - 1)
        _quick_sort(data, mid + 1, right)


@cal_time
def quick_sort(li, left, right):
    _quick_sort(li, left, right)

4、归并排序

**归并排序**仍然是利用完全二叉树实现，它是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列。

**基本过程**：假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列，再两两归并，最终得到一个长度为n的有序序列为止，这称为2路归并排序。

图中主要表明了实例代码中的两部分，分别为原始序列的拆分和合并两部分

def merge(li, low, mid, high):
    i = low
    j = mid + 1
    ltmp = []
    while i <= mid and j <= high:
        if li[i] < li[j]:
            ltmp.append(li[i])
            i = i + 1
        else:
            ltmp.append(li[j])
            j = j + 1

    while i <= mid:
        ltmp.append(li[i])
        i = i + 1

    while j <= high:
        ltmp.append(li[j])
        j = j + 1

    li[low:high + 1] = ltmp


def _mergesort(li, low, high):
    if low < high:
        mid = (low + high) // 2
        _mergesort(li, low, mid)
        _mergesort(li, mid + 1, high)
        merge(li, low, mid, high)


@cal_time
def mergesort(li, low, high):
    _mergesort(li, low, high)

多种排序算法在同一条件下的执行情况

li = list(range(1, 10000))
random.shuffle(li)
mergesort(li, 0, len(li) - 1)

li = list(range(1, 10000))
random.shuffle(li)
bubble_sort1(li)

li = list(range(1, 10000))
random.shuffle(li)
bubble_sort2(li)

li = list(range(1, 10000))
random.shuffle(li)
select_sort(li)

li = list(range(1, 10000))
random.shuffle(li)
insert_sort(li)

li = list(range(1, 10000))
random.shuffle(li)
quick_sort(li, 0, len(li) - 1)
---------------------------------------------------------------------mergesort消耗的时间是:0.03596305847167969
bubble_sort1消耗的时间是:12.642452716827393
bubble_sort2消耗的时间是:10.469623804092407
select_sort消耗的时间是:4.044940233230591
insert_sort消耗的时间是:5.539592027664185
quick_sort消耗的时间是:0.032910823822021484

5、希尔排序

希尔排序是一种分组插入排序算法。

首先取一个整数d1=n/2，将元素分为d1个组，每组相邻量元素之间距离为d1，在各组内进行直接插入排序；

取第二个整数d2=d1/2，重复上述分组排序过程，直到di=1，即所有元素在同一组内进行直接插入排序。

希尔排序每趟并不使某些元素有序，而是使整体数据越来越接近有序；最后一趟排序使得所有数据有序。

# 希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
# 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
# 希尔排序是基于插入排序的以下两点性质而提出改进方法的：
# 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
# 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

def shell_sort(li):
    gap = len(li) // 2
    while gap > 0:
        for i in range(gap, len(li)):
            tmp = li[i]
            j = i - gap
            while j >= 0 and tmp < li[j]:
                li[j + gap] = li[j]
                j -= gap
                li[j + gap] = tmp
                gap /= 2

小结：

Python—数据结构算法

原文：https://www.cnblogs.com/prodigal/p/11094619.html