specialping

sort排序

           例:70   73   69   23   93   18   11   68

               i                                  j

快速排序

       1. 用最后一个数和这组数(从头)开始比较大小,

          若这个数小于数组比较的这个数,则交换这两个数的位置

          即j与i比较大小;

for (int i=0;i<10;i++)

   for(int j=9;j>=0;j--)

         排序1:68   73   69   23   93   18   11   70

                            i    i+1                                          j

         结 果:68   70   69   23   93   18   11   73

         O(3)

        

         排序2:68   70   69   23   93   18   11   73

                           i    i+1   i+2  i+3   i+4                   j                 

         结果: 68   70   69   23   73   18   11   93

         O(6)

 

         排序3:68   70   69   23   73   18   11   93    //确定93为最大的数

                           i     i+1  i+2   i+3   i+4  i+5   i+6   j

                           //从这一步可知,下一个数由j+1与前数组注意比较

         结果: 68   70   69   23   73   18   11   93   

                                                 // 意味着开始j的第二重循环

         O(7)

        

         排序4:68   70   69   23   73   18   11   93

                            i                             j-1   j

         结果: 11   70   69   23   73   18   68   93 

         O(2)

 

         排序5:11   70   69   23   73   18   68   93

                            i    i+1                       j-1   j   

         结果:   11   68   69   23   73   18   70   93

        O(3)  

 

         排序6:11   68   69   23   73   18   70   93

                            i    i+1  i+2   i+3   i+4       j-1    j

         结果:  11   68   69   23   70   18   73   93

        O(6)

 

        排序7: 11   68   69   23   70   18   73   93

                             i    i+1                  j-2   j-1    j

        结果:  11   18   69   23   70   68   73   93

        O(3)

 

       排序8:11   18   69   23   70   68   73   93

                         i    i+1  i+2              j-2   j-1   j

       结果:  11   18   68   23   70   69   73   93

       O(4)

 

      排序9: 11   18   68   23   70   69   73   93

                          i    i+1  i+2   i+3   i+4   j-2   j-1    j

      结果:  11   18   68   23   69   70   73   93

      O(6)

 

     排序10:11   18   68   23   69   70   73   93

                         i    i+1  i+2   i+3   j-3   j-2   j-1   j

     结果:    11   18   68   23   69   70   73   93

     O(4)

 

     排序11:11   18   68   23   69   70   73   93

                         i    i+1   i+2  j-4   j-3   j-2   j-1   j

     结果:  11   18    23   68   69   70   73   93

     O(4)

 

预计时间复杂度:O(n)=O(48)

               最大是多少?

posted on 2011-12-09 22:46 曦冉 阅读(472) 评论(0)  编辑 收藏 引用