数据结构排序算法 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