" id="b1img" alt="米课”N+1“思维建站-非官方免费技术支持,Wordpress/Zencart/Opencart建站、SEO" title="米课”N+1“思维建站-非官方免费技术支持,Wordpress/Zencart/Opencart建站、SEO">
  • " alt="米课”N+1“思维建站-非官方免费技术支持,Wordpress/Zencart/Opencart建站、SEO" title="米课”N+1“思维建站-非官方免费技术支持,Wordpress/Zencart/Opencart建站、SEO" />
  • " alt="Windows/Linux服务器运维技术支持 环境搭建、应用发布、服务器管理、虚拟化、云计算" title="Windows/Linux服务器运维技术支持 环境搭建、应用发布、服务器管理、虚拟化、云计算" />
  • " alt="高校/小型企业网络运维与建设免费技术支持,网络规划、网络优化、故障排除、网络管理" title="高校/小型企业网络运维与建设免费技术支持,网络规划、网络优化、故障排除、网络管理" />

排序算法

程序设计2009-11-12 itlogger阅读(469) 评论(0)

  排序是数据结构中重要的一个部分,也是在实际开发中最易遇到的问题之一,当然了,你也可以不考虑这些排序的算法,直接把要排序的数据insert到数据库中,用数据库的order by 再select一下,也能产生排序结果,不过,开发一个好的系统,性能同样很重要。

  在一堆数据中,是比较的执行耗时多,还是复制交换的执行耗时比较多,大量数据比较时,是否会有内存限制等等,在综合这些因素后,我们选择适当的排序算法,常常会让系统性能提升数倍,当然了,如果你的系统中没有任何需要数据排序的,那就不考虑了。

  所有的排序算法,都是在大数据量时才会显示出其运行差别,所以,在下面的讨论中,大家了解各特性,按需选用。(如果你觉得往数据库里插入数据,再带着order by 去select执行耗时最小,那就使用我提的这个方法吧)

  注:以下的排序,均以int或long型来比较,其实,比较的元素可以是除这以外的任何对象,要对象实现比较功能,可参考jdk的compareable接口,这个后面再讨论。

   所有的问题,都会有一个简单的解决方法,但它往往并不是最佳的方法。

一,冒泡排序

Java代码

