|
本文介绍常见的八大排序算法：直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快排、归并排序以及计数排序 文章内容很干，也很长，不过有多种动图图解，希望可以给枯燥的算法学习带来一抹亮色！ 如果对于复杂度还不清楚，可以查看下面的文章 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:
break
复制代码
07 计数排序首先统计原数组中每个值出现的次数 然后进行排序：遍历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 res
复制代码
08 基数排序基数排序核心思想是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前 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
复制代码
今天我们的排序算法就介绍到这里，后面我们还会更加深入的介绍其他数据结构和算法，不要错过哦~ 喜欢的小伙伴可以点个赞和关注哦~感谢你的支持！
|
