排序算法|面试官：手撕十大排序算法，你会几种？
今天我们就来讨论面试官最喜欢问到的排序算法吧 ， 从冒泡排序、选择排序、插入排序等十大排序算法的排序步骤、代码实现两个方面入手 ， 彻底搞清实现原理 ， 保证面试道路一路畅通 。
01 排序算法的概述所谓排序算法 ， 就是通过特定的算法因式将一组或多组数据按照一定模式进行重新排序 。
这种新序列遵循着一定的规则 ， 体现出一定的规律 ， 因此 ， 经处理后的数据便于筛选和计算 ， 大大提高了计算效率 。
02 排序算法的分类
本文插图
03评价标准 （1）时间复杂度：即从序列的初始状态到经过排序算法的变换移位等操作变到最终排序好的结果状态的过程所花费的时间度量 。
（2）空间复杂度：就是从序列的初始状态经过排序移位变换的过程一直到最终的状态所花费的空间开销 。
（3）稳定性：稳定性是不管考虑时间和空间必须要考虑的问题 ， 往往也是非常重要的影响选择的因素 。
04 实现步骤与代码 冒泡排序（Bubble Sort）
冒泡排序是一种简单直观的排序算法 。 它重复地走访过要排序的数列 ， 一次比较两个元素 ， 如果他们的顺序错误就把他们交换过来 。 走访数列的工作是重复地进行直到没有再需要交换的数据 ， 也就是说该数列已经排序完成 。 这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端 。
（1）算法步骤
步骤1：比较相邻的元素 。 如果第一个比第二个大 ， 就交换他们两个；步骤2：对每一对相邻元素作同样的工作 ， 从开始第一对到结尾的最后一对 。 这步做完后 ， 最后的元素会是最大的数；步骤3：针对所有的元素重复以上的步骤 ， 除了最后一个；步骤4：重复步骤1~3 ， 直到排序完成；
（2）过程演示
本文插图
（3）代码实现 public class BubbleSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝 ， 不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length) for (int i = 1 i < arr.length i++) { // 设定一个标记 ， 若为true ， 则表示此次循环没有进行交换 ， 也就是待排序列已经有序 ， 排序已经完成 。boolean flag = true for (int j = 0 j < arr.length - i j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j] arr[j] = arr[j + 1] arr[j + 1] = tmp flag = false } } if (flag) { break } } return arr }}
选择排序（Selection Sort）选择排序是一种简单直观的排序算法 ， 无论什么数据进去都是 O(n2) 的时间复杂度 。 所以用到它的时候 ， 数据规模越小越好 。
（1）算法步骤
【排序算法|面试官：手撕十大排序算法，你会几种？】步骤1：首先在未排序序列中找到最小（大）元素 ， 存放到排序序列的起始位置；步骤2：再从剩余未排序元素中继续寻找最小（大）元素 ， 然后放到已排序序列的末尾；步骤3：重复步骤2 ， 直到所有元素均排序完毕；
（2）过程演示
本文插图
（3）代码实现 public class SelectionSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { int[] arr = Arrays.copyOf(sourceArray, sourceArray.length) // 总共要经过 N-1 轮比较 for (int i = 0 i < arr.length - 1 i++) { int min = i // 每轮需要比较的次数 N-i for (int j = i + 1 j < arr.length j++) { if (arr[j] < arr[min]) { // 记录目前能找到的最小值元素的下标 min = j } } // 将找到的最小值和i位置所在的值进行交换 if (i != min) { int tmp = arr[i] arr[i] = arr[min] arr[min] = tmp } } return arr }}
推荐阅读
- |某程序员面试支付宝P7，面试已通过，却因为背调没过
- |初学者指南：什么是算法？11行伪代码给你讲明白
- 互联网|最全解密微信红包随机算法
- 中年|编程的乐趣：用Python解算法的经典趣题你知道几个？
- 全息|谷歌量子计算改进图像分类，微美全息5G核心算法助力AI视觉发展
- 青年|人人可用的在线抠图，AI自动化的那种！北大校友的算法玩出新高度
- 中年|5分钟快速了解机器学习基础概念
- |面试官：这个MySql语法都没掌握，你简历怎么写精通数据库呢
- 中年|C/C++编程笔记：快速排序的思路与优化改进
- 大数据&云计算|AWS云服务上线Amazon Braket量子计算，帮助客户探索设计量子算法