public void bubbleSort(int[] array) {   

  int temp;   

  for(int i=0;i<array.length-1;i++){    

   for(int j=i+1;j<array.length;j++){   

    if (array[i]>array[j]){   

     temp=array[i];   

     array[i]=array[j];   

     array[j]=temp;   

    }   

   }   

  }  

  这个是最简单,最易理解的排序算法。从队列的最左边开始,比较0号位置和1号位置的元素,如果左边的元素(0号)大,就让两个元素交换;如果右边的元素大,就什么也不做。然后右移一个位置比较1号位置和2号位置;沿着这个队列照这样比较下去,一直比较到队列的最右端,虽然没有把所有元素排好充,但是最大的那个元素已经在最右边了,也就像是在水底下冒泡一样,冒上来了。然后再从左边的1号开始,再循环前面的操作。。。。

  可以看出,冒泡排序运行需要O(N^2)时间级别,其速度是很慢的,比较次数:N*(N-1)/2,交换次数最坏的情况也是:N*(N-1)/2。

2,选择排序

  选择排序与冒泡排序有点相似,但是,选择排序对冒泡排序做了些许优化:减少元素交换的次数。
  从下面的代码中,我们可以看出,通过每一次循环,标识出当前最小的元素,再做交换。

  选择排序和冒泡排序执行了相同的比较次数:N*(N-1)/2,对于100个数据项就是要4950次比较,但选择排序只进行了不到100次交换。当N值很大时,比较的次数是主要的。所以,当N比较小,特别是如果交换的性能消耗比比较的性能消耗大得多时,用选择排序是相当快的。

Java代码

public void selectionSort(int[] array)   

      {   

      int out, in, min,nElems=array.length;   

  

      for(out=0; out<nElems-1; out++)   // 外层循环   

         {   

         min = out;                     // 最小值   

         for(in=out+1; in<nElems; in++) // 内层循环   

            if(a[in] < a[min] )         // 如果有比最小值还小的   

                min = in;               // 得到新最小值   

         swap(out, min);                // 交换   

         }  // end for(out)   

      }  // end selectionSort()   

  

    

  

 private void swap(int one, int two)   

      {   

      long temp = a[one];   

      a[one] = a[two];   

      a[two] = temp;   

      }  

三,插入排序

  插入排序的特点是局部有序,通过循环,在(局部)有序组中的适当位置插入元素进行排序。然而要做到这一点,就需要把部分已排序的队员右移以让出空间。当把最后一个要比较的元素移位之后,这个移动的过程就结束了。

Java代码

public void insertionSort(int a[]){   

      int in, out,nElems=a.length;   

  

      for(out=1; out<nElems; out++) {    // 外层循环   

          long temp = a[out];            // 先把要插入有序队列中的元素取出   

         in = out;                      // 要从这个元素的左边开始依次比较了   

         while(in>0 && a[in-1] >= temp){ // 比较条件,   

            a[in] = a[in-1];            // 比temp大的元素,就要右移了   

            –in;                       // 再比较左边的   

            }   

         a[in] = temp;                  // 找到合适的位置了   

         }  // end for   

      }  // end insertionSort()  

  在外层的for循环中,out变量从1开始,向右移动。它标记了未排序部分的最左端的数据。而在内层的while循环中,in变量从out变量开始,向左移动,直到temp变量小于in所指的数组数据项,或者它已经不能再往左移动了。while循环的每一趟都向右移动了一个已排序的数据项。

  这个算法需要多少次比较和复制呢?在第一趟排序中,它最多比较一次,在第二趟中最多比较两次,依此类推了,最后一趟最多,N-1次.所以:

     1+2+3+……+N-1=N*(N-1)/2

  然而,在每一趟排序发现插入点之前,平均只有全体数据项的一半真的进行了比较,所以实际上大约是N*(N-1)/4 次 (这个值不是精确值,只是一个概率的估算值,学过数理统计的朋友就不要太过计较了)

  复制的次数大致等于比较的次数,由于一次复制与一次交换的时间耗费不同,所以相对于随机数据,这个算法比冒泡排序快一倍,比选择排序略快。

  如果数据基本有序,插入排序几乎只需要O(N)的时间;然后对于逆序排列的数据,每次比较和移动都会执行,所以这时插入排序并不比冒泡快。

  大家在选择算法时,要注意了,在事先估算待排序数据的状况下,再选择相应的算法。

四,有序链表排序

    这里存储数据的方式就不是前面讨论的用数组来存储了,而是用链表这一个数据结构。

  有序链表排序是一种高效的排序机制。所设有一个无序数组,如果从这个数组中取出数据,然后一个一个地插入有序链表,它们自动地按序排列,把它们从链表中删除重新放入数组,那么数组就会排好序了。

建立链表类Link.java:

Java代码

class Link   

   {   

   public long dData;                     

  

   public Link next;                      

   public Link(long dd)                 

      { dData = dd; }   

   }    

建立有序链表SortedList.java

Java代码

class SortedList   

   {   

   private Link first;               

   public SortedList()               

      { first = null; }                      

   public SortedList(Link[] linkArr)     

  

      {                                  

  

      first = null;                           

      for(int j=0; j<linkArr.length; j++)     

         insert( linkArr[j] );                

  

      }   

   public void insert(Link k)        

  

      {   

      Link previous = null;               

      Link current = first;   

                                          

  

      while(current != null && k.dData > current.dData)   

         {                                

  

         previous = current;   

         current = current.next;          

         }   

      if(previous==null)                 

         first = k;                       

  

      else                                

         previous.next = k;               

  

      k.next = current;                  

      }  // end insert()   

   public Link remove()              

  

      {                              

      Link temp = first;                

  

      first = first.next;                

  

      return temp;                        

  

      }   

   }    

测试类ListInsertionSortApp.java:

Java代码

class ListInsertionSortApp   

   {   

   public static void main(String[] args)   

      {   

      int size = 10;   

                                 // 建立一个随机数组   

      Link[] linkArray = new Link[size];   

  

      for(int j=0; j<size; j++)     

  

         {                               

         int n = (int)(java.lang.Math.random()*99);   

         Link newLink = new Link(n);  // 建立链表   

  

         linkArray[j] = newLink;         

  

         }   

                                    

      System.out.print(“Unsorted array: “);   

      for(int j=0; j<size; j++)   

         System.out.print( linkArray[j].dData + ” “ );   

      System.out.println(“”);   

  

      SortedList theSortedList = new SortedList(linkArray);   

  

      for(int j=0; j<size; j++)     

         linkArray[j] = theSortedList.remove();   

  

                                    

      System.out.print(“Sorted Array:   “);   

      for(int j=0; j<size; j++)   

         System.out.print(linkArray[j].dData + ” “);   

      System.out.println(“”);   

      }    

  

   }    

  这种排序方式总体上比在数组中用常用的插入排序效率更高一些,因为这种方式进行的复制次数少一些,但它仍然是一个时间级为O(N^2)的过程,因为在有序链表中每插入一个新的链结点,平均要与一半已存在数据进行比较。如果插入N个新数据,就进行了N*N/4次比较。每一个链结点只进行两次复制:一次从数组到链表,一次从链表到数组。在数组中进行插入排序需要N*N次移动,相比之下,2*N次移动更好。

注:以上提供的算法出自《Data Structures & Algorithms in Java》by Robert Lafore Sams © 1998

摘至:javaeye

转载请注明 :IT樵客
文章地址:http://www.itlogger.com/program/957.html
标签:, ,
相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注