【注】文章动态取自菜鸟教程。
一点小闲话
知道算法这玩意已经很晚的时间了，也买过几门相关的课程/专栏，但是都不甚满意。不是科班出身，自然希望课程能够带我循序渐进的入门。
对算法比较重视，并开始刷题大概也是进了饭佬的那个群，看到几个厉害的大佬都在刷，我就重拾了兴趣，准备刷一刷。
的确很难，工作中也用不到，又不进大厂。但我为什么要刷呢？可能天生就喜欢难的东西，也有眼高手低的毛病。嗯，也是想给即将奔三的同学做一个榜样，我们一样还是很能打的哦。
如果你也是初学者，没刷过算法，也想学一学，我们一起哈。
我大致罗列了一下需要了解的基础知识：数据结构与算法的概念，查找与搜索，常见的排序算法，堆与栈，顺序表，链表，树与树算法。
了解之后就可以去力扣和牛客上拼命的刷题了，锻炼一下脑力吧。
今天我们先介绍几种常见的排序算法。
有些写法不一定是最优解，但我觉得这个解法更容易理解，仅此而已。
冒泡排序
冒泡排序算法的运作如下：比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。 针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
image
#冒泡排序
def bubble_sort(nums):
n=len(nums)
for i in range(n-1):#0到n-1，一共n个数
for j in range(n-i-1):#每次比较之后，有一个数会排好序
if nums[j]>nums[j+1]:
nums[j],nums[j+1]=nums[j+1],nums[j]
return nums
def bubble_sort2(nums):
n=len(nums)
count=0 #当数组有序的时候，只进行一次遍历即可排完
for i in range(n-1):
for j in range(n-i-1):
if nums[j]>nums[j+1]:
count+=1
nums[j],nums[j+1]=nums[j+1],nums[j]
if count==0:
break
return nums
def bubble_sort3(nums):
n=len(nums)
for j in range(n-1,0,-1):#每次排序减少一个步长
for i in range(j):
if nums[i]>nums[i+1]:
nums[i],nums[i+1]=nums[i+1],nums[i]
return nums
print(bubble_sort([1, 5, 7, 2, 8, 0, 1, 6]))
print(bubble_sort2([1, 5, 7, 2, 8, 0, 1, 6]))
print(bubble_sort3([1, 5, 7, 2, 8, 0, 1, 6]))
选择排序
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
image
#选择排序
def select_sort(nums):
n=len(nums)
for i in range(n-1):
min_index=i
for j in range(i+1,n):
if nums[j]<nums[min_index]:
min_index=j #先找出最小或者最大值
if min_index !=i: #某一个最大或者最小值回到正确的位置
nums[min_index],nums[i]=nums[i],nums[min_index]
return nums
print(select_sort([1, 5, 7, 2, 8, 0, 1, 6]))
插入排序
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
image
#插入排序
def insert_sort(nums):
n=len(nums)
for i in range(1,n):
for j in range(i,0,-1):
if nums[j]<nums[j-1]:
nums[j],nums[j-1]=nums[j-1],nums[j]
return nums
print(insert_sort([1, 5, 7, 2, 8, 0, 1, 6]))
快速排序
从数列中挑出一个元素，称为"基准"（pivot），重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
image
#快速排序
def quick_sort(nums, start, end):
left = start
right = end
if left > right:
return
mid = nums[left]
while left < right and nums[right] > mid:
right -= 1
nums[left] = nums[right]
while left < right and nums[left] < mid:
left += 1
nums[right] = nums[left]
nums[left]=mid
quick_sort(nums, 0, left-1)
# 这里有个地方一直不是很明白，为啥一定是left-1,left编辑器会报错。
quick_sort(nums, left+1, end)
return nums
print(quick_sort([1, 5, 7, 2, 8, 0, 1, 6],0,7))
希尔排序
没理解，就不写了。
归并排序
将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
image
这里还是有那么一点模糊，如何合并的？
def merge_sort(nums):
if len(nums) == 1:
return nums
mid = len(nums) // 2
left_sort = merge_sort(nums[:mid])
right_sort = merge_sort(nums[mid:])
print('left',left_sort)
print('right',right_sort)
return merge(left_sort, right_sort)
def merge(left, right):
l, r = 0, 0
result = []
while l < len(left) and r < len(right):
if left[l] < right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result += left[l:]
result += right[r:]
return result
print(merge_sort([1,7,4,88,90,5,8,33]))
资料推荐
之前说到没有遇到好的资料，但是下面这些看着不错，至少看了能入门，原理大致了解了。
网友评论