【苏州程序大白用2万字】解析数据结构和八大排序算法☀️《❤️记得收藏❤️》

def sumofN(n):
    theSum = 0
    for i in range(1, n+1):
        theSum = thSum + i
    return theSum
print(sumofN(10))
# 1 + n + 1  =====>   n + 2  =====>  O(n)
a = 5
b = 6
c = 10
for i in range(n):
    for j in range(n):
      x = i * i
      y = j * j
      z = i * j
for k in range(n):
    w = a * k + 45
    v = b * b
d = 33
# 3 + 3n**2 + 2n + 1 ====> 3n**2 + 2n ====> 3n**2 ====> n**2 ====> O(n**2)

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

- Stack() //创建一个空的新栈。 它不需要参数，并返回一个空栈。
- push(item)    //将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。
- pop()   //从栈中删除顶部项。它不需要参数并返回 item 。栈被修改。
- peek()   //从栈返回顶部项，但不会删除它。不需要参数。 不修改栈。
- isEmpty()  //测试栈是否为空。不需要参数，并返回布尔值。
- size()   //返回栈中的 item 数量。不需要参数，并返回一个整数。
class Stark():
    def __init__(self):
        self.items = []
    def push(self, item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
  def peek(self):
        return len(self.items) - 1
    def isEmpty(self):
        return self,items == []
    def size(self):
        return len(self.items)

- Queue() //创建一个空的新队列。 它不需要参数，并返回一个空队列。
- enqueue(item) //将新项添加到队尾。 它需要 item 作为参数，并不返回任何内容。
- dequeue() //从队首移除项。它不需要参数并返回 item。 队列被修改。
- isEmpty() //查看队列是否为空。它不需要参数，并返回布尔值。
- size() //返回队列中的项数。它不需要参数，并返回一个整数。
class Queue():
    def __init__(self):
        self.items = []
    def enqueue(self, item):
        self.items.insert(0, item)
    def dequeue(self):
        return self.items.pop()
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)

//案例：烫手的山芋
// 烫手山芋游戏介绍：6个孩子围城一个圈，排列顺序孩子们自己指定。第一个孩子手里有一个烫手的山芋，需要在计时器计时1秒后将山芋传递给下一个孩子，依次类推。规则是，在计时器每计时7秒时，手里有山芋的孩子退出游戏。该游戏直到剩下一个孩子时结束，最后剩下的孩子获胜。请使用队列实现该游戏策略，排在第几个位置最终会获胜。
// 准则：队头孩子的手里永远要有山芋。
queue = Queue()
kids = ['A','B','C','D','E','F']
for kid in kids:
    queue.enqueue(kid)
while queue.size() > 1:
    for i in range(6):
        kid = queue.dequeue()
        queue.enqueue(kid)
    queue.dequeue()
print('获胜者为：', queue.dequeue())

- Deque() //创建一个空的新 deque。它不需要参数，并返回空的 deque。
- addFront(item) //将一个新项添加到 deque 的首部。它需要 item 参数 并不返回任何内容。
- addRear(item) //将一个新项添加到 deque 的尾部。它需要 item 参数并不返回任何内容。
- removeFront() //从 deque 中删除首项。它不需要参数并返回 item。deque 被修改。
- removeRear() //从 deque 中删除尾项。它不需要参数并返回 item。deque 被修改。
- isEmpty() //测试 deque 是否为空。它不需要参数，并返回布尔值。
- size() //返回 deque 中的项数。它不需要参数，并返回一个整数。
class Dequeue():
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)
    def addFront(self, item):
        self.items.append(item)
    def addRear(self, item):
        self.items.insert(0, item)
    def removeFront(self):
        return self.items.pop()
    def removeRear(self):
        return self.items.pop(0)

