数据结构排序算法

数据结构排序算法 python实现：

该文章实现了冒泡，快速，选择，插入排序，二分插入排序，希尔排序，堆排序，归并排序，基数排序

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
# 冒泡排序
def bobble_sort(data):
    for i in range(len(data) - 1):
        data_mark = 0
        mark = 0
        for m in range(1, len(data)-i):
            if data[data_mark] > data[m]:
                data[data_mark], data[m] = data[m], data[data_mark]
                mark = 1
            data_mark = m
        if mark == 0:
            break
    return data

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 快速排序
def find_mid(data, low, high):
    mark = data[low]
    while low < high:
        while mark <= data[high] and low < high:
            high -= 1
        data[low] = data[high]
        while mark >= data[low] and low < high:
            low += 1
        data[high] = data[low]
    data[low] = mark
    return low
def Q_sort(data, low, high):
    if low < high:
        mid = find_mid(data, low, high)
        Q_sort(data, low, mid-1)
        Q_sort(data, mid+1, high)

def Quick_Sort(data):
    Q_sort(data, 0, len(data)-1)
    return data

选择排序

1
2
3
4
5
6
7
8
9
10
# 选择排序
def Choose_Sort(data):
    for i in range(0, len(data)-1):
        mark = i
        for m in range(i+1, len(data)):
            if data[mark] > data[m]:
                mark = m
        if mark != i:
            data[mark], data[i] = data[i], data[mark]
    return data

插入排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
# 插入排序
def Insert_Sort(data):
    for i in range(len(data)-1):
        if data[i] > data[i+1]:
            mark = data[i+1]
            data[i+1] = data[i]
            for m in range(i-1, -1,-1):
                if data[m] > mark:
                    data[m+1] = data[m]
                else:
                    data[m+1] = mark
                    break
    return data

二分插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 二分插入排序
def BInsert_Sort(data):
    for i in range(len(data)-1):
        if data[i] > data[i+1]:
            low = 0
            high = i
            mark = data[i+1]
            while(low <= high):
                mid = int(high-low)
                if(data[mid] > mark):
                    high = mid-1
                else:
                    low = mid+1
            for m in range(i, low-1, -1):
                data[m+1] = data[m]
            data[low] = mark
    return data

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 希尔排序
def Shell_Insert(data, k):
    for i in range(k, len(data)):
        if data[i-k] > data[i]:
            mark = data[i]
            for m in range(i-k, 0-k-1, -k):
                if m >= 0 and data[m] > mark:
                    data[m+k] = data[m]
                else:
                    break
            data[m+k] = mark

def Shell_Sort(data):
    k = int(len(data) / 2)
    for i in range(k, -4, -4):
        Shell_Insert(data, i)
    Shell_Insert(data, 1)
    return data

堆排序

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
# 堆排序
def HeapAdjust(data, s, m):
    mark = data[s]
    j = 2*s
    while True:
        if j > m:
            break
        if j < m and data[j] < data[j+1]:
            j += 1
        if mark > data[j]:
            break
        data[s] = data[j]
        s=j
        j *= 2
    data[s] = mark
    
def CreatHeap(data):
    n = len(data)-1
    m = int(n/2)
    for i in range(m, 0, -1):
        HeapAdjust(data, i, n)
        
def HeapSort(data):
    CreatHeap(data)
    for i in range(len(data)-1, 0, -1):
        data[i], data[1] = data[1], data[i]
        HeapAdjust(data,1, i-1)
    return data

归并排序

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(data1, data2):
    data3 = []
    i = j = 0
    while i < len(data1) and j < len(data2) :
        if data1[i] < data2[j]:
            data3.append(data1[i])
            i += 1
        else:
            data3.append(data2[j])
            j += 1
    if j == len(data2):
        for m in data1[i:]:
            data3.append(m)
#         data3.extend(data1[i:])
    else:
        for m in data2[j:]:
            data3.append(m)
        
    return data3

def Msort(data):
    if len(data) <= 1:
        return data
    mid = (len(data))//2
    left = Msort(data[:mid])
    right = Msort(data[mid:])
    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
22
23
24
25
26
27
28
29
30
31
32
33
34
# 基数排序
def Cardinality_sort(data):
    max_len = len(str(max(data)))
    data = [(max_len-len(str(i)))*"0"+str(i) for i in data]
    temp_list = [[] for i in range(10)]
    temp_data = []
    for i in range(max_len):
        for num in data:
            if int(num[max_len-i-1]) == 0:
                temp_list[0].append(num)
            elif int(num[max_len-i-1]) == 1:
                temp_list[1].append(num)
            elif int(num[max_len-i-1]) == 2:
                temp_list[2].append(num)
            elif int(num[max_len-i-1]) == 3:
                temp_list[3].append(num)
            elif int(num[max_len-i-1]) == 4:
                temp_list[4].append(num)
            elif int(num[max_len-i-1]) == 5:
                temp_list[5].append(num)
            elif int(num[max_len-i-1]) == 6:
                temp_list[6].append(num)
            elif int(num[max_len-i-1]) == 7:
                temp_list[7].append(num)
            elif int(num[max_len-i-1]) == 8:
                temp_list[8].append(num)
            elif int(num[max_len-i-1]) == 9:
                temp_list[9].append(num)
        data.clear()
        for temp in temp_list:
            data.extend(temp)
            temp.clear()
    temp_data = data
    return temp_data