冒泡和归并排序是两种常用的排序方法,实际应用中性能差别有多大呢,通过如下有两个小测试可以看到它们之间大概的差距。
需求:
对10000个员工根据编号排序,员工编号以A开头。由于各公司分别编号,员工编号可以重复。
util类:
public class SortUtil { private static final int EMP_NUMBER = 10000; public static void swap(Employee[] employees, int i, int j){ Employee temp = employees[i]; employees[i] = employees[j]; employees[j] = temp; } public static Employee[] createEmployees(){ long start = System.currentTimeMillis(); Employee[] employees = new Employee[EMP_NUMBER]; for(int i = 0; i < EMP_NUMBER; i++){ employees[i] = new Employee(); employees[i].setEmNO("A"+ String.valueOf((int)(Math.random() * 1000))); } System.out.println("~~~~~~~~ createEmployees() Time elapsed : "+ (System.currentTimeMillis() - start)); return employees; } }
2路归并排序:
/** * 对10000个员工号码进行排序 * 归并排序 * * @author Administrator * */ public class TestSortMergeEmployee { private static Employee[] employees = null; public void mergeSort(Employee[] array) { if(employees == null || employees.length == 0 || employees.length == 0) throw new RuntimeException("******** Array is null or Empty!"); long start = System.currentTimeMillis(); Employee[] temp = new Employee[array.length]; mSort(array, temp, 0, array.length - 1); System.out.println("~~~~~~~~ Merge sort time elapsed : "+ (System.currentTimeMillis() - start)); } private void mSort(Employee[] a, Employee[] temp, int first, int last) { if (first < last) { int mid = (first + last) / 2; mSort(a, temp, first, mid); mSort(a, temp, mid + 1, last); merge(a, temp, first, mid, last); } } private void merge(Employee[] a, Employee[] temp, int first, int mid, int last) { int i = first; int j = mid + 1; int m = mid; int n = last; int k = 0; while (i <= m && j <= n) { //if (a[i] < a[j]) if(a[i].compareTo(a[j]) < 0) temp[k++] = a[i++]; else temp[k++] = a[j++]; } while (i <= m) temp[k++] = a[i++]; while (j <= n) temp[k++] = a[j++]; for (i = 0; i < k; i++) a[first + i] = temp[i]; } public static void main(String[] args) { TestSortMergeEmployee sortEmployees = new TestSortMergeEmployee(); employees = SortUtil.createEmployees(); sortEmployees.mergeSort(employees); /*for(int i = 0; i < employees.length; i++){ System.out.println(employees[i].getEmNO()); }*/ } }
冒泡排序:
/** * 对100000个员工号码进行排序 * 冒泡排序 * * @author Administrator * */ public class TestSortBubbleEmployees { private static Employee[] employees = null; public Employee[] sortBuddle(Employee[] employees){ if(employees == null || employees.length == 0 || employees.length == 0) return employees; int length = employees.length; long start = System.currentTimeMillis(); for(int i = 0; i < length; i++){ for(int j = length - 1; j > i + 1; j--){ if(employees[i].compareTo(employees[j]) > 0) SortUtil.swap(employees, i, j); } } System.out.println("~~~~~~~~ Bubble sort time elapsed : "+ (System.currentTimeMillis() - start)); return employees; } /** * @param args */ public static void main(String[] args) { TestSortBubbleEmployees sortEmployees = new TestSortBubbleEmployees(); employees = SortUtil.createEmployees(); Employee[] rtnEmployees = sortEmployees.sortBuddle(employees); /*for(int i = 0; i < rtnEmployees.length; i++){ System.out.println(rtnEmployees[i].getEmNO()); }*/ } }
测试结果:
归并排序:
~~~~~~~~ Merge sort time elapsed : 40
冒泡排序:
~~~~~~~~ Bubble sort time elapsed : 11390
测试结论:
虽然测试环境等因素会影响测试结果,但以上测试结果可以初步证明冒泡排序和归并排序性能差距比较大,大约相差200倍左右。究其原因,冒泡排序移动次数太多了,造成用时较多。
如果按照以上的代码进行测试,当员工增长到10万人时,冒泡排序程序运行几分钟也排不完。如果排序超大数据集时,用时之久可想而知。
因此,虽然冒泡算法是很基础的算法,并且具备比较简单和容易编写等特点,但可用性太差,建议大多数情况下,应该回避该算法。
相关推荐
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
各种排序算法的实现函数:包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。 查找最大最小值函数 findMinMax:在给定数组中查找最大值和最小值。 计算平均值...
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
本文件是7种常用排序算法的实现(C++),包括冒泡排序、选择排序、直接插入排序、希尔排序、堆排序、归并排序以及快速排序。代码详细有注释且有测试用例。
JAVA排序算法: 直接插入,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,包括算法的详细介绍,以及对几种算法的详细测试
采用c++描述了各种排序算法,包括选择排序 冒泡排序 插入排序 基数排序 快速排序 归并排序 。实验内容 1、创建排序类。 2、提供操作:选择排序、冒泡排序、插入排序、*基数排序、*快速排序、*归并排序。 3、*能够...
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
printf("\t2: 冒泡法排序\n"); printf("\t3: 快速排序\n"); printf("\t4: 直接选择排序\n"); printf("\t5: 堆排序\n"); printf("\t6: 归并排序\n"); printf("\t7: 希尔排序\n"); printf("\t*****************...
各种常用c++排序算法,包括插入排序、冒泡排序、选择排序、快速排序、归并排序、希尔排序等
排序算法演示:插入排序、选择排序、冒泡排序、希尔排序、归并排序、快速排序
使用c语言比较几种常用排序的使用时间(归并排序、插入排序、归并排序、冒泡排序、选择排序)
实现一组经典的排序算法,通过实验数据的设计,考察不同规模和分布(正 序序列、反序序列和随机序列)的数据对排序算法运行时间影响的规律,验证理 论分析结果的正确性。 实验要求: 1. 实现以下三组排序方法中的...
排序的基本概念以及其算法的种类,介绍几种常见的排序算法的算法:冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序的算法和分析它们各自的复杂度,然后以表格的形式,清晰直观的表现出它们的复杂度的...
快速排序
VC++多线程实现三种排序算法比较----冒泡排序、快速排序、归并排序,很有意思,可以下载看看!
选择排序,冒泡排序,插入排序 基数排序,快速排序,归并排序
C# 排序算法大全参考资料,比较清淅的一个版本。集中介绍了C#中的冒泡算法、选择排序、插入排序、希尔排序等常用算法,并包含示例代码和注意事项等。
数据结构之排序算法 包含目前所有排序方法: 1 快速排序 2 冒泡排序 3 堆排序 4 希尔排序 5 直接插入排序 6 直接选择排序 7 基数排序 8 箱、桶排序 9 归并排序
经典排序算法,有选择排序,冒泡排序,交换排序,谢尔排序,插入排序基数排序
在这份文档中,我用C语言实现了排序算法的多种方法,包括插入排序、选择排序、冒泡排序、希尔排序、归并排序、快速排序、桶排序和基数排序。这些算法可以帮助我们对数据进行有效的排序和整理,以便更好地处理和分析...