排序算法中的稳定性
排序算法中的稳定性
1. 相同的大小的元素在排序完成后相对位置没有发生改变，就是稳定的
1. 选择基准分割数组为两个字数组，小于基准和大于基准
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
data = [2,4,5,2,1,7,8,5,3,9]
def quicksort(data):
if len(data) < 2: # 当数据只剩一个的时候就返回
return data
datum_index = 0 # 去下标为0作为基准值
left = [] # 小于基准值的数组
right = [] # 大于基准值的数据
for d in data[1:]: # 从1开始遍历
if d <= data[datum_index]: left.append(d)
else: right.append(d)
return quicksort(left) + [data[datum_index]] + quicksort(right) # 把基准值排序完的数据再进行排序
print(quicksort(data)) # 输出：[1, 2, 2, 3, 4, 5, 5, 7, 8, 9]
归并排序
1. 把数组一半一半进行分割
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
def merge_sorted(data_1, data_2): # 合并两个有序的数组
if len(data_1) == 0 or len(data_2) == 0: # 如果其中一个数组为空，可直接返回
return data_1 + data_2
left=right=0
new_data = []
while left < len(data_1) and right < len(data_2): # 两个数组其中一个数据用完就退出循环
if data_1[left] <= data_2[right]:
new_data.append(data_1[left])
left += 1
else:
new_data.append((data_2[right]))
right += 1
if left < len(data_1): new_data += data_1[left:] # 若数组一还有剩余数据，补充
if right < len(data_2): new_data += data_2[right:] # 若数组二还有剩余数据，补充
return new_data
def mergesort(data): # 归并排序
if len(data) <= 1: # 若数组只有一个，已经有序，返回
return data
mid = len(data)//2 # 获取中间切分下标
left = mergesort(data[:mid]) # 左边递归归并排序
right = mergesort(data[mid:]) # 右边递归归并排序
return merge_sorted(left, right) # 把两个有序的数组合并
print(mergesort([1,5,6,7,8,9,10,1,2,3,4]))
冒泡排序
1. 从第一位开始，依次与后面对比大小，大的进行交换，最后把数组后面是最大的元素
1
2
3
4
5
6
7
if __name__ == '__main__':
data = [2,5,1,3,7,0,1,7,9,3,6]
for index in range(len(data)):
for index_2 in range(len(data[:-index])):
if data[index_2] > data[index_2+1]:
data[index_2], data[index_2+1] = data[index_2+1], data[index_2]
print(data)
选择排序
1. 从第一位开始，去找后面比第一位小的数，交换两个数，依次类推
1
2
3
4
5
6
7
8
9
10
11
if __name__ == '__main__':
data = [2,5,1,3,7,0,1,7,9,3,6]
length = len(data)
for index in range(len(data)):
min_index = index
for index_2 in range(index+1, length):
if data[index_2] < data[min_index]:
min_index = index_2
data[index], data[min_index] = data[min_index], data[index]
print(data)
