2006-09-12

重新温习数据结构二:简单排序

这里并没有给出完整的例子,只是一些代码块.我说的是最核心的一些部分.
1、冒泡排序，这应该是性能最差的一种排序，不提倡用.

  1. public void bubbleSort()   
  2.   {   
  3.   int out, in;   
  4.   for(out=nElems-1; out>1; out--)   // 外层的循环,nElems是数组的大小   
  5.      for(in=0; in<out; in++)        // 里面层的循环   
  6.         if( a[in] > a[in+1] )          
  7.            swap(in, in+1);          // 交换两个数   
  8.   }     

交换的方法：

  1. private void swap(int one, int two)   
  2. {   
  3. long temp = a[one];   
  4. a[one] = a[two];   
  5. a[two] = temp;   
  6. }  


小结：冒泡排序的交换和比较操作的次数都和N2成正比，排序需要O(N2)的时间级别.

2、选择排序的算法:

 

  1. public void selectionSort()   
  2.     {   
  3.     int out, in, min;   
  4.   
  5.     for(out=0; out<nElems-1; out++)   // 外层的循环,nElems是数组的大小   
  6.        {   
  7.        min = out;                     //最小值设为min   
  8.        for(in=out+1; in<nElems; in++) // 里面层的循环   
  9.           if(a[in] < a[min] )         // 如果有更小的值   
  10.               min = in;                   
  11.        swap(out, min);                // 交换   
  12.        }      
  13.     }   

小结：选择排序与冒泡排序执行了相同次数的比较N*(N-1)/2。当N值比较大时，比较的次数是主要，这时候采用选择排序性能也不好；当N值比较小的时候，选择排序的性能还是比较好的.

3、插入排序：性能比冒泡排序，选择排序好，在局部有序的情况下，插入排序的性能很好.

 

  1. public void insertionSort()   
  2.       {   
  3.       int in, out;   
  4.   
  5.       for(out=1; out<nElems; out++)         
  6.          {   
  7.          long temp = a[out];            // 标记一下   
  8.          in = out;                             
  9.          while(in>0 && a[in-1] >= temp) // 直到有一个值比temp小的   
  10.             {   
  11.             a[in] = a[in-1];            // 移动出一个空位   
  12.             --in;                              
  13.             }   
  14.          a[in] = temp;                  // 插入这一个值temp   
  15.          }     
  16.       }     
  17.   

小结：如果数组是基本有序或是有序了，这时候用插入排序只需要O(N)的时间。但如果对于逆序的数据，性能并不比冒泡排序快，这一点需要注意.

下一次会介绍多几种排序的，有空且心情好的时候再过来写写。

评论
发表评论

您还没有登录，请登录后发表评论