基础排序算法(附加java实现)
2020-06-02 16:08:03来源:博客园 阅读 ()
基础排序算法(附加java实现)
七种基本的排序算法以及java代码实现七种最基本的排序算法:(面试必会!)
冒泡排序:
最基础的排序算法,从数列最前端开始,两两比较,如果前一个数比后一个数大,那么两个数就交换位置,经过一轮遍历之后,最大的数就到了数列的最后一个位置上,再进行下一次循环,第二大的数就浮到了倒数第二个位置,这样一步步较大的数往上浮的过程就是冒泡排序。
java实现:
1 public void bubbleSort(int[] arr) { 2 for (int i = 0; i < arr.length; i++) { 3 for (int j = 0; j < arr.length - 1; j++) { 4 if(arr[j] > arr[j+1]) { 5 arr[j] = arr[j]^arr[j+1]; //通过一个数异或同一个数两次,结果不变 6 arr[j+1] = arr[j]^arr[j+1]; //的方法将两个数的值进行交换 7 arr[j] = arr[j]^arr[j+1]; 8 } 9 } 10 } 11 }
时间复杂度 O(n^2),空间复杂度O(1),稳定性(a=b,排序前a在b的前面,排序后仍在前即为稳定):稳定
选择排序:
将一个数列看成有序区和无序区,刚开始,有序区没有元素,无序区就是整个列表。将无序区的最大(或者最小)的元素找到,并与无序区的第一个元素交换位置,那么这时,无序区的第一个元素就是最大(或者最小的),此时无序区就变为第一个元素之后的剩余元素,再对剩余元素进行找最大(或者最小)元素的操作,并再把该元素与此时无序区第一个元素位置互换,依次类推,那么整个数列中最大(或者最小)的元素就依次排在了数列中
Java实现:(注意:选择排序在实现时,是记录最大值的索引,如果出现更大的值,就更新索引,最后通过索引互换元素)
1 public void selectSort(int[] arr) { 2 int subMin; 3 for (int i = 0; i < arr.length - 1; i++) { 4 subMin = i; 5 for (int j = i + 1 ; j < arr.length; j++) { 6 if(arr[j] < arr[subMin]) { 7 subMin = j; 8 } 9 } 10 if (i != subMin) { //一定要加这个判断,不然当i=subMin的时候,两个相同的数异或为零 11 arr[i] = arr[i]^arr[subMin]; 12 arr[subMin] = arr[i]^arr[subMin]; 13 arr[i] = arr[i]^arr[subMin]; 14 } 15 } 16 }
时间复杂度 O(n^2),空间复杂度O(1),稳定性:不稳定
插入排序:
插入排序也比较直观,通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
1 public void insertSort(int[] arr) { 2 3 //从下标为1的元素开始选择合适的位置插入,因为下标为0只有一个元素,默认是有序的 4 for (int i = 1; i < arr.length; i++) { 5 6 //tmp为要插入的元素 7 int tmp = arr[i]; 8 9 //j表示已排序部分的索引,它将逐渐自减 10 int j = i; 11 12 //挪位置 13 while (j>0 && tmp<arr[j-1]) { 14 arr[j] = arr[j-1]; 15 j--; 16 } 17 18 //插入 19 if(j!=i) { 20 arr[j] = tmp; 21 } 22 } 23 }
插入排序在实现上,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
时间复杂度 O(n^2),空间复杂度O(1),稳定性:稳定
希尔排序:
插入排序的改进版,确定一个间隔,然后根据这个间隔进行分组,这个间隔通常为总长度的一半,奇偶数均可。先进行组内排序,组内排序用插入排序的方法。当每组排完序以后,间隔数减半,重新进行分组并进行插入排序,知道间隔数为1,那么此时对整个数组进行插入排序。
那么为什么使用希尔排序呢?那是因为,当数列元素数目多大的时候, 插入排序的比较次数会远远大于希尔排序。
Java实现
1 public void shellSort(int[] arr) { 2 3 int gap = 1; 4 5 while (gap<arr.length) { 6 gap = gap * 3 + 1; 7 } 8 9 while(gap>0) { 10 for (int i = gap; i < arr.length; i++) { 11 int tmp = arr[i]; 12 int j = i-gap; 13 while (j>=0 && arr[j]>tmp) { 14 arr[j+gap] = arr[j]; 15 j = j-gap; 16 } 17 arr[j+gap] = tmp; 18 } 19 gap = (int) Math.floor(gap/3); 20 } 21 }
时间复杂度 O(n^1.3),空间复杂度O(1),稳定性:不稳定
推荐B站视频:https://www.bilibili.com/video/BV1rE411g7rW [算法]六分钟彻底弄懂希尔排序,简单易懂 by新原家龙之介
归并排序:
核心思想为分治法,并通过递归实现。将长度为n的序列分成两个长度为n/2的子序列,对这两个子序列分别采用归并排序,最后将两个排序好的子序列合并成一个最终的排序序列。
Java代码待更新
...
时间复杂度 O(nlog以2为底n的对数),空间复杂度O(n),稳定性:稳定
快速排序:
快速排序也是分治法加递归的思想,首先从数列中挑出一个元素作为基准(pivot);重新排列数列,所有比基准小的元素放在基准前面,所有比基准大的摆在后面,(相同的数可以到仍一边)。在这个分区退出以后,该基准就处在数列的中间位置。递归地把小于基准值元素的子数列和大于基准值元素的子数列排列。
Java代码待更新
....
时间复杂度 O(nlog以2为底n的对数),空间复杂度O(nlog以2为底n的对数),稳定性:不稳定
堆排序:
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:
- 大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;
- 小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列;
Java代码实现待更新:
...
时间复杂度 O(nlog以2为底n的对数),空间复杂度O(1),稳定性:不稳定
可参考B站视频:https://www.bilibili.com/video/BV1Gb411a7o3?from=search&seid=13649039337940123139
原文链接:https://www.cnblogs.com/AICROC/p/13027968.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 04.Java基础语法 2020-06-11
- DES/3DES/AES 三种对称加密算法实现 2020-06-11
- 1-Java基础回顾整理_01 2020-06-10
- Java基础语法菜鸟教程笔记 2020-06-10
- Java基础复习——类和对象 2020-06-09
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash