常用排序算法
2019-04-09 本文已影响0人
Radiance_sty
1.冒泡排序
- 又称交换排序法，原理是：从第一个元素开始，比较相邻元素的大小，若大小顺序有误，则对调顺序后再进行下一个元素的对比。如此扫描过一次之后就可确保最后一个元素位于正确的顺序，接着再进行第二次扫描，直到所有元素的排序关系为止。这里看出是对一个序列进行移动交换操作，它的时间复杂度为O(n^2)。
其示意图如下图所示：
冒泡排序
''' 冒泡排序 '''
def bubble_sort(list):
n = len(list)
count = 0
for j in range(n-1):
for i in range(n-1-j):
if list[i] > list[i+1]:
list[i],list[i+1] = list[i+1],list[i]
count += 1
if count == 0:
return
#list有n个数，需要进行n-1次排序
#从左往右排序，第一次排序移动n-2次，第二次排序移动n-3次...
if __name__ == '__main__':
list = [65,12,33,72,5,8,45,28]
print(list)
bubble_sort(list)
print(list)
2.插入排序
- 从数据最左拿一个元素，然后与第二个元素比较进行排序，组成新的序列，再将新的序列与第三个元素比较进行排序，重复上述操作最后得到正序或者倒序的数据。这里可以看成是两个序列，将旧序列最左的元素添加到新序列中并进行排序。
其示意图为：
插入排序
''' 插入排序 '''
def insert_sort(list):
n = len(list)
for j in range(1,n):
i = j
while i > 0:
if list[i] < list[i-1]:
list[i],list[i-1] = list[i-1],list[i]
i -= 1
else:
break
# i代表能蹭循环起始值
# i=j 执行从右边的无序序列中取出第一个元素，即i位置，插入前面正确的位置
if __name__ == '__main__':
list = [65, 12, 33, 72, 5, 8, 45, 28]
print(list)
insert_sort(list)
print(list)
3.选择排序
- 从序列最左边拿出一个元素作为初始值，与右边序列的每个值进行对比，若右边的值小于初始值，交换元素，直到整个右边的元素对比完毕；然后取出右边序列最左边元素作为初始值，重复上述步骤，最后组成新的序列。
其示意图为：
选择排序
''' 选择排序 '''
def select_sort(list):
n = len(list)
for j in range(0,n-1):
min_index = j
for i in range(j+1,n):
if list[min_index] > list[i]:
min_index = i
list[j],list[min_index] = list[min_index],list[j]
#将最左边的的值作为初始值与右边的值进行对比，当右边的值小于初始值，交换元素，直到整个右边对比完
#将对比的结果作为最左边的值，从第二位开始，重复第一步的步骤
if __name__ == '__main__':
list = [65, 12, 33, 72, 5, 8, 45, 28]
print(list)
select_sort(list)
print(list)
4.希尔排序
- 选取一个步长，例如 1 2 3 4 5 6，步长为2的话，会把数组分成1 3 5，2 4 6，这样分开之后对每部分进行直接插入排序，下一步缩小步长继续上述步骤，直至步长为1。
其示意图如下图所示：
希尔排序
''' 希尔排序 '''
def shell_sort(list):
n = len(list)
gap = n // 2
while gap > 0:
for j in range(gap,n):
i = j
while i > 0:
if list[i] < list[i-gap]:
list[i],list[i-gap] = list[i-gap],list[i]
i -= gap
else:
break
if __name__ == '__main__':
list = [65, 12, 33, 72, 5, 8, 45, 28]
print(list)
shell_sort(list)
print(list)
5.快速排序
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
其示意图如下图所示：
快速排序
# 快速排序-分而治之
def quickSort(list):
# 基线条件：为空或只包含一个元素的数组是“有序”的
if len(list) < 2:
return list
else:
pivot = list[0]
# 由所有小于基准值的元素组成的子数组
low = [i for i in list[1:] if i <= pivot]
# 由所有大于基准值的元素组成的子数组
high = [i for i in list[1:] if i > pivot]
return quickSort(low) + [pivot] + quickSort(high)
if __name__ == '__main__':
list = [65, 12, 33, 72, 5, 8, 45, 28]
print(list)
list = quickSort(list)
print(list)
6.归并排序
- 把长度为n的输入序列分成两个长度为n/2的子序列；对这两个子序列分别采用归并排序；将两个排序好的子序列合并成一个最终的排序序列。
其示意图如下图所示：
归并排序
'''归并排序'''
def merge_sort(list):
n = len(list)
if n <= 1:
return
mid = n//2 #拆分序列
#left采取归并排序后形成的有序的新的列表
left_list = merge_sort(list[:mid])
#right采取归并排序后形成的有序的新的列表
rigth_list = merge_sort(list[mid:])
#将两个子序列合并成一个新的整体
left_point,right_point = 0,0
result = []
while left_point < len(left_list) and right_point < len(rigth_list):
if left_list[left_point] < rigth_list[right_point]:
result.append(left_list[left_point])
left_point += 1
else:
result.append(rigth_list[right_point])
right_point += 1
result += left_list[left_point]
result += rigth_list[right_point]
return result
if __name__ == '__main__':
list = [65, 12, 33, 72, 5, 8, 45, 28]
print(list)
merge_sort(list)
print(list)
7.二分法查找
''' 二分法查找 '''
def binary_search(list,item): #二分法查找,递归
n = len(list)
if n > 0:
mid = n // 2
if list[mid] == item:
return True
elif item < list[mid]:
return binary_search(list[:mid],item)
else:
return binary_search(list[mid+1:],item)
return False
def binary_search_(list,item): #二分查找,非递归
n = len(list)
first = 0
last = n-1
while first <= last:
mid = (first+last)//2
if list[mid] == item:
return True
elif item < list[mid]:
last = mid-1
else:
first = mid+1
return False
if __name__ == '__main__':
list = [5,8,12,28,33,45,65,72]
print(binary_search(list,33))
print(binary_search(list,99))
print(binary_search_(list,33))
print(binary_search_(list,99)) 
