笔试算法day1

发表于

#选择排序算法

1
2
3
4
5
6
7
8
9
10
def sort(a):
	N = len(a)
	for i in range(N):
		min = i
		for j in range(i+1,N):
			if a[min] > a[j]:
				min = j
		temp = a[min]
		a[min] = a[j]
		a[j] = temp

#插入排序算法

1
2
3
4
5
6
7
8
def sort(a):
	N = len(a)
	for i in range(1,N):
		for j in range(i,0,-1):
			if a[j] < a[j-1]
				temp = a[j]
				a[j] = a[j-1]
				a[j-1] = temp

#希尔排序算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def sort(a):
	N = len(a)
	#将整个数组分成3份
	h = N
	while h > 1:
		h = h / 3 +1
		for i in range(h,N):
			j = i
			while j-h >= 0:
				if a[j] < a[j-h]:
					temp = a[j]
					a[j] = a[j-h]
					a[j-h] = temp
				j = j-h

#归并排序

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
26
27
28
def merge(a, b):
    c = []
    h = j = 0
    while j < len(a) and h < len(b):
        if a[j] < b[h]:
            c.append(a[j])
            j += 1
        else:
            c.append(b[h])
            h += 1

    if j == len(a):
        for i in b[h:]:
            c.append(i)
    else:
        for i in a[j:]:
            c.append(i)

    return c


def merge_sort(lists):
    if len(lists) <= 1:
        return lists
    middle = len(lists)/2
    left = merge_sort(lists[:middle])
    right = merge_sort(lists[middle:])
    return merge(left, right)

#快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def sort(a,low,high):
	left = low
	right = high
	if left >= right:
		return
	key = a[left]
	l = left
	while True:
		while a[left] <= key and left < right:
			left +=1
		while a[right] > key and left < right:
			right -=1
		
		temp = a[left]
		a[left] = a[right]
		a[right] = temp
		if left >= right:
			break
	a[right] = key
	sort(a,low,right)
	sort(a,right,high)