# 数据结构与算法——排序——Celia

1212-王同学

, ,

## 冒泡排序

def bubble_sort(alist):
"""冒泡排序"""
n = len(alist)
for j in range(0, n-1):
# 注意这里，到n-2截止所以最后一个应是n-1
# 而冒泡排序
for i in range(0, n-1-j):
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]

if __name__ == "__main__":
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
bubble_sort(li)  # 调用方法的时候直接写即可
print(li)


def bubble_sort(alist):
"""冒泡排序"""
n = len(alist)
for j in range(len(alist)-1, 0, 1):  # j范围表示方法变动
# 注意这里，到n-2截止所以最后一个应是n-1
# 而冒泡排序
for i in range(0, n-1-j):
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]

if __name__ == "__main__":
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
bubble_sort(li)  # 调用方法的时候直接写即可
print(li)


def bubble_sort(alist):
"""冒泡排序"""
n = len(alist)
for j in range(0, n-1):
count = 0  # “班长”从头到尾走一遍，如果直接可行即退出
for i in range(0, n-1-j):
if alist[i] > alist[i+1]:
alist[i], alist[i+1] = alist[i+1], alist[i]
count += 1
if count == 0:
return


## 选择排序

def select_sort(alist):
n = len(alist)
for j in range(0, n-1):
min_index = j
for i in range(j+1, n):
if alist[min_index] > alist[i]:
min_index = i
alist[min_index], alist[j] = alist[j], alist[min_index]

if __name__ == "__main__":
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
select_sort(li)
print(li)


def select_sort(alist):
n = len(alist)
for j in range(0, n-1):
min_index = j
for i in range(j+1, n):
if alist[min_index] > alist[i]:
# min_index = i
alist[i], alist[j] = alist[j], alist[i]

if __name__ == "__main__":
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
select_sort(li)
print(li)


## 插入排序

def insert_sort(alist):
"""插入排序"""
n = len(alist)

for i in range(1, n):
# 从右边的无序序列中取出一个元素，从小到大插入到相应位置
while i > 0:
if alist[i-1] > alist[i]:
alist[i], alist[i-1] = alist[i-1], alist[i]
i -= 1  # 因为前面数列已是有序数列，所以
else:
break  # 检测到某alist[1-1]<alist[i]之后即可停止

if __name__ == "__main__":
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
insert_sort(li)
print(li)


## 希尔排序

gap表示一个间隔，前gap个数的顺序不用特意考虑。
gap需要分别取len(alist)折半取整、再折半取整……1，多次执行希尔排序

def shell_sort(alist):
"""希尔排序"""
n = len(alist)
gap = n//2
while gap > 0:
for i in range(gap, n):
# 从右边的无序序列中取出一个元素，从小到大插入到相应位置
while i > 0:
if alist[i-gap] > alist[i]:
alist[i], alist[i-gap] = alist[i-gap], alist[i]
i -= gap  # 因为前面数列已是有序数列，所以
else:
break
gap //= 2

if __name__ == "__main__":
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
shell_sort(li)
print(li)


## 快速排序

def quick_sort(alist, first, last):
"""快速排序"""
if first >= last:
return

mid_value = alist[first]
low = first
high = last

while low < high:
while low < high and alist[high] >= mid_value:  # 当存在多个与mid相等的值时统一放到mid的一边
high -= 1
alist[low] = alist[high]  # 若遇到一个比mid小的alist[high]则放到low上
# low += 1

while low<high and alist[low] < mid_value:
low += 1
alist[high] = alist[low]
# high += 1
# 从循环退出时low == high
alist[low] = mid_value

# 这时分割成出去low索引处元素的从头开始的alist[:low-1]和直到最后的alist[low+1:]
# 可以执行递归嵌套
# 注意不要用新的列表，要在原列表上排序quick_sort(alist[:low-1])
# quick_sort(alist[low+1:])
# 对low左边的列表执行排序
quick_sort(alist, first, low-1)
# 对low右边的列表执行排序
quick_sort(alist, low+1, last)

if __name__ == "__main__":
li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(li)
quick_sort(li, 0, len(li)-1)
print(li)


## 二分查找

def binary_search(alist, item):
"""二分查找递归"""
n = len(alist)
if n > 0:
mid = n//2
if item == alist[mid]:
return True
elif item < alist[mid]:
return binary_search(alist[:mid], item)
else:
return binary_search(alist[mid+1:], item)
return False

if __name__ == "__main__":
li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
print(binary_search(li, 100))
print(binary_search(li, 54))


def binary_search(alist, item):
"""二分查找非递归"""
n = len(alist)
first = 0
last = n-1
while first <= last:
mid = (first + last)//2
if alist[mid] == item:
return True
elif item < alist[mid]:
last = mid - 1
else:
first = mid + 1
return False

if __name__ == "__main__":
li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
print(binary_search(li, 100))
print(binary_search(li, 54))


Vieu3.3主题

Q Q 登 录