五种排序算法python语言实现
1.冒泡排序
思想： 依次循环遍历，没什么好说的，循环就完事了。每个数据都需要排列，i表示当前位置元素，第j个元素需要对比元素个数，n-1-i表示每行需要对比的最多次数，冒泡排序时间复杂度为O(n²)
def bubbleSort(list,n):
if n <= 1:
return list
for i in range(n): #表示行
flag = False #表示是否有数据交换
for j in range(n-1-i): #表示每行的下标
if list[j] > list[j+1]:
list[j],list[j+1] = list[j+1],list[j]
flag = True
if flag == False:
break
return list
list = [8,1,9,3,4,2,6,7]
n = len(list)
f = bubbleSort(list,n)
运行结果：
2.插入排序
思想：插入排序的工作方式就像许多人排列手中扑克牌一样。一般都是右手去拿桌子上的牌面向下的牌，然后从牌堆上拿走一张牌并将它插入左手中正确的位置. 为了找到这张牌的正确位置，一般都是将它与已在手中的每张牌进行比较,拿在左手中的牌总是排序好的. 时间复杂度为O(n²)
def insertSort(list,n):
if n <= 1:
return list
for i in range(1,n): #未排序区间
value = list[i]
for j in range(i,-1,-1): #排序过程
if value < list[j-1]: #如果value小于它前面的数。
list[j] = list[j-1] #就和它前面的数字换位置
else: #若没有，表示当前value为已排序区间最大值
break
list[j] = value
return list
list1 = [1,9,4,23,11,56,8,43,6,7]
print(list1)
n = len(list1)
a = insertSort(list1,n)
print(a)
运行结果：
3.选择排序：
思想：原理同插入排序。也分已拍区间和未拍区间，选择排序会从每次未排序的区间中找到最小元素，将其放到已排序区间末尾 选择排序刚开始没有已排序，找到最小元素，放到开始。或者末尾.时间复杂度为O(n²)
def selectionSort(list):
if len(list) <= 1:
return list
for i in range(len(list)-1):
min_index = i #记录最小位置
for j in range(i+1,len(list)):
if list[j] < list[min_index]:
min_index = j
if min_index != i:
list[i],list[min_index] = list[min_index],list[i]
return list
list1 = [1,9,4,23,11,56,8,43,6,7]
print(list1)
a = selectionSort(list1)
print(a)
运行结果：
4.归并排序：
思想：如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。归并排序使用了二分法，归根到底的思想还是分而治之。拿到一个长数组，将其不停的分为左边和右边两份，然后以此递归分下去。 然后再将她们按照两个有序数组的样子合并起来。.时间复杂度为O(nlogn)
def merge(a, b): #接受两个列表
c = [] #定义了一个新列表
h = j = 0 #两个变量
while j < len(a) and h < len(b): #当j<列表a的长度。当h小于列表b的长度
if a[j] < b[h]: #如果a的j小于b的h，c添加a[j]，j再+1
c.append(a[j])
j += 1
else:
c.append(b[h]) #反言之c添加b[h]，h+1
h += 1
if j == len(a): #当j到a的末尾了
for i in b[h:]: #列表c添加列表b从h位到末尾的值
c.append(i)
else:
for i in a[j:]: #反之列表c添加列表a从j位到末尾的值
c.append(i)
return c
def merge_sort(lists):
if len(lists) <= 1:
return lists
middle = len(lists)//2 #将列表分成两份，放到merge中
left = merge_sort(lists[:middle])
right = merge_sort(lists[middle:])
return merge(left, right)
if __name__ == '__main__':
a = [14, 2, 34, 43, 21, 19]
print(a)
print (merge_sort(a))
运行结果：
5.快速排序：
思想：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。 时间复杂度：O(nlgn)
import random
def getrandata(num):
a = []
i = 0
while i <num:
a.append(random.randint(0,100))
i += 1
return a
def quicksort(num_list):
lenth = len(num_list)
if lenth <= 1:
return num_list
temp = random.randint(0,lenth-1)# 随便取的一个数，作为列表索引
tempval = num_list[temp]
left = []
right = []
for i in range(0,lenth):
if num_list[i] > tempval:
right.append(num_list[i])
else:
left.append(num_list[i])
return quicksort(left)+quicksort(right)
if __name__ == '__main__':
a = getrandata(10)
print(a)
b = quicksort(a)
print(b)
运行结果：
希望能给后来学习的人一点启示。
