首页 > itarticle > 排序

排序

admin 11月 12, 2020 0

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

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)));

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能