学过了《数据结构》,也学过了《算法导论》,今天总结一下算法方面的内容,便于日后回忆使用!
算法是一种程序优化的方法,很多参考书籍都是 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; }
版权声明:《 程序中的常见算法总结 》为DYBOY原创文章,转载请注明出处!
最后编辑:2019-2-14 12:02:28