这里整理的都是基础的不能再基础的算法，目的就是进行一个回忆，同时作为剑指offer的一个补充~嘿嘿~

查找算法

二分查找

# 实现一个二分查找

# 输入:一个顺序list

# 输出: 待查找的元素的位置

def binarySearch(alist, item):

first = 0

last = len(alist) - 1

while first <= last:

mid = (first + last)//2

print(mid)

if alist[mid] > item:

last = mid - 1

elif alist[mid] < item:

first = mid + 1

else:

return mid+1

return -1

test = [0, 1, 2, 8, 13, 17, 19, 32, 42]

print(binarySearch(test, 3))

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

排序算法

冒泡排序

def bubbleSort(alist):

for passnum in range(len(alist)-1, 0, -1):

for i in range(passnum):

if alist[i] > alist[i+1]:

alist[i], alist[i+1] = alist[i+1], alist[i]

return alist

1

2

3

4

5

6

插入排序

def insertionSort(alist):

for index in range(1, len(alist)):

currentvalue = alist[index]

position = index

while position > 0 and alist[position-1] > currentvalue:

alist[position] = alist[position-1]

position -= 1

alist[position] = currentvalue

1

2

3

4

5

6

7

8

9

快速排序

def quickSort(alist):

quickSortHelper(alist, 0, len(alist)-1)

def quickSortHelper(alist, first, last):

if first < last:

splitPoint = partition(alist, first, last)

quickSortHelper(alist, first, splitPoint-1)

quickSortHelper(alist, splitPoint+1, last)

def partition(alist, first, last):

pivotvlue = alist[first]

leftmark = first+1

rightmark = last

done = False

while leftmark > rightmark:

while alist[leftmark] <= pivotvlue and leftmark <= rightmark:

leftmark += 1

while alist[rightmark] >= pivotvlue and rightmark >= leftmark:

rightmark -= 1

alist[leftmark], alist[rightmark] = alist[rightmark], alist[leftmark]

alist[rightmark], alist[first] = alist[first], alist[rightmark]

return rightmark

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

选择排序

def selectionSort(alist):

for i in range(len(alist)-1):

min = i

for j in range(i+1, len(alist)):

if alist[j] < alist[min]:

min = j

alist[i], alist[min] = alist[min], alist[i]

return alist

1

2

3

4

5

6

7

8

9

冒泡排序

class Solution:

def bubbleSort(nums):

# 这个循环负责设置冒泡排序进行的次数

for i in range(len(nums)-1):

# ｊ为列表下标

for j in range(len(nums)-i-1):

if nums[j] > nums[j+1]:

nums[j], nums[j+1] = nums[j+1], nums[j]

return nums

1

2

3

4

5

6

7

8

9

树的四种遍历方式

class node(object):

def __init__(self,data=None,left=None,right=None):

self.data=data

self.left=left

self.right=right

#深度

def depth(tree):

if tree==None:

return 0

left,right=depth(tree.left),depth(tree.right)

return max(left,right)+1

#前序遍历

def pre_order(tree):

if tree==None:

return

print tree.data

pre_order(tree.left)

pre_order(tree.right)

#中序遍历

def mid_order(tree):

if tree==None:

return

mid_order(tree.left)

print tree.data

mid_order(tree.right)

#后序遍历

def post_order(tree):

if tree==None:

return

post_order(tree.left)

post_order(tree.right)

print tree.data

#层次遍历

def level_order(tree):

if tree==None:

return

q=[]

q.append(tree)

while q:

current=q.pop(0)

print current.data

if current.left!=None:

q.append(current.left)

if current.right!=None:

q.append(current.right)

---------------------

作者：alicelmx

来源：CSDN

原文：https://blog.csdn.net/alicelmx/article/details/80429229

版权声明：本文为博主原创文章，转载请附上博文链接！