面试必备:冒泡,选择,插入,希尔,归并,快速排序大合集

2024-06-18 01:48

本文主要是介绍面试必备:冒泡,选择,插入,希尔,归并,快速排序大合集,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

冒泡排序

选择排序

插入排序

希尔排序

归并排序

快速排序


在很多大厂的面试中,算法是最基本的要求,像基础的算法,冒泡,选择,插入等,基本上都会问到。

很多同学往往忽略了其重要程度,只注重编程语言,小编并不建议这样子,今天我们来梳理一下算法,汇总一下面试的一些基础算法。

冒泡排序

原理:每次冒泡排序操作都会将相邻的两个元素进行比较,看是否满足大小关系要求,如果不满足,就交换这两个相邻元素的次序,一次冒泡至少让一个元素移动到它应该排列的位置,重复N次,就完成了冒泡排序。

面试必备:冒泡,选择,插入,希尔,归并,快速排序大合集

 

代码实现

/**
* 冒泡算法
* @author:溪云阁
* @date:2020年5月3日
* 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。
* 如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复n 次,
* 就完成了 n 个数据的排序工作。
*/
public static void bubbleSort(Integer[] arr) {
// 如果只有一个元素就不用排序了
if (arr.length <= 1) {
return;
} else {
// 打印排序后的数组
System.out.println("排序前的数组:" + Arrays.toString(arr));
for (int i = 0; i < arr.length; ++i) {
// 提前退出冒泡循环的标志位,即一次比较中没有交换任何元素,这个数组就已经是有序的了
boolean flag = false;
// 此处你可能会疑问的j<n-i-1,因为冒泡是把每轮循环中较大的数飘到后面,
for (int j = 0; j < arr.length - i - 1; ++j) {
// 数组下标又是从0开始的,i下标后面已经排序的个数就得多减1,总结就是i增多少,j的循环位置减多少
if (arr[j] > arr[j + 1]) {
// 即这两个相邻的数是逆序的,交换位置
final int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true;
}
}
if (!flag)
// 没有数据交换,数组已经有序,退出排序
break;
}
// 打印排序后的数组
System.out.println("排序后的数组:" + Arrays.toString(arr));
}
}

选择排序

原理:先遍历数组,然后找到一个最大或者最小的元素(这个看需要),把这个元素放到第一个位置,接着在剩余的数组中继续找,找到比第一个大或者小的元素,放到第二个位置,依次这样子做,从而完成排序。

面试必备:冒泡,选择,插入,希尔,归并,快速排序大合集

 

代码实现:

/**
* 选择排序
* @author 溪云阁
* @param arr void
* 先遍历数组,然后找到一个最大或者最小的元素(这个看需要)
* 把这个元素放到第一个位置,接着在剩余的数组中继续找
* 找到比第一个大或者小的元素,放到第二个位置
* 依次这样子做,从而完成排序。
*/
public static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
// 用来记录最小值的索引位置,默认值为i
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
// 遍历 i+1~length 的值,找到其中最小值的位置
minIndex = j;
}
}
// 交换当前索引 i 和最小值索引 minIndex 两处的值
if (i != minIndex) {
final int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}

插入排序

原理:这个比较抽象,但是我来划分来辅助理解

一组无序序列{A1,A2,........An}

先取出A1,然后从A2与A1比较,比较完之后序列状况是{A1,A2}{A3..........An},这时候其中{A1,A2}就变成有序

然后取出A3 ,放到{A1,A2}有序序列合适位置,从而形成{A1,A2,A3}{A4........An}

重复这个过程,直到取出An放入{A1,A2........An-1}有序序列中

面试必备:冒泡,选择,插入,希尔,归并,快速排序大合集

 

代码实现:

/**
* 插入排序
* @author 溪云阁
* @param ins
* @return int[]
* 一组无序序列{A1,A2,........An}
* 先取出A1,然后从A2与A1比较,比较完之后序列状况是{A1,A2}{A3..........An},这时候其中{A1,A2}就变成有序
* 然后取出A3 ,放到{A1,A2}有序序列合适位置,从而形成{A1,A2,A3}{A4........An}
* 重复这个过程,直到取出An放入{A1,A2........An-1}有序序列中
*/
public static int[] insertSort(int[] ins) {
for (int i = 1; i < ins.length; i++) {
// 保存每次需要插入的那个数
final int temp = ins[i];
int j;
for (j = i; j > 0 && ins[j - 1] > temp; j--) {
// 把大于需要插入的数往后移动。最后不大于temp的数就空出来j
ins[j] = ins[j - 1];
}
// 将需要插入的数放入这个位置
ins[j] = temp;
}
return ins;
}

希尔排序

原理:希尔排序是插入排序的改进版,它将数组按照约定的数量分成N列,对每一列执行插入排序,接着缩小步长,不断重复这过程,最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法。