def isHuiWen(s):
    ex = True
    q = Dequeue()
    for ch in s:
        q.addFront(ch)
    for i in range(len(s)//2):
        font = q.removeFront()
        rear = q.removeRear()
        if font != rear:
            ex = False
            break
    return ex
print(isHuiWen('addan'))

is_empty()：//链表是否为空
length()：//链表长度
travel()：//遍历整个链表
add(item)：//链表头部添加元素
append(item)：//链表尾部添加元素
insert(pos, item)：//指定位置添加元素
remove(item)：//删除节点
search(item)：//查找节点是否存在

class Node():
    def __init__(self,item):
        self.item = item
        self.next = None

def sort(alist, item):  // item就是我们要找的元素
    low = 0  //进行二分查找操作的列表中的第一个元素的下标
    high = len(alist)
    find = False
    while low <= high:
        mid = (low+high) // 2 # 中间元素的下标
        if item > alist[mid]: // 我们要找的数比中间的数大，则意味着我们要找的数在中间元素的右侧
            low = mid + 1
        elif item < alist[mid]: // 我们要找的数比中间的数小，则我们要找的数在中间数的左侧
            high = mid - 1
        else:
            find = True
            break
    return find

class Node():
    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None
class Tree():
    # 构造出一颗空的二叉树
    def __init__(self, item): // root指向第一个节点的地址，如果root指向了None，则意味着该二叉树为空
        self.root = None
    # 向二叉树中插入节点
    def addNode(self, item):
        node = Node(item)
        if self.root == None:
            # addNode如果第一次被调用则意味着：向空树中插入第一个节点，该节点一定是该树的根节点
            self.root = node
            return
        # 如果上面的if不执行则树为非空，下面就执行向一个非空的树中插入节点的操作
        cur = self.root
        queue = [cur]
        while queue:
            n = queue.pop(0)
            if n.left != None:
                queue.append(n.left)
            else:
                n.left = node
                break
            if n.right != None:
                queue.append(n.right)
            else:
                n.right = node
                break
    def travel(self):
        # 如果为空
        if self.root == None:
            print("树为空！")
            return
        cur = self.root
        queue = [cur]
        while queue:
            n = queue.pop(0)
            print(n.item)
            if n.left != None:
                queue.append(n.left)
            if n.right != None:
                queue.append(n.right)
    # 前序遍历
    def forward(self, root):
        if root == None:
            return
        print(root.item)
        self.forward(root.left)
        self.forward(root.right)
    # 中序遍历
    def middle(self, root):
        if root == None:
            return
        self.middle(root.left)
        print(root.item)
        self.middle(root.right)
    # 后序遍历
    def back(self, root):
        if root == None:
            return
        self.back(root.left)
        self.back(root.right)
        print(root.item)

class Node():
    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None
class SortTree():
    def __init__(self):
        self.root = None
    def insertNode(self, item):
        node = Node(item)
        # 向空树插入第一个节点
        if self.root == None:
            self.root = node
            return
        # 树为非空的情况
        cur = self.root
        while True:
            if node.item > cur.item: // 往右插
                if cur.right == None:
                    cur.right = node
                    break
                else:
                    cur = cur.right
            else: #往左插
                if cur.left = None:
                    cur.left = node
                    break
                else:
                    cur = cur.left
    def forward(self, root):
        if root == None:
            return
        print(root.item)
        self.forward(root.left)
        self.forward(root.right)
    def middle(self, root):
        if root == None:
            return
        self.middle(root.left)
        print(root.item)
        self.middle(root.right)
    def back(self, root):
        if root == None:
            return
        self.back(root.left)
        self.back(root.right)
        print(root.item)

void bubble_sort(int *arr,int len)
{
    int i,j,tmp;
    int swap = 1;
    for(i = 0; i< len-1;i++)
    {
        for(j = 0; j< len -1 -i; j++)
            if(arr[j] > arr[j+1])
            {
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
                swap = 0;
            }
        if(swap)  //如果没进行交换直接退出
            return;
    }
}

void select_sort(int *arr,int len)
{
    int i,j,tmp;
    int min;
    for(i = 0;i<len;i++)
    {
        min = i;
        for(j=i + 1;j<len;j++)
            if(arr[j] < arr[min])
                min = j;
        tmp = arr[i];
        arr[i]=arr[min];
        arr[min] = tmp;
    }
}

void insert_sort(int *arr,int len)
{
    int i,j;
    int tmp = 0;
    for(i = 1;i< len;i++)
    {
        tmp  = arr[i];
        for(j = i-1;j>=0;j--)
            if(arr[j] > tmp)
                arr[j+1] = arr[j];
            else
                break;
        arr[j+1] = tmp;
    }
}

void shell_sort(int *arr,int len,int gap)
{
    int tmp;
    int i,j;
    for(i = gap; i<len; i = i+gap)
    {
        tmp = arr[i];
        for(j = i -gap;j>=0;j=j-gap)
            if(arr[j] > tmp)
                arr[j+gap] = arr[j];
            else
                break;
        arr[j+gap] = tmp;
    }
}
void Shell(int *arr,int len)
{
    int gap[] = {5,3,1};    //可以分为步长的一半，这里就自定义好了
    int len_gap = sizeof(gap)/sizeof(gap[0]);
    for(int i=0;i<len_gap;++i)
        shell_sort(arr,len,gap[i]);
}

int division(int *arr,int left,int right)
{
    //每次取基准数为最左边的那个数
    int base = arr[left];
    while(left<right)
    {
        //从右端开始，向左寻找，找到小于基准数的值时将元素放最左边
        while(left<right && arr[right] >= base)
            --right;
        arr[left] = arr[right];
        //同理，当找到时转为左边开始向右找，将大于基准数的值放元素右边
        while(left<right && arr[left] <= base)
            ++left;
        arr[right] = arr[left];
    }
    // 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；
    // 而left位置的右侧数值应该都比left大
    arr[left] = base;
    return left;
}
void quick_sort(int *arr,int left,int right)
{
    //左下标要小于右下标，否则会越界
    if( left < right)
    {
        //按照基准数对数组进行分割
        int base = division(arr,left,right);
        //分别对左右两边进行递归
        quick_sort(arr,left,base-1);
        quick_sort(arr,base+1,right);
    }
}