我已经创建了新的排序算法,这个算法的基本概念是从给定列表中找到最小和最大的元素,并用左角和右角元素交换它们,这将重复直到我们到达mid元素.
该算法在比Quick sort和merge sort更短的时间内执行.我想确定这个算法是否比快速排序更好.
我的算法代码
public class VeryQuickVersion1 { public static void main(String args[]) { long current = System.nanoTime(); int[] first = { 8 ,1 ,3 ,2, 6, 5, 7, 4, 12 ,9, 11 ,10 ,14 ,13, 15}; for (int x=0,y=first.length - 1;xfirst[i]) { low = first[i]; li = i; } if (high < first[i]) { high = first[i]; hi = i; } } first[li]=first[x]; first[hi]=first[y]; first[x]=low; first[y]=high; } /* for(int i:first){ System.out.println(i); }*/ System.out.println(System.nanoTime() - current); } }
该算法所花费的时间是:10148并且快速排序算法对于相同列表所花费的时间是:17498
上述算法的时间复杂度似乎是O(n^2)
.
如您所见,有2个嵌套for
循环.外部一个从运行x = 0, y = n
到x < y
,并且在每个步骤它减少x++
和y--
.而其他内部回路从x
到y
.
这可以看作是一个系列n + (n-2) + (n-4) + .... + 0
.这显然给了时间复杂性O(n^2)
时间复杂度不是按照您的方式计算的.您应该检查当输入的大小增加时,此程序所花费的时间将如何增加.并使用不同类型的输入(ex exnding,random等)测试相同的内容.
在收集了大量输入和不同类型输入的数据之后,您将看到作为O(nlogn)
时间复杂度的算法与具有O(n^2)
时间复杂度的算法之间的差异.
注意:您可以看到本网站如何增加时间的真正差异.注意在输入长度增加到的时间后,时间会增加50000
.