Skip to main content

排序算法

时间复杂度

        这个时间复杂度还是很好计算的:外循环和内循环以及判断和交换元素的时间开销;

       最优的情况也就是开始就已经排序好序了,那么就可以不用交换元素了,则时间花销为:[ n(n-1) ] /  2;所以最优的情况时间复杂度为:O( n^2 );

       最差的情况也就是开始的时候元素是逆序的,那么每一次排序都要交换两个元素,则时间花销为:[ 3n(n-1) ] / 2;(其中比上面最优的情况所花的时间就是在于交换元素的三个步骤);所以最差的情况下时间复杂度为:O( n^2 );

        综上所述:

       最优的时间复杂度为:O( n^2 ) ;有的说 O(n),下面会分析这种情况;

       最差的时间复杂度为:O( n^2 );

       平均的时间复杂度为:O( n^2 );

空间复杂度

      空间复杂度就是在交换元素时那个临时变量所占的内存空间;

     最优的空间复杂度就是开始元素顺序已经排好了,则空间复杂度为:0;

     最差的空间复杂度就是开始元素逆序排序了,则空间复杂度为:O(n);

     平均的空间复杂度为:O(1);