排序算法

1

import numpy as np

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def bubble_sort(data):
    for i in range(len(data)):
        x = 0
        for j in range(len(data)-i-1):
            print(data)
            if data[j] > data[j+1]:
                x = 1
                data[j] ,data[j+1] = data[j+1],data[j]
        if not x:
            break

1
2
3
4

sample = np.random.randint(10,size = 10)
print(sample)
print('--------')
bubble_sort(sample)

 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
29
30
31
32
33
34
35
36
37
38
39
40
41

[8 3 0 0 7 6 6 5 3 7]
--------
[8 3 0 0 7 6 6 5 3 7]
[3 8 0 0 7 6 6 5 3 7]
[3 0 8 0 7 6 6 5 3 7]
[3 0 0 8 7 6 6 5 3 7]
[3 0 0 7 8 6 6 5 3 7]
[3 0 0 7 6 8 6 5 3 7]
[3 0 0 7 6 6 8 5 3 7]
[3 0 0 7 6 6 5 8 3 7]
[3 0 0 7 6 6 5 3 8 7]
[3 0 0 7 6 6 5 3 7 8]
[0 3 0 7 6 6 5 3 7 8]
[0 0 3 7 6 6 5 3 7 8]
[0 0 3 7 6 6 5 3 7 8]
[0 0 3 6 7 6 5 3 7 8]
[0 0 3 6 6 7 5 3 7 8]
[0 0 3 6 6 5 7 3 7 8]
[0 0 3 6 6 5 3 7 7 8]
[0 0 3 6 6 5 3 7 7 8]
[0 0 3 6 6 5 3 7 7 8]
[0 0 3 6 6 5 3 7 7 8]
[0 0 3 6 6 5 3 7 7 8]
[0 0 3 6 6 5 3 7 7 8]
[0 0 3 6 5 6 3 7 7 8]
[0 0 3 6 5 3 6 7 7 8]
[0 0 3 6 5 3 6 7 7 8]
[0 0 3 6 5 3 6 7 7 8]
[0 0 3 6 5 3 6 7 7 8]
[0 0 3 6 5 3 6 7 7 8]
[0 0 3 5 6 3 6 7 7 8]
[0 0 3 5 3 6 6 7 7 8]
[0 0 3 5 3 6 6 7 7 8]
[0 0 3 5 3 6 6 7 7 8]
[0 0 3 5 3 6 6 7 7 8]
[0 0 3 5 3 6 6 7 7 8]
[0 0 3 3 5 6 6 7 7 8]
[0 0 3 3 5 6 6 7 7 8]
[0 0 3 3 5 6 6 7 7 8]
[0 0 3 3 5 6 6 7 7 8]
[0 0 3 3 5 6 6 7 7 8]

1
2
3
4
5
6
7
8

def selection_sort(data):
    for i in range(len(data)):
        x = i
        print(data)
        for j in range(i+1,len(data)):
            if data[j] < data[x]:
                x = j                    
        data[i],data[x] = data[x],data[i]

1
2
3
4

sample = [6, 1, 4, 5, 2] #[np.random.randint(10,size = 5)]
print(sample)
print('--------')
selection_sort(sample)

1
2
3
4
5
6
7

[6, 1, 4, 5, 2]
--------
[6, 1, 4, 5, 2]
[1, 6, 4, 5, 2]
[1, 2, 4, 5, 6]
[1, 2, 4, 5, 6]
[1, 2, 4, 5, 6]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def insert_sort(data):
    for i,j in enumerate(data):
        if i < 1:
            continue
        k = i
        while(k>0 and data[k]<data[k-1]):
            data[k],data[k-1] = data[k-1],data[k]
            k -= 1
            print(k)
            print(data)
    return data

1
2
3
4

sample = [6, 1, 4, 5, 2] #[np.random.randint(10,size = 5)]
print(sample)
print('--------')
insert_sort(sample)

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

[6, 1, 4, 5, 2]
--------
0
[1, 6, 4, 5, 2]
1
[1, 4, 6, 5, 2]
2
[1, 4, 5, 6, 2]
3
[1, 4, 5, 2, 6]
2
[1, 4, 2, 5, 6]
1
[1, 2, 4, 5, 6]

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

def shell_sort(data):
    # Marcin Ciura's gap sequence
    gaps = [701, 301, 132, 57, 23, 10, 4, 1]
    for gap in gaps:
        i = gap
        while i < len(data):
            temp = data[i]
            j = i
            while j >= gap and data[j - gap] > temp:
                data[j] = data[j - gap]
                j -= gap
            data[j] = temp
            i += 1
            print(data)

    return data

1
2

sample = [0,3,5,0,-1,9,0]
shell_sort(sample)

1
2
3
4
5
6
7
8
9

[-1, 3, 5, 0, 0, 9, 0]
[-1, 3, 5, 0, 0, 9, 0]
[-1, 3, 0, 0, 0, 9, 5]
[-1, 3, 0, 0, 0, 9, 5]
[-1, 0, 3, 0, 0, 9, 5]
[-1, 0, 0, 3, 0, 9, 5]
[-1, 0, 0, 0, 3, 9, 5]
[-1, 0, 0, 0, 3, 9, 5]
[-1, 0, 0, 0, 3, 5, 9]

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

def merge_sort(data):
    def divide(data):
        if len(data)<=1:
            return data
        return merge(divide(data[:len(data)//2]),divide(data[len(data)//2:]))
    
    def merge(data1,data2):
        i,j=0,0
        ret = []
        while(data2 and data1):
            ret.append((data1 if data1[0] < data2[0] else data2).pop(0))
        return ret+data1+data2
    return divide(data)

1
2
3
4
5
6
7
8
9

def quick_sort(data):
    if len(data) < 1 :
        return data
    else:
        mid = data[0]
        greater = [element for element in data[1:] if element > mid]
        lesser = [element for element in data[1:] if element <= mid]
        print(lesser,mid,greater)
        return quick_sort(lesser) + [mid] + quick_sort(greater)

1
2

sample = [0, 5, 3, 4, 2]
quick_sort(sample)

1
2
3
4
5

[] 0 [5, 3, 4, 2]
[3, 4, 2] 5 []
[2] 3 [4]
[] 2 []
[] 4 []

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

def heap_sort(data):
    for i in range(len(data) // 2 - 1, -1, -1):
        heapify(data, i, len(data))
    for i in range(len(data)-1, 0, -1):
        data[0], data[i] = data[i],data[0]
        heapify(data, 0, i)
    return data
def heapify(data, index, heap_size):
    largest = index
    left_index = 2 * index + 1
    right_index = 2 * index + 2
    if left_index < heap_size and data[left_index] > data[largest]:
        largest = left_index

    if right_index < heap_size and data[right_index] > data[largest]:
        largest = right_index
    if largest != index:
        data[largest], data[index] = data[index], data[largest]
        heapify(data, largest, heap_size)