当前位置：首页 > news >正文

7- 排序算法

news 来源：原创 2024/9/20 1:42:35

文章目录

前言
一、选择排序（搞明白每轮在干什么）
二、冒泡排序（搞明白每轮在干什么）
三、插入排序
四、快速排序（分治：哨兵划分+递归）
五、归并排序（分治：递归+合并两个有序数组）
六、堆排序（建议学前先好好复习一下前面那篇博客的自顶向下堆化和建堆操作这些）
- 1 暴力堆排序
- 2 优雅的堆排序
七、桶排序（特简单）
八、计数排序
九、基数排序

前言

排序算法有很多种，平时记不住无所谓（现在都是各种高级API，自己写那有哪些高级API稳定啊，除非你能自己发明一种更加高效的排序算法），面试前那几种关键的一定要记住（思路、复杂度哪些）。

【注】：本节排序算法都是以小到大排序。

一、选择排序（搞明白每轮在干什么）

– 小的不断移到左边

思路：（从O索引开始，拿着每一个索引上的元素跟后面的元素依次比较,小的放前面，大的放后面，以此类推。）

1，从0索引开始，跟后面的元素——比较。
2，小的放前面，大的放后面。
3，第一轮循环结束后，最小的数据已经确定放在了索引0的位置。
4，第二轮循环从1索引开始以此类推，第二轮结束第二小的数就放在了索引1的位置。
5，第三轮循环从2索引开始以此类推。
6，不断下去进行n-1轮这个过程排序就完成了

相信还是看不懂或者容易忘记，没关系忘了就看视频选择排序，并且代码怎么写讲的也非常不错

def selection_sort(nums: List[int]):'''选择排序'''n = len(nums)# 外循环，要进行交换操作的轮数for i in range(n - 1):# 内循环，进行交换操作for j in range(i + 1, n):if nums[j] < nums[i]:nums[i], nums[j] = nums[j], nums[i]

复杂度分析：

时间复杂度 $O(n^2)$ ,空间复杂度 $O (1)$

上述选择排序还可以优化一下：每一轮的目标都是将后面部分元素中最小的元素移到最左边的索引位上，我们不必频繁交换元素，只要维护一个记录最小索引的变量即可，这样每轮就只用交换一次。

def selection_sort(nums:List[int]):'''选择排序'''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 = jnums[i],nums[min_index] = nums[min_index], nums[i]

二、冒泡排序（搞明白每轮在干什么）

– 大的不断移到右边
思路：（相邻的元素两两比较，大的放右边，小的放左边）

1，相邻的元素两两比较，大的放右边，小的放左边。
2，第一轮循环结束，最大值已经找到，在数组的最右边。
3，第二轮循环只要在剩余的元素找最大值就可以了。
4，每二轮循环结束，次大值已经确定，第三轮循环继续在剩余数据中循环。
不断进行下去进行 n-1轮这样的操作就可以排序完成
上述过程可以看视频中的动图冒泡排序，并且代码怎么写讲的也非常不错

【注】：忘了就去看视频，视频一看就明白，总会记住的。

注意点：

1，相邻的元素两两比较，大的放右边，小的放左边（核心思想）。
2，第一轮比较完毕之后，最大值就已经确定，第二轮可以少循环一次，后面以此类推。
3，如果数组中有n个数据，总共我们只要执行n-1轮的代码就可以。

def bubble_sort(num:List):'''冒泡排序'''n = len(nums)for i in range(n-1):     # 外循环，执行冒泡操作的轮数for j in range(n-1-i):   # 内循环：未排序区间进行冒泡操作# -1 是因为 j 从 0 开始，所以 j+1 不能超出索引，防止索引越界# -i 是为了提高效率，因为每一轮冒泡操作都会将最大的元素放到最后；所以每一轮冒泡操作都会减少一个元素（如果不-i也可以排序不会报错）if nums[j] > nums[j+1]:nums[j],nums[j+1] = nums[j+1],nums[j]