程序中的常见算法总结

学过了《数据结构》，也学过了《算法导论》，今天总结一下算法方面的内容，便于日后回忆使用！

算法是一种程序优化的方法，很多参考书籍都是 C++/C 语言的，为了编程的简单性，参考了《啊哈！算法》一书，同时采用python编程。

0x01 桶排序

初始一个数组，对应索引下记录该索引值数字的个数，然后按照个数输出索引值次数

# name: sort001.py
# author: DYBOY
# description: 一种简单的排序-桶排序
# time: O(N+M)

unsort_list = [1,2,5,3,4,6,7,0,9,8,5]   # 待排序序列
num = int(input('请输入排序的不同数字的数量：'))
numArr = [0 for i in range(0,num)]

for i in unsort_list:
    numArr[i] += 1
for index,j in enumerate(numArr):
    for k in range(0,j):
        print(index)

---

0x02 冒泡排序

每次比较两个相邻元素大小，按照约定大小顺序交换或不交换

# name: sort002.py
# author: DYBOY
# description: 一种简单的排序-冒泡排序
# time: O(N^2)

unsort_list = [1,2,5,3,4,6,7,0,9,8,5]   # 待排序序列

num = len(unsort_list)

for i in range(0,num):
    for j in range(0,num-i-1):
        if(unsort_list[j] > unsort_list[j+1]):
            temp = unsort_list[j]
            unsort_list[j] = unsort_list[j+1]
            unsort_list[j+1] = temp

print(unsort_list)

---

0x03 快速排序

一个基准数，从左往右大于基准数，则放到基准数右边，从右往左小于基准数，则放到基准数左边。（从左往右找一个大于基准数，从右往左找一个大于基准数，交换这两个数位置）

# name: sort003.py
# author: DYBOY
# description: 一种简单的排序-快速排序
# time: O(NlogN)

unsortArr = [6,1,2,7,9,3,4,5,10,3,8,3]

def quicksort(left, right):
    if(left > right): # 左侧大于右侧（索引号），则停止
        return
    temp = unsortArr[left]  # 存放基准值
    i = left
    j = right

    while(i != j):        # 直到两头相遇
        while(unsortArr[j] >= temp and i<j):    # 右边开始与基准值比较
            j-=1
        while(unsortArr[i] <= temp and i<j):    # 左边开始与基准值比较
            i+=1
        if(i<j):    # i<j 情况下交换值
            t = unsortArr[i]
            unsortArr[i]=unsortArr[j]
            unsortArr[j]=t

    unsortArr[left] = unsortArr[i]  #当i=j，最左侧选择的基准值与当前同索引值交换
    unsortArr[i] = temp
    # 分两半继续快速排序
    quicksort(left, i-1)
    quicksort(i+1, right)
    return

if __name__ == '__main__':
    quicksort(0,len(unsortArr)-1)
    print(unsortArr)

---

0x04 队列

struct queue{
    int data[1000];
    int head;
    int tail;
}

---

0x05 栈

struct stack{
    int data[100];
    int top;
}

---

0x06 链表

struct node{
    int data;
    struct node *next;
}