最近在看一些代码优化相关的东西,下午看到排序这块,常用的排序方式有冒泡排序、选择排序、快速排序等,这里记录下这三种排序的Java实现。最后附有2个测试这几种排序方式的时间的代码
一、几种常用排序方式介绍
1.冒泡排序
以升序排序为例,将序列看成一排竖着的气泡,最后一个元素与倒数第二个元素进行比较,小的往前移,再将倒数第二个元素与倒数第三个元素比较,依次类推,第一轮比较后,最小的就到了位置1,同样第二轮比较后第二小的到了位置二~
#PopSortDemo.java
/** * 冒泡排序 * * @author admin * */ public class PopSortDemo implements Sorted { public void sort(int[] array) { for (int i = 0; i < array.length; i++) { for (int j = array.length - 1; j > i; j--) { if (array[j] < array[j - 1]) { SortUtil.exchange(array, j, j-1); } } } } }
总结:
1). 需要比较的次数和数组长度有关[1+2+3+4~+(n-1)]
2). 需要排序数组长度越长,效率下降明显:n为10时需要比较45次,但n为100时比较次数直线上升到4950次,相差100多倍
2.冒泡排序(改进算法)
针对冒泡算法,如果有一轮没有发生交换,说明每个相邻位置不需要交换,即每个位置已经排好了,后面就可以不用继续了
#PopSortImproveDemo.java
/** * 冒泡排序算法(改进):如果有一轮没有发生交换,说明位置已经排好了,后面就可以不用继续了 * @author admin * */ public class PopSortImproveDemo implements Sorted { public void sort(int[] array) { boolean changed = true; for (int i = 0; i < array.length && changed; i++) { changed = false; for (int j = array.length - 1; j > i; j--) { if (array[j] < array[j - 1]) { changed = true; SortUtil.exchange(array, j, j - 1); } } } } }
总结:
1). 需要比较的次数和数组长度有关,最多比较[1+2+3+4~+(n-1)] 次,最少比较[n-1]次(初始就是有序的)
3.选择排序
先找出最小的数,放到第一个,找出后面数中,第二小的,放到第二个,以此类推。
/** * 选择排序 * * @author admin * */ public class SelectSortDemo implements Sorted { public void sort(int[] array) { int pos; for (int i = 0; i < array.length; i++) { pos=i; for (int j = i + 1; j < array.length; j++) { if (array[pos] > array[j]) { pos=j; } } if(pos!=i) SortUtil.exchange(array, pos, i); } } }
总结:
1). 比较次数和冒泡排序算法相同
2). 之前一直把选择排序记成冒泡排序,实际有区别的(*+﹏+*)~@
4.快速排序
选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分
/** * 快速排序:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分 * @author admin * */ public class QuickSortDemo implements Sorted { public void sort(int[] array) { sort(array, 0, array.length - 1); } /** * 递归调用排序:排序基准位置前后子数组 * * @param array * @param start * @param end */ public void sort(int[] array, int start, int end) { if (start < end) { int pos = findMiddle(array, start, end); sort(array, start, pos - 1); sort(array, pos + 1, end); } } /** * 获取基准元素位置 */ public int findMiddle(int[] array, int start, int end) { int temp = array[start]; while (start < end) { // 结束位置递减,直到找到第一个比标准位置值小的 while (start < end && array[end] >= temp) { end--; } // 基准位置交换到end array[start] = array[end]; // 开始位置递增,直到找到第一个比标准位置值大的 while (start < end && array[start] <= temp) { start++; } // 基准位置交换到start array[end] = array[start]; } // 记录基准位置值 array[start] = temp; return start; } }
总结:
1) 速度比较快,当然前提是基准位置找的好\(`▽′)/
2) 最差的情况,需要找[n-1]次基准位置,找基准位置的过程中总共循环比较[1+2+3+4~+(n-1)]次
二、排序方式时间测试
几种排序的时间复杂度
排序法 |
最差时间分析 | 平均时间复杂度 | 稳定度 | 空间复杂度 |
冒泡排序 | O(n2) | O(n2) | 稳定 | O(1) |
快速排序 | O(n2) | O(n*log2n) | 不稳定 | O(log2n)~O(n) |
选择排序 | O(n2) | O(n2) | 稳定 | O(1) |
二叉树排序 | O(n2) | O(n*log2n) | 不一顶 | O(n) |
插入排序 |
O(n2) | O(n2) | 稳定 | O(1) |
堆排序 | O(n*log2n) | O(n*log2n) | 不稳定 | O(1) |
希尔排序 | O | O | 不稳定 | O(1) |
这里直接测试每种排序方式消耗的时间,采用两种方式:一种是每次排序都重新设置数组每个元素的值,第二种是不同的排序方式排序同一个数组
2. 不同排序方式,不同的数组
>测试代码:
/** * 排序测试,每种排序方式对不同随机数组排序多次,取平均时间 * * @author admin * */ public class RandomSortTest { private static Logger log = LogManager.getLogger(); public static void main(String[] args) { // 87, 76, 65, 51, 43, 31, 23, 17, 6, 3 // 6, 17, 23, 31, 43, 51, 65, 76, 87, 3 // 3, 6, 17, 23, 31, 43, 51, 65, 76, 87 // 数组长度 & 数组元素随机生成的最大值 & 每种排序方式测试次数 int len = 100000, numMax = 10000,sortTypeCount = 10; // 待排序数组 int[] arr = new int[len]; // 排序类 Sorted sorter = null; // 循环调用多个排序方法,每次调用getSorter()会返回不同的排序方法 while ((sorter = getSorter()) != null) { long time = 0; for (int i = 0; i < sortTypeCount; i++) { // 给每个数组元素设置随机值 SortUtil.insertRandomNumber(arr, numMax); // 排序,并返回排序时间 time += SortUtil.testSortTime(arr, sorter); } log.info("排序方法[{}],平均[{}/{}]耗时{}ms", sorter.getClass().getSimpleName(), time, sortTypeCount, time / sortTypeCount); } } /** * 排序方式:1、快速排序;2、选择排序;3、冒泡排序;4、冒泡排序(改进) */ private static int sortType = 1; private static Sorted getSorter() { Sorted sorter = null; // 1、快速排序;2、选择排序;3、冒泡排序;4、冒泡排序(改进) switch (sortType++) { case 1: sorter = new QuickSortDemo(); break; case 2: sorter = new SelectSortDemo(); break; case 3: sorter = new PopSortDemo(); break; case 4: sorter = new PopSortImproveDemo(); break; default: break; } return sorter; } }
>测试结果(len=10W):
2017-03-22 22:30:11.214 [main] INFO - 排序方法[QuickSortDemo],平均[92/10]耗时9ms cn.tinyf.demo.sort.RandomSortTest 2017-03-22 22:30:38.408 [main] INFO - 排序方法[SelectSortDemo],平均[27182/10]耗时2718ms cn.tinyf.demo.sort.RandomSortTest 2017-03-22 22:33:04.408 [main] INFO - 排序方法[PopSortDemo],平均[145987/10]耗时14598ms cn.tinyf.demo.sort.RandomSortTest 2017-03-22 22:35:26.352 [main] INFO - 排序方法[PopSortImproveDemo],平均[141931/10]耗时14193ms cn.tinyf.demo.sort.RandomSortTest
相关推荐
用JAVA实现七个常用排序,包括:冒泡排序,插入排序,选择排序,希尔排序,快速排序,归并排序和堆排序。
十大常用排序算法(java实现),冒泡排序,简单选择排序等
关于各种排序算法的图形演示,做得很不错
常用各种排序算法Java的实现_差不多了__.rar常用各种排序算法Java的实现_差不多了__.rar
Java常用排序算法 Java常用排序算法 Java常用排序算法 Java常用排序算法
用java实现了以下算法: 1、冒泡排序、冒泡排序的两种改进。 2、插入排序。 3、选择排序。 4、希尔排序。 5、归并排序。 6、快速排序。
用java对常用排序算法进行分析与实现.包含: 插入排序 直接插入排序、希尔排序 • 选择排序 简单选择排序、堆排序 • 交换排序 冒泡排序、快速排序 • 归并排序 • 基数排序
java 常用排序算法 java 常用排序算法 java 常用排序算法
常见排序算法java实现,包括快速排序,归并排序,堆排序三个常用nlogn复杂度的算法
主要总结了常用的七大排序算法java实现!
常用排序算法的Java实现源码,包括冒泡排序,快速排序,直接插入排序,希尔排序,直接选择排序,堆排序,归并排序,基数排序,计数排序。
java实现的常用的几种基本排序算法,插入、交换、选择、归并
Java常用排序算法程序员必须掌握的8大排序算法Java开发Java经验技巧共16页.pdf.zip
用Java语言实现的几种常用的排序算法。
1. 一个PPT 用动画演示了 插入排序,直接插入排序,希尔排序,附带讲解。 2. 附带其他几种常用排序的java实现的源码。 3. PPT 还是简洁、美观的,可用作模板。
Java常用排序算法源码 稳定:冒泡排序、插入排序、归并排序和基数排序;不稳定:选择排序、快速排序、希尔排序、堆排序
实现了四类排序算法,插入排序、交换排序、选择排序、归并排序,详情请看文档,其中 树形选择排序算法--选择排序、 堆排序--选择排序 这两种算法还没实现,有兴趣的自行解决
Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找 Java常用排序算法&程序员必须掌握的8大排序算法+二分法查找
关于八种常见的排序算法的总结,里面有可运行的Java代码,方便打印
Java常用8大排序算法,包含每种算法详细介绍,及代码如何实现。