伍六七带你学算法 进阶篇-排序算法
给定一个整数数组 nums，将该数组升序排列。
示例 1：
输入：[5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：[5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
各排序算法解法如下： (如想要了解算法排序原理，见> 十大算法)
public class _912排序数组 {public int[] sortArray(int[] nums) {if(nums.length <=1)return nums;//qSort(nums,0,nums.length-1);//selectSort(nums);// insertSort(nums);// shellSort(nums);// bucketSort(nums);// countSort(nums);// mergeSort(nums,0,nums.length-1);heapSort(nums);return nums;}/**快速排序**/void qSort(int[] arr,int s,int e){int l = s, r = e;if(l < r){int temp = arr[l];while(l < r){while(l < r && arr[r] >= temp) r--;if(l < r) arr[l] = arr[r];while(l < r && arr[l] < temp) l++;if(l < r) arr[r] = arr[l];}arr[l] = temp;qSort(arr,s,l);qSort(arr,l + 1, e);}}/**选择排序**/void selectSort(int[] arr){int min;for(int i = 0;i<arr.length;i++){min = i;for(int j = i;j<arr.length;j++){if(arr[j] < arr[min]){min = j;}}if(min != i) {int temp = arr[i];arr[i] = arr[min];arr[min] = temp;}}}/**** 插入排序：数列前面部分看为有序，依次将后面的无序数列元素插入到前面的有序数列中，初始状态有序数列仅有一个元素，即首元素。在将无序数列元素插入有序数列的过程中，采用了逆序遍历有序数列，相较于顺序遍历会稍显繁琐，但当数列本身已近排序状态效率会更高。** 时间复杂度：O(N2) 稳定性：稳定* @param arr*/public void insertSort(int arr[]){for(int i = 1; i < arr.length; i++){int rt = arr[i];for(int j = i - 1; j >= 0; j--){if(rt < arr[j]){arr[j + 1] = arr[j];arr[j] = rt;}else{break;}}}}/*** 希尔排序 - 插入排序的改进版。为了减少数据的移动次数，在初始序列较大时取较大的步长，通常取序列长度的一半，此时只有两个元素比较，交换一次；之后步长依次减半直至步长为1，即为插入排序，由于此时序列已接近有序，故插入元素时数据移动的次数会相对较少，效率得到了提高。** 时间复杂度：通常认为是O(N3/2) ，未验证 稳定性：不稳定* @param arr*/void shellSort(int arr[]){int d = arr.length >> 1;while(d >= 1){for(int i = d; i < arr.length; i++){int rt = arr[i];for(int j = i - d; j >= 0; j -= d){if(rt < arr[j]){arr[j + d] = arr[j];arr[j] = rt;}else break;}}d >>= 1;}}/*** 桶排序 - 实现线性排序，但当元素间值得大小有较大差距时会带来内存空间的较大浪费。首先，找出待排序列中得最大元素max，申请内存大小为max + 1的桶（数组）并初始化为0；然后，遍历排序数列，并依次将每个元素作为下标的桶元素值自增1；* 最后，遍历桶元素，并依次将值非0的元素下标值载入排序数列（桶元素>1表明有值大小相等的元素，此时依次将他们载入排序数列），遍历完成，排序数列便为有序数列。** 时间复杂度：O(x*N) 稳定性：稳定* @param arr*/void bucketSort(int[] arr){int[] bk = new int[50000 * 2 + 1];for(int i = 0; i < arr.length; i++){bk[arr[i] + 50000] += 1;}int ar = 0;for(int i = 0; i < bk.length; i++){for(int j = bk[i]; j > 0; j--){arr[ar++] = i - 50000;}}}/*** 基数排序 - 桶排序的改进版，桶的大小固定为10，减少了内存空间的开销。首先，找出待排序列中得最大元素max，并依次按max的低位到高位对所有元素排序；* 桶元素10个元素的大小即为待排序数列元素对应数值为相等元素的个数，即每次遍历待排序数列，桶将其按对应数值位大小分为了10个层级，桶内元素值得和为待排序数列元素个数。* @param arr*/void countSort(int[] arr){int[] bk = new int[19];Integer max = Integer.MIN_VALUE;for(int i = 0; i < arr.length; i++){if(max < Math.abs(arr[i])) max = arr[i];}if(max < 0) max = -max;max = max.toString().length();int [][] bd = new int[19][arr.length];for(int k = 0; k < max; k++) {for (int i = 0; i < arr.length; i++) {int value = (int)(arr[i] / (Math.pow(10,k)) % 10);bd[value+9][bk[value+9]++] = arr[i];}int fl = 0;for(int l = 0; l < 19; l++){if(bk[l] != 0){for(int s = 0; s < bk[l]; s++){arr[fl++] = bd[l][s];}}}bk = new int[19];fl = 0;}}/*** 归并排序 - 采用了分治和递归的思想，递归&分治-排序整个数列如同排序两个有序数列，依次执行这个过程直至排序末端的两个元素，再依次向上层输送排序好的两个子列进行排序直至整个数列有序（类比二叉树的思想，from down to up）。** 时间复杂度：O(NlogN) 稳定性：稳定* @param arr*/void mergeSortInOrder(int[] arr,int bgn,int mid, int end){int l = bgn, m = mid +1, e = end;int[] arrs = new int[end - bgn + 1];int k = 0;while(l <= mid && m <= e){if(arr[l] < arr[m]){arrs[k++] = arr[l++];}else{arrs[k++] = arr[m++];}}while(l <= mid){arrs[k++] = arr[l++];}while(m <= e){arrs[k++] = arr[m++];}for(int i = 0; i < arrs.length; i++){arr[i + bgn] = arrs[i];}}void mergeSort(int[] arr, int bgn, int end){if(bgn >= end){return;}int mid = (bgn + end) >> 1;mergeSort(arr,bgn,mid);mergeSort(arr,mid + 1, end);mergeSortInOrder(arr,bgn,mid,end);}/*** 堆排序 - 堆排序的思想借助于二叉堆中的最大堆得以实现。首先，将待排序数列抽象为二叉树，并构造出最大堆；然后，依次将最大元素（即根节点元素）与待排序数列的最后一个元素交换（即二叉树最深层最右边的叶子结点元素）；* 每次遍历，刷新最后一个元素的位置（自减1），直至其与首元素相交，即完成排序。** 时间复杂度：O(NlogN) 稳定性：不稳定** @param arr*/void heapSort(int[] nums) {int size = nums.length;for (int i = size/2-1; i >=0; i--) {adjust(nums, size, i);}for (int i = size - 1; i >= 1; i--) {int temp = nums[0];nums[0] = nums[i];nums[i] = temp;adjust(nums, i, 0);}}void adjust(int []nums, int len, int index) {int l = 2 * index + 1;int r = 2 * index + 2;int maxIndex = index;if (l<len&&nums[l]>nums[maxIndex])maxIndex = l;if (r<len&&nums[r]>nums[maxIndex])maxIndex = r;if (maxIndex != index) {int temp = nums[maxIndex];nums[maxIndex] = nums[index];nums[index] = temp;adjust(nums, len, maxIndex);}}
}以上！
相关文章：
伍六七带你学算法 进阶篇-生命游戏
有趣的算法题–生命游戏 难度-中等 根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰何顿康威在 1970 年发明的细胞自动机。 想要体验生命游戏的小伙伴可以到这里——>生命游戏 进入正题： 给定一个包含 m n 个格子的…
Linux下docker安装配置oracle，oracle创建用户并远程连接，实测可用！
最近在给同学弄毕业设计的数据库，因为oracle在个人电脑上极不稳定，所以他的电脑数据库崩溃了，这时候我就在docker上为他拉了一个oracle，解决了问题。 docker的安装共有以下几步，实测没问题，直接搬去永久可以…
plsql配置多数据源，想换哪个换哪个
现在的公司内部普遍使用plsql对数据库进行管理。而数据库非常多，从测试到线上环境数据库那么多，我们通常使用同一配置管理，便于切换。那么配置数据库连接就成为了很重要的一步。 1、安装plsql （这里大家去下载安装一下࿰…
常见的几种网络抓包及协议分析工具
网络工程师必备技能-抓取网络数据。在本篇博客中，我们将集中记下几个问题进行探讨：Wireshark 是免费的抓取数据包、分析数据包的工具，兼容 Windows、Linux、Mac等主流平台。使用 wireshark 抓包需要的工具是：安装了 wireshark 的 PC。wireshark 抓包的范围是：抓取安装了 wireshark 的 PC 本机的网卡上流经的数据包。其中，网卡指的是 PC 上网使用的模块，常见的包括：以太网网卡、wifi 无线网卡，PC 分别使用它们用于连接以太网、wifi 无线网络。
一文搞懂网络OSI网络模型
在互联网技术里，有两件事最为重要，一个是TCP/IP协议，它是万物互联的事实标准；另一个是Linux操作系统，它是推动互联网技术走向繁荣的基石。在网络编程中最重要的模型便是OSI七层网络模型和TCP/IP四层网络模型七层模型，也称为OSI(Open System Interconnection)参考模型，是国际标准化(ISO)指定的一个用于计算机或通信系统间互联的标准体系。建立七层模型的主要目的是为解决各种网络互联时遇到的兼容性问题。
简单两步，spring aop上手即用即会
面向切面思想在于它的干净，对逻辑代码没有任何侵入性，只需要在想要切入的方法或者类之上加上自定义的注解即可。 首先，就是自定义一个注解： //这里我们定义一个名为 MyPointer 的注解 Documented Retention(RetentionPolicy.RUNTI…
手动将jar包导入pom依赖，让jar包适配本地maven项目
前言： Oracle对maven很久没有更新依赖，虽然19年更新了一版，但pom引入一直有错误。 我用的是oralce 12的依赖，虽然有jar包，但是依赖和pom没有适配，项目打包的时候还要去中央仓库去下载，而中央仓库…
浏览器兼容video视频播放的多种方法&视频在浏览器播放格式，视频浏览器播放格式演示
对于老版本的IE可以通过HTML5shiv来使不支持HTML5的浏览器支持HTML新标签video和audio标签。主要解决HTML5提出的新的元素不被IE6/IE7/IE8识别，这些新元素不能作为父节点包裹子元素，且不能应用CSS样式。让CSS 样式应用在未知元素只需执行 document.createElement(elementName) 即可实现。html5shiv的工作原理也就是基于此。
Linux通过端口号杀死指定进程
前言： 我们在服务器上升级项目的时候，需要将原来的项目停止，然后启动新的项目。 这时候我们只知道应用所占的端口号，如何将进程杀死呢？ linux中杀进程时候，如果你是知道它所占用的端口号的话，可…
Linux/docker下oracle开启监听，开启自动启动
写在前头： 之前呢，使用docker安装了oracle，但它默认是会关闭的。使用了几天以后突然连接异常了，报的问题是oracle监听有问题了，我知道了是oracle服务自动关闭了，监听也跟着关了。所以我找了一些文章&#x…
手把手教你JavaEE的分页查询、分页展示，有了这个，你的项目又多了一个谈资
前言： 我们在写项目的时候，往往有一些项目的信息展示。而展示的数据量往往是很大的，这时候，加入一个分页的功能往往是最理想的选择。 先简单描述一下功能： 根据你的数据量和指定的页面展示数据条数，进行查…
一分钟带你了解什么是“复杂度” 算法上的O(1)、O(n)、O(logn) 这些都是什么❓❓
前言：在最开始学习编程的时候，打开数据结构的书，最显眼的就是排序算法，什么堆排序、希尔排序，然后旁边写着最坏复杂度、最优复杂度、平均复杂度，是一些O(n)、O(logn)、O(n)。这时候我脑子想起一首歌——大朋…
什么是LinkedList？什么时候使用它呢？Java LinkedList结构、用法及源码解析
前言：我们学习java时都知道ArrayList实现List接口，LinkedList也实现List接口，但我们平时用的时候LinkedList却很少被用到。那么，LinkedList什么时候该用到呢？内部又是如何实现的呢？本文对此进行详细说明&am…
Myeclipse中修改项目默认编码还是乱码？一步永久解决！
在myeclipse中修改默认编码后发现项目还是乱码？ 点击Windows选择Preferences 如下图👇 点击General->Content Types->text->选择你要修改的文件类型->选择你要修改的编码格式 （比如我这里是jsp页面乱码）如下图&#…
Myeclipse中项目没有代码错误提示，jsp页面无编译迹象？如何解决
在使用Myeclipse开发项目时，发现jsp页面中嵌入的java代码没有编译的迹象，错误的get方法没有报错，没有报错信息我们如何知道我们开发的内容是正确的呢？ 接下来就演示一下如何解决👉 第一步，点击Project 选择…
伍六七带你学算法 入门篇 ——最大子序和
力扣 53. 最大子序和 难度简单 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大…
伍六七带你学算法 入门篇——最后一个单词的长度
难度 简单 给定一个仅包含大小写字母和空格 ’ ’ 的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。 如果不存在最后一个单词，请返回 0 。 说明：一个单词是指仅由字母组…
伍六七带你学算法 动态规划 ——不同路径
力扣 62. 不同路径 难度 中等 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 问总共有多少条不…
大脑的漏洞：你是如何走向狭隘和顽固的？
但是，我们常常会切断这个链条，只记住最终的结论，忘记了支撑结论的一系列事实、论据、逻辑，从而，任由这个落单的、孤零零的「结论」不断飘摇，不断泛化和极端化。像我在之前的文章里，以及智识营里，都提出过一些比较颠覆性的观点，就经常能看到「难以置信」「感觉自己的世界被颠覆了」「我需要时间去理解和接受」的留言……大脑难以记住复杂的事实，所以，我们会倾向于把事实「压缩」成一个高密度的观点。例如：当你阅读我的文章时，一定不要只记住我给出的「根本原因」和「做法」，也要同时记住「这些原因是怎么来的」「这些做法背后的原理」。
伍六七带你学算法——被忽视的数学公式
中学时候学习那么多的数学，却没有人告诉我们这些数学公式我们以后会用到哪里？疑惑了十好几年，直到，你进入it行业，它的舞台来了！ 在力扣上有一道中度难度的题，题目是这样的👇 &#…
设置linux初始root密码
简单一步设置linux第一个root密码 sudo passwd root #输入当前账户密码 #输入准备设置的root密码 #确认密码如下所示：👇
伍六七带你学算法——栈的使用
大家都知道栈这种数据结构，它有非常多的应用场景。但如果我们不经常接触这些应用场景的话，就可能不太熟悉栈的用法。 目录smd1.栈的创建和使用JAVA Stack类：2.栈的实际应用示范解题如下👇1.栈的创建和使用 JAVA Stack类ÿ…
最优的去重处理——HashSet去重
算法与数据结构是密不可分的，我们使用不同的数据结构和算法的组合就是我们解决问题的答案。 本篇我将就HashSet的特性和使用进行介绍。 HashSet有哪些特性呢？ HashSet继承了Set接口，Set接口有如下特性： 1.元素的无序性 ÿ…
什么是原码、反码、补码？什么是按位与？范围数字按位与！
前言：学过计算机基础的大家都知道什么是二进制，什么是“与”运算，这里先给大家复习一下。 举一个简单的例子： 5的二进制表示是0101（补齐4位） 7的二进制表示是0111（补齐4位） 那么5&a…
不占用多余空间实现值的交换——异或运算
首先什么是异或运算？ ^规则： 0 ^ x x x ^ x 0那么 a 与 b 交换值如何做呢？？？三行代码👇 a a ^ b; b a ^ b; a a ^ b;第一步 a a ^ b 第二步 b （a ^ b）^ b a ^ 0 a …
通用解题法——回溯算法（理解+练习）
积累算法经验，积累解题方法——回溯算法，你必须要掌握的解题方法！ 什么是回溯算法呢？ 回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时ÿ…
linux vi编辑器中的复制粘贴快捷键
在使用vi有时会想直接复制一行数据，然后粘贴若干行进行修改 复制一行数据的方法 把光标放到要复制的一行前面，然后按两下yy字母键 yy # 复制光标所在的那一行然后把光标放到要复制到的地方去，按键盘的p字母键 p # 将已复制的数据粘贴到…
二进制与十进制的小数位怎么转？
二进制转十进制 (0.001)2 ->十进制 从小数点后第一位开始，依次乘2的-1次方 02-1 02-2 12-3 这里已经把上面的小数点后三位全部乘完 然后将结果相加，0 0 0.125 0.125 所以，(0.001)2 的十进制为0.125 十进制转二进制 0.125 -> 二进…
作为一个java程序员，常用的linux命令（越攒越多）
本篇记录我在工作中不断遇到的常用的linux命令，并进行总结，时常更新！ 1. 升级服务时先停止服务，然后进行替换 linux中杀进程时候，如果你是知道它所占用的端口号的话，可以通过 netstat -tunpl | grep 端口…
使用JPA进行update操作时，报org.springframework.beans.factory.BeanCreationException: Error creating bean with
使用JPA进行update操作时，报org.springframework.beans.factory.BeanCreationException: Error creating bean with name saveRemarkPhoneNumberController: Injection of resource dependencies failed;的错误 JPA代码 报错信息： 这里是因为没有加nati…