排序

-_-会常见的大部分排序,这种会的都总结一下,有些虽然简单但还是手写记录一下
插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
import random

def (arr):
if(len(arr) == 0): return arr;
for i in range(1, len(arr)-1):
for j in range(i-1, -1, -1):
if(arr[j] > arr[j+1]): arr[j], arr[j+1] = arr[j+1], arr[j]
else: break
return arr

arr = random.sample(range(100), 10)
print("origin arr is {}".format(arr));
print("sort arr is {}".format(insert_sort(arr)));


选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import random

def select_sort(arr):
if(len(arr) == 0): return arr;
for i in range(len(arr)):
min_pos = i
for j in range(i+1, len(arr)):
if(arr[j]<arr[min_pos]): min_pos = j
arr[i], arr[min_pos] = arr[min_pos], arr[i]
return arr

arr = random.sample(range(100), 10)
print("origin arr is {}".format(arr));
print("sort arr is {}".format(select_sort(arr)));


冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import random

def bubble_sort(arr):
if(len(arr) == 0): return arr;
for end in range(len(arr), 0, -1):
is_sorting = True
for j in range(1, end):
if(arr[j] < arr[j-1]):
is_sorting = False
arr[j], arr[j-1] = arr[j-1], arr[j]
if(is_sorting): break;
return arr

arr = random.sample(range(100), 10)
print("origin arr is {}".format(arr));
print("sort arr is {}".format(bubble_sort(arr)));

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import random

def merge(left, right):
ans = []
while(len(left)>0 and len(right)>0):
if(left[0] > right[0]):
ans.append(right.pop(0))
else:
ans.append(left.pop(0))
if(len(left)==0): ans += right
else: ans += left
return ans

def merge_sort(arr, lo, hi):
if(lo>=hi): return [arr[lo]]
mid = lo+(hi-lo)//2
left = merge_sort(arr, lo, mid)
right = merge_sort(arr, mid+1, hi)
return merge(left, right)

arr = random.sample(range(100), 10)
print("origin arr is {}".format(arr));
print("sort arr is {}".format(merge_sort(arr, 0, len(arr)-1)));

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import random

def quick_sort(arr, lo, hi):
if(lo>=hi): return
key = arr[lo];
i, j = lo, hi
while(i<j):
while(i<j and arr[j]>key):j-=1
if(i<j): arr[i], i = arr[j], i+1
while(i<j and arr[i]<key):i+=1
if(i<j): arr[j], j = arr[i], j-1
arr[i]=key
quick_sort(arr, lo, i-1)
quick_sort(arr, i+1, hi)
return arr

arr = random.sample(range(100), 10)
print("origin arr is {}".format(arr));
print("sort arr is {}".format(quick_sort(arr, 0, len(arr)-1)));