基础算法-排序
文章目录
冒泡排序 bubbleSort
基本原理：比较相邻两个数字的大小，比较大的数放在靠后的位置。不断的交换直到最大的数都放在尾部
小的元素浮到上面来，大的元素沉到下面去
实现代码
def randomList(n):
makeList = []
for i in range(n):
makeList.append(random.randint(0,1000))
return makeList
def bubbleSort(iList):
if len(iList) <= 1:
return iList
else:
for i in range(len(iList) - 1):
for j in range(len(iList)-1-i):
if iList[j] > iList[j + 1]:
iList[j], iList[j + 1] = iList[j + 1], iList[j]
print(iList)
选择排序 selectionSort
基本原理：在序列中不断的找最小（大）的数，得到下标，之后再找次小（大）的元素，交换位置
实现代码
def selectionSort(iList):
if len(iList) == 0:
return iList
else:
for i in range(len(iList) - 1):
if iList[i]!=min(iList[i:]):
# min 函数找剩下元素的最小元素下标
minIndex = iList.index(min(iList[i:]))
iList[minIndex], iList[i] = iList[i], iList[minIndex]
print(iList)
插入法排序 insertionSort
基本原理：形同于扑克牌的排序
实现代码
def insertionSort(iList):
if len(iList) <=1:
return iList
else:
for right in range(1, len(iList)):
target = iList[right]
for left in range(0, right):
if target <= iList[left]:
iList[left + 1:right + 1] = iList[left:right]
iList[left] = target
break
print(iList)
归并排序 mergeSort
基本原理：一种递归排序
将数列分成两部分，左右两部分排好了再合并到一起成为一个有序序列
实现代码
def mergeSort(iList):
if len(iList) <= 1:
return iList
else:
middle = len(iList) // 2
left, right = iList[0:middle], iList[middle:]
return mergeList(mergeSort(left), mergeSort(right))
def mergeList(left, right):
mList = []
while left and right:
if left[0] >= right[0]:
mList.append(right.pop(0))
else:
mList.append(left.pop(0))
# 退出循环的时候 left，right都为空了或者一方为空
# 现在需要直接把剩下的元素拼接到mList上边去
print(left,right)
while left:
mList.append(left.pop(0))
while right:
mList.append(right.pop(0))
return mList
快速排序 quickSort
基本原理：递归排序，缺点是浪费空间
以列表的任意一个数为基准（一般选择第一个数），将列表分成左右两的部分：左边列表的数要比基准小，右边列表的数要比基准大；左右列表依照相同的方式继续分解，比较，直到不可再分为止。最后 左边子列表+基准+右边子列表 合并起来
实现代码
def quickSort(iList):
if len(iList) <= 1:
return iList
else:
base = iList[0]
left = []
right = []
for i in iList[1:]:
# left 存储的都是比base小的
if i <= base:
left.append(i)
else:
right.append(i)
print(left, right)
# 递归的对左右两个部分排序，得到left right的有序
return quickSort(left)+[base]+quickSort(right)
计数排序 countingSort
基本原理：选择一个数为基数，然后统计整个序列中有多少个数比基数小。新建一个等长度的序列，如果有n个数比基数小，基数放到新序列的第n+1个位置上
实现代码
def countingSort(iList):
if len(iList) == 1:
return iList
else:
countList = [None] * len(iList)
for i in range(len(iList)):
small = 0
same = 0
for j in range(len(iList)):
if iList[j]<iList[i]:
small += 1
if iList[j]==iList[i]:
same += 1
# 给新的列表countList赋值
for m in range(small,small + same):
countList[m]=iList[i]
return countList