面试必备:冒泡,选择,插入,希尔,归并,快速排序大合集

 

代码实现:

/**
* 希尔排序
* @author 溪云阁
* @param arrays void
* 希尔排序是插入排序的改进版,
* 它将数组按照约定的数量分成N列,对每一列执行插入排序,接着缩小步长
* 不断重复这过程,最后整个表就只有一列了
*/
public static void shellSort(int[] arrays) {
if (arrays == null || arrays.length <= 1) {
return;
} else {
// 增量
int incrementNum = arrays.length / 2;
while (incrementNum >= 1) {
for (int i = 0; i < arrays.length; i++) {
// 进行插入排序
for (int j = i; j < arrays.length - incrementNum; j = j + incrementNum) {
if (arrays[j] > arrays[j + incrementNum]) {
final int temple = arrays[j];
arrays[j] = arrays[j + incrementNum];
arrays[j + incrementNum] = temple;
}
}
}
// 设置新的增量
incrementNum = incrementNum / 2;
}
}
}

归并排序

原理:归并其实就是分而治之的思想,对于每一个数组,每个递归过程涉及三个步骤

1、分解::把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.

2、治理::对每个子序列分别调用归并排序MergeSort, 进行递归操作

3、合并:合并两个排好序的子序列,生成排序结果.

面试必备:冒泡,选择,插入,希尔,归并,快速排序大合集

 

代码实现:

/**
* 两路归并算法,两个排好序的子序列合并为一个子序列
* @author 溪云阁
* @param a
* @param left
* @param mid
* @param right void
*/
public static void merge(int[] a, int left, int mid, int right) {
// 辅助数组
final int[] tmp = new int[a.length];
// p1、p2是检测指针,k是存放指针
int p1 = left, p2 = mid + 1, k = left;
while (p1 <= mid && p2 <= right) {
if (a[p1] <= a[p2])
tmp[k++] = a[p1++];
else
tmp[k++] = a[p2++];
}
while (p1 <= mid) {
// 如果第一个序列未检测完,直接将后面所有元素加到合并的序列中
tmp[k++] = a[p1++];
}
while (p2 <= right) {
// 同上
tmp[k++] = a[p2++];
}
// 复制回原素组
for (int i = left; i <= right; i++) {
a[i] = tmp[i];
}
}
/**
* 归并排序
* @author 溪云阁
* @param a
* @param start
* @param end void
*/
public static void mergeSort(int[] a, int start, int end) {
// 当子序列中只有一个元素时结束递归
if (start < end) {
// 划分子序列
final int mid = (start + end) / 2;
// 对左侧的序列进行递归排序
mergeSort(a, start, mid);
// 对右侧的序列进行递归排序
mergeSort(a, mid + 1, end);
// 合并
merge(a, start, mid, end);
}
}

快速排序

原理:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

面试必备:冒泡,选择,插入,希尔,归并,快速排序大合集

 

代码实现:

/**
* 快速排序
* @author 溪云阁
* @param arr 待排序列
* @param leftIndex 待排序列起始位置
* @param rightIndex 待排序列结束位置
*/
public static void quickSort(int[] arr, int leftIndex, int rightIndex) {
if (leftIndex >= rightIndex) {
return;
} else {
int left = leftIndex;
int right = rightIndex;
// 待排序的第一个元素作为基准值
final int key = arr[left];
// 从左右两边交替扫描,直到left = right
while (left < right) {
while (right > left && arr[right] >= key) {
// 从右往左扫描,找到第一个比基准值小的元素
right--;
}
// 找到这种元素将arr[right]放入arr[left]中
arr[left] = arr[right];
while (left < right && arr[left] <= key) {
// 从左往右扫描,找到第一个比基准值大的元素
left++;
}
// 找到这种元素将arr[left]放入arr[right]中
arr[right] = arr[left];
}
// 基准值归位
arr[left] = key;
// 对基准值左边的元素进行递归排序
quickSort(arr, leftIndex, left - 1);
// 对基准值右边的元素进行递归排序。
quickSort(arr, right + 1, rightIndex);
}
}

 

部分图片或源码来源网络,如侵权请联系删除,谢谢!

这篇关于面试必备:冒泡,选择,插入,希尔,归并,快速排序大合集的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1070969

相关文章

如何选择适合孤独症兄妹的学校?

在探索适合孤独症儿童教育的道路上,每一位家长都面临着前所未有的挑战与抉择。当这份责任落在拥有孤独症兄妹的家庭肩上时,选择一所能够同时满足两个孩子特殊需求的学校,更显得尤为关键。本文将探讨如何为这样的家庭做出明智的选择,并介绍星贝育园自闭症儿童寄宿制学校作为一个值得考虑的选项。 理解孤独症儿童的独特性 孤独症,这一复杂的神经发育障碍,影响着儿童的社交互动、沟通能力以及行为模式。对于拥有孤独症兄

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时