排序研究一

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

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

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

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

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

一,冒泡排序

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比较小,特别是如果交换的性能消耗比比较的性能消耗大得多时,用选择排序是相当快的。

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;
      }

三,插入排序

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

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:

class Link
   {
   public long dData;                  

   public Link next;
   public Link(long dd)
      { dData = dd; }
   }

建立有序链表SortedList.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:

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

添加评论