共计 4318 个字符，预计需要花费 11 分钟才能阅读完成。
本文介绍常见的八大排序算法：间接插入排序、希尔排序、抉择排序、堆排序、冒泡排序、快排、归并排序以及计数排序
文章内容很干，也很长，不过有多种动图图解，心愿能够给干燥的算法学习带来一抹亮色！
如果对于复杂度还不分明，能够查看上面的文章
01 冒泡排序
对于冒泡排序置信咱们都比拟相熟了，其核心思想就是相邻元素两两比拟，把较大的元素放到前面，在一轮比拟实现之后，最大的元素就位于最初一个地位了，就如同是气泡，缓缓的浮出了水面一样
def bubble_sort(data, reverse=False):
"""
:param data: list type data
:param reverse:
:return: list type data
"""
if not reverse:
for i in range(len(data) - 1):
for j in range(len(data) - 1 -i):
if data[j] > data[j+1]:
data[j], data[j+1] = data[j+1], data[j]
return data
else:
for i in range(len(data) - 1):
for j in range(len(data) - 1 -i):
if data[j] < data[j+1]:
data[j], data[j + 1] = data[j + 1], data[j]
return data 冒泡排序算法还是比拟好了解的，只须要进行两次循环，最外层的循环代表排序元素的个数，外部循环则进行两两比拟，工夫复杂度为 O(n^2)
02 疾速排序
快排的思维为首先任意选取一个数据（通常选用数组的第一个数）作为要害数据，而后将所有比它小的数都放到它后面，所有比它大的数都放到它前面，这个过程称为一趟疾速排序，之后再递归排序两边的数据
def quick_sort(data):
if not data:
return data
first = data[0]
left = quick_sort([l for l in data[1:] if l < first])
right = quick_sort([r for r in data[1:] if r >= first])
return left + [first] + right相比冒泡排序，疾速排序每次替换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全副放到基准点的右边，将大于等于基准点的数全副放到基准点的左边。这样在每次替换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行替换，替换的间隔就大的多了。因而总的比拟和替换次数就少了，速度天然就进步了，工夫复杂度为 O（N*logN）
03 间接插入排序
插入排序的思维是把一个数据插入到一个有序序列中，从而失去一个新的序列加一的有序序列，能够通过下图来进一步加深了解
def insert_sort(data, reverse=False):
if not reverse:
for i in range(1, len(data)):
key = data[i]
j = i - 1
while j >= 0:
if data[j] > key:
data[j+1] = data[j]
data[j] = key
j -= 1
return data
else:
for i in range(1, len(data)):
key = data[i]
j = i - 1
while j >= 0:
if data[j] < key:
data[j+1] = data[j]
data[j] = key
j -= 1
return data因为每次遍历有序序列时，都会有序列中所有的数据做比照，故而工夫复杂度为 O(n^2)
04 抉择排序
抉择排序，是一一确定元素地位的思维。同样是 n 遍循环，第一轮时，每一个元素都与第一个元素比拟，如果比第一个元素大，则与之替换，这样一轮过后，第一个元素就是最小的了，第二轮开始每个元素与第二个地位的元素比拟，如果大，则与第二地位的元素替换，以此类推，达到排序的目标
def selection_sort(data, reverse=False):
"""
:param data: list type data
:param reverse:
:return: list type data
"""
if not reverse:
for i in range(len(data)-1):
min_index = i
for j in range(i+1, len(data)):
if data[j] < data[min_index]:
min_index = j
data[i], data[min_index] = data[min_index], data[i]
return data
else:
for i in range(len(data) - 1):
min_index = i
for j in range(i+1, len(data)):
if data[j] > data[min_index]:
min_index = j
data[i], data[min_index] = data[min_index], data[i]
return data抉择排序和冒泡排序还是很类似的，然而抉择排序会比冒泡排序少一次替换的过程，然而同样是两层循环，所有工夫复杂度也是 O(n^2)
05 并归排序
能够把一个数组分成两半，对于每一个数组当他们是有序的就能够进行一次合并操作。对于他们的两个区间进行递归，始终递归上来划分区间，当区间只有一个值的时候咱们就能够进行合并返回上一层，让上一层合并再返回
def merge(a, b):
c = []
h = j = 0
while j < len(a) and h < len(b):
if a[j] < b[h]:
c.append(a[j])
j += 1
else:
c.append(b[h])
h += 1
if j == len(a):
for i in b[h:]:
c.append(i)
else:
for i in a[j:]:
c.append(i)
return c
def merge_sort(lists):
if len(lists) <= 1:
return lists
middle = len(lists)//2
left = merge_sort(lists[:middle])
right = merge_sort(lists[middle:])
return merge(left, right)归并排序采纳分而治之的原理：首先将一个序列从两头地位分成两个序列，而后再将这两个子序列依照第一步持续二分上来，最初直到所有子序列的长度都为 1，也就是不能够再二分截止。这时候再两两合并成一个有序序列即可。工夫复杂度 O（NlogN)
06 随机疾速排序
随机疾速排序与疾速排序的思路一样，差别就是取主元之前，随机疾速排序多了一个步骤：随机疾速排序是随机获得一个元素，并且会与最初一个元素替换地位。获得主元的下标地位实际上还是最初一个下标，疾速排序是习惯获得最初一个元素作为主元
import random
def random_quicksort(a,left,right):
if(left<right):
mid = random_partition(a,left,right)
random_quicksort(a,left,mid-1)
random_quicksort(a,mid+1,right)
def random_partition(a,left,right):
t = random.randint(left,right) #生成 [left,right] 之间的一个随机数
a[t],a[right] = a[right],a[t]
x = a[right]
i = left-1 #初始 i 指向一个空，保障 0 到 i 都小于等于 x
for j in range(left,right): #j 用来寻找比 x 小的，找到就和 i + 1 替换，保障 i 之前的都小于等于 x
if(a[j]<=x):
i = i+1
a[i],a[j] = a[j],a[i]
a[i+1],a[right] = a[right],a[i+1] #0 到 i 都小于等于 x , 所以 x 的最终地位就是 i +1
return i+1
while(True):
try:
s = input("输出待排序数组：\n") #待排数组
l =s.split()
a = [int(t) for t in l]
random_quicksort(a,0,len(a)-1)
print ("排序后：")
for item in a:
print(item,end=‘‘)
print("\n")
except:
break07 计数排序
首先统计原数组中每个值呈现的次数
而后进行排序：遍历 Count 数组，对应地位的值呈现多少次就往原数组写几个这个值
当然，在对于数据比拟大的时候咱们能够通过绝对映射，让（该值 -min）后的数组加一，最初还原回去即可
def countSort(arr):
max_value = max(arr)
res = []
count_nums = [0 for i in range(max_value + 1)]
for num in arr:
count_nums[num] += 1
for i in range(len(count)):
if count_nums[i] != 0:
# 元素 i 有 count_nums[i]个，增加入最终的排序数组
res.extend(count_nums[i] * [i])
return res08 基数排序
基数排序核心思想是依照低位先排序，而后收集；再依照高位排序，而后再收集；顺次类推，直到最高位。有时候有些属性是有优先级程序的，先按低优先级排序，再按高优先级排序。最初的秩序就是高优先级高的在前，高优先级雷同的低优先级高的在前
def radixSort(arr):
n = len(str(max(arr))) # 记录最大值的位数
for k in range(n):#n 轮排序
# 每一轮生成 10 个列表
bucket_list=[[] for i in range(10)]# 因为每一位数字都是 0~9，故建设 10 个桶
for i in arr:
# 按第 k 位放入到桶中
bucket_list[i//(10**k)%10].append(i)
# 按以后桶的程序重排列表
arr=[j for i in bucket_list for j in i]
return arr明天咱们的排序算法就介绍到这里，前面咱们还会更加深刻的介绍其余数据结构和算法，不要错过哦~
喜爱的小伙伴能够点个赞和关注哦~ 感激你的反对！
