排序算法效率分析及总结

语言主流的排序算法效率剖析及总结班级：计科二班

作者：

XXX日期：2016-3-29

工作：算法收集及程序组合，结论总结。礼拜二

同组者：刘文工作：程序测试，时间记录以及程序演示此次我们组主要收集了冒泡排序算法，简单排序算法，直接插入排序算法，希尔排序算法，堆排序算法，迅速排序算法六种常有的排序算法，并对它们的运转效率作了一个简单的测试与剖析。A冒泡排序：算法思想简单描绘：在要排序的一组数中，对目前还未排好序的范围内的所有数，自上而下对相邻的两个数挨次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们交换。冒泡排序是稳固的。算法时间复杂度：O(N2)下边我们来测试试看不一样数据量的排序时间：这是200个乱序随机数：冒泡排序运转时间为毫秒这是1000个乱序随机数：冒泡排序运转时间为毫秒这是5000个乱序随机数：冒泡排序运转时间为毫秒这是20000个乱序随机数：冒泡排序运转时间为毫秒从不一样数据量的纵向剖析来看，1，在冒泡排序算法里，跟着数据量的增添，其运转时间也会愈来愈长。2，在两百个数据的时候，其运转时间少到忽视不计，即运算瞬时达成。这说明冒泡排序在办理小数据量的时候仍是很给力的3，当办理的数据量从5000提到20000的时候，冒泡排序的运转时间发生了质的增添。从几十毫秒到几千毫秒，运转时间大大增添，从这里可见，冒泡排序在办理略微大的数据的时候便已经展现出了力所不及感，我个人感觉已不大合用。简单项选择择排序：算法思想简单描绘：在要排序的一组数中，选出最小的一个数与第一个地点的数交换；而后在剩下的数中间再找最小的与第二个地点的数交换，这样循环到倒数第二个数和最后一个数比较为止。选择排序是不稳固的。时间复杂度：O(N2)下边我们依旧来测试试看简单项选择择排序在不一样数据量的运转时间：这是200个乱序随机数：简单项选择择排序运转时间：毫秒这是1000个乱序随机数：简单项选择择排序运转时间：毫秒这是5000个乱序随机数：简单项选择择排序运转时间：毫秒这是20000个乱序随机数：简单项选择择排序运转时间：毫秒从不一样数据量的纵向剖析来看，1，其运转时间跟着数据量的增添而增添2，简单项选择择排序同冒泡排序相同，在办理像200个这样的小数据量的时候，其运转时间能够忽视不计，即瞬时达成3，当数据量从5000提升到20000的时候，其运转时间也是提升了几十倍。直接插入排序算法思想简单描绘：在要排序的一组数中，假定前面(n-1)[n>=2]个数已经是排好次序的，此刻要把第n个数插到前面的有序数中，使得这n个数也是排好次序的。这样频频循环，直到所有排好次序。直接插入排序是稳固的。算法时间复杂度：O(N2)下边我们来简单测试试看直接插入排序在不一样数据量下的运转时间：这是200个乱序随机数：直接插入排序运转时间：毫秒这是1000个乱序随机数：直接插入排序运转时间：毫秒这是5000个乱序随机数：直接插入排序运转时间：毫秒这是20000个乱序随机数：直接插入排序运转时间：毫秒从不一样数据量的纵向剖析来看：直接插入排序在想200个这样的小数据量的时候履行特别快，效率高。当数据量增添的20000的时候，运转时间会猛增几十倍，效率体现降落趋向。D希尔排序算法思想简单描绘：在直接插入排序算法中，每次插入一个数，使有序序列只增添1个节点，而且对插入下一个数没有供给任何帮助。假如比较相隔较远距离（称为增量）的数，使得数挪动时能越过多个元素，则进行一次比较便可能除去多个元故旧换。算法先将要排序的一组数按某个增量d分红若干组，每组中记录的下标相差

d.对每组中所有元素进行排序，而后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到

1时，整个要排序的数被分红一组，排序达成。希尔排序是不稳固的。希尔排序时间复杂度：O（均匀）最好的O(N)最差的O(N2)下边我们来简单测试试看希尔排序在不一样数据量的运转时间状况：这是200个乱序随机数：希尔排序运转时间为：毫秒这是1000个乱序随机数：希尔排序的运转时间：毫秒这是5000个乱序随机数：希尔排序的运转时间：毫秒这是20000个乱序随机数：希尔排序的运转时间：毫秒从不一样数据量的纵向剖析来看：从200个到20000量的随机数，希尔排序运转的时间都是特别快的，效率极高。20000个数据的时候也不过不过5毫秒，这说明希尔排序在办理大数据的能力上特别优胜。E堆排序算法思想简单描绘：堆排序是一种树形选择排序，是对直接选择排序的有效改良。堆的定义以下：拥有n个元素的序列（h1,h2,...,hn),当且仅当知足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)时称之为堆。在这里只议论知足前者条件的堆。由堆的定义能够看出，堆顶元素（即第一个元素）必为最大项。完整二叉树能够很直观地表示堆的构造。堆顶为根，其余为左子一个堆，这时堆的根节点的数最大。而后将根节点与堆的最后一个节点交换。而后对前面(n-1)个数从头调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后获得有n个节点的有序序列。从算法描绘来看，堆排序需要两个过程，一是成立堆，二是堆顶与堆的最后一个元故旧换地点。因此堆排序有两个函数构成。一是建堆的浸透函数，二是频频调用浸透函数实现排序的函数。堆排序是不稳固的。算法时间复杂度：O(nlog2n)。下边我们测试试看堆排序在不一样数据量的运转成效：这是200个乱序随机数：堆排序运转时间：毫秒这是1000个乱序随机数：堆排序运转时间：毫秒这是5000个乱序随机数：堆排序运转时间：毫秒这是20000个乱序随机数：堆排序运转时间：毫秒从不一样数据量的纵向剖析来看：堆排序不由在办理小数据的时候效率特别高，就算办理几万个数据，也几乎是瞬时达成。从200到20000个数据的运转结果来看，堆排序在办理大数据的能力上仍是很强的。迅速排序算法思想简单描绘：迅速排序是对冒泡排序的一种实质改良。它的基本思想是经过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只好保证最大数值的数移到正确地点，而待排序序列的长度可能只减少1。迅速排序经过一趟扫描，就能保证某个数（以它为基准点吧）的左侧各数都比它小，右侧各数都比它大。而后又用相同的方法办理它左右两边的数，直到基准点的左右只有一个元素为止。明显迅速排序能够用递归实现，自然也能够用栈化解递归实现。迅速排序是不稳固的。最理想状况算法时间复杂度：O(nlog2n)，最坏O(n2)下边我们测试试看迅速排序在不一样数据量的运转状况：这是200个乱序随机数：迅速排序运转时间毫秒这是1000个乱序随机数：迅速排序运转时间：毫秒这是5000个乱序随机数：迅速排序运转时间毫秒这是20000个乱序随机数：迅速排序运转时间毫秒从不一样数据量纵向剖析来看：跟着数据量的增添，迅速排序运转的时间也愈来愈长在办理小数据量的时候，迅速排序效率特别高在办理大数据的时候，运转时间所花的也不是很长，是能够接受的，个人以为迅速排序是一种比较均衡的算法。横向剖析这6种排序算法的效率：在办理小数据量的时候，6中排序算法的效率都是特别可观的，都是能够接受的。但依据算法详细